What is sorting and searching algorithm { SORTING और खोज एल्गोरिथम क्या है}

Sorting Algorithm

Data को किसी field के आधार पर एक निश्चित क्रम में व्यवस्थित रखना ही sorting कहलाता है। यह निश्चित क्रम आरोही (ascending) अथवा अवरोही (descending) में से कोई एक हो सकता है। Ascending order में न्यूनतम संख्या सबसे ऊपर/पहले तथा अधिकतम संख्या सबसे नीचे/बाद में होती है। Descending order में क्रम इसके विपरीत होता है अर्थात् अधिकतम संख्या सबसे ऊपर तथा न्यूनतम संख्या सबसे नीचे होती है।

Types of Sorting (सॉर्टिंग के प्रकार) डाटा को निश्चित क्रम में व्यवस्थित करने हेतु प्रयुक्त Sorting निम्न प्रकार की होती है

1. Selection sort
2. Insertion sort
3. Heap sort
4. Merge sort
5. Bubble sort
6. Shell sort
7. Quick sort
8. Radix sort

Selection Sort

Selection sort तकनीक में सबसे छोटी संख्या का चयन करके उसे array के पहले element के साथ exchange कर दिया जाता है। अब शेष n-1 elements में से न्यूनतम value वाले element को खोजकर उसे array के दूसरे element के साथ exchange कर दिया जाता है। इसी प्रकार यह क्रम आगे बढ़ता रहता है। यह अदला-बदली की प्रक्रिया अंतिम दो elements तक चलती रहती है।

Bubble Sort

Bubble sorting सबसे अधिक जानी पहचानी sorting होती है। ऐसा इसकी आसानी तथा इसके आकर्षक नाम के कारण है। हाँलाकि अधिक values की sorting करने के लिए यह सबसे अधिक खराब मानी जाती है। ऐसा इसलिए है क्योंकि अन्य sorting तकनीकों की अपेक्षा इसमें समय अधिक लगता है। इसे exchange sort भी कहा जाता है। इसमें बारम्बार तुलना करने तथा आवश्यकता होने पर array के दो लगातार elements को आपस में बदलने की क्रिया होती है। इ  Sorting में शुरुआत में दो elements को compare किया जाता है। यदि left element, right element से बड़ा है तो वे अपने स्थान को एक दूसरे से बदल लेगें तथा यह comparison अंत तक चलता रहेगा। Bubble Sort की best case complexity O(n) तथा Worst case complexity O(n2 ) हैं 

Insertion Sort

इस प्रकार की sorting में सर्वप्रथम array के प्रथम दो elements को sort किया जाता है। इसके बाद 3rd element को पहले दोनों elements के सापेक्ष क्रमवार स्थिति में रखा जाता है। अब array के शुरू के तीन elements क्रम में हैं। यह process अंत तक चलता रहेगा जब तक पूरा array short न हो जाए। Insertion Sort average and worst case complexity O(n’) तथा best case complexity O(n) है।

Shell sort

यह insertion sort का सुधरा हुआ रूप है जो 1957 में D.L. Shell नामक गणितज्ञ ने दिया था। उन्हीं के नाम पर इसका नाम shell sort रखा गया है।

Insertion sort

Insertion sort में values केवल एक ही position पर move की जाती है क्योंकि इसमें value की तुलना उसकी adjacent संख्याओं के साथ की जाती है। यदि हम एक निश्चित दूरी पर रखी दो संख्याओं को लें तो हम उन संख्याओं को compare करके sort कर सकेंगे। इसके पश्चात् इस दूरी को पटाकर वही प्रक्रिया दोहराई जाती है। अंत में यह दूरी 1 रह जाती है तथा values को insertion sort के द्वारा sort कर लिया जाता है। इसमें दूरी को कम करते रहना होता है, अतः इसे diminishing increment sort भी कहा जाता है।

Heap sort

Heap sort तकनीक का अध्ययन करने के लिए पहले heap tree को जानने की आवश्यकता होगी। इसमें heap tree की सहायता से ही sorting की जाती है। Heap Tree का निर्माण करना Heap tree एक पूर्ण binary tree होता है जो arrays के द्वारा प्रदर्शित किया जाता है। यह दो प्रकार का हो सकता है- max heap तथा min heap/Max heap एक ऐसा tree होता है जिसमें किसी भी node की संख्या उसके children की values के बराबर अथवा अधिक होती है।

Min heap एक ऐसा tree होता है जिसमें किसी भी node की संख्या उसके children की values के बराबर अथवा कम होती है। इस प्रकार min heap में न्यूनतम संख्या सदैव root पर होती है। Quick sort यह संख्याओं को sort करने की सर्वाधिक प्रचलित तकनीकों में से एक है। यह “divide and conquer” तकनीक पर आधारित होती है। इसका विकास C.A.R. Hoare ने किया था।

Quick sortй Worst case complexity O(n) Best case complexity O(n log n) है। Divide and Conquer तकनीक में sort किए जाने वाले array को दो भागों में विभक्त किया जाता है। फिर इसके प्रत्येक भाग को फिर से दो भागों में विभक्त किया जाता है। यही प्रक्रिया लगातार चलती रहती है। दो भागों में विभाजन के लिए array में से किसी एक value का चयन किया जाता है। सामान्यतया array की प्रथम value arr [0] का चयन किया जाता है। इस प्रकार, यदि array का नाम arr है तथा key arr [0] = की अन्य सभी संख्याऐं दो भागों में इस प्रकार विभक्त हो है तो array जाती हैं कि- बाँई ओर वाले भाग में सभी values arr [0] से कम होती हैं। दाँई ओर वाले भाग में सभी values arr[0] से अधिक होती है।

Merge sort

यह sorting तकनीक भी “divide and conquer” तकनीक पर आधारित होती है। यहाँ पर arrays को तब तक दो भागों में विभाजित किया जाता है जब तक प्रत्येक भाग में केवल 1 (एक) संख्या न बच जाए। इसके बाद इन दोनों भागों की संख्याओं को sort करते हुए इन्हें merge किया जाता है। इसीलिए इसे merge sort कहा जाता है। इस तकनीक की मुख्य हानि यह है कि इसमें मूल array के अतिरिक्त भी memory की आवश्यकता होती है। अतः यदि संख्याऐं अधिक हैं तो अधिक memory की आवश्यकता होगी। ऐसी परिस्थिति में यह अधिक उचित तकनीक नहीं मानी जाती है। Merge sort Worst case complexity O(n logn)|

Radix sort

Radix sort को bucket sort भी कहा जाता है। इसका उपयोग नामों की सूची को alphabetical order में व्यवस्थित करने में किया जा सकता है। वर्णमाला अक्षरों को alphabetical order में व्यवस्थित करने की इस स्थिति में base या radix 26 होगा क्योंकि alphabets की कुल संख्या 26 होती है। इसी प्रकार decimal संख्याओं को sort करने के लिए base 10 होगा क्योंकि संख्याऐं 10(0-9) होती हैं। अतः हमें 10 buckets की आवश्यकता होती है। इन buckets का क्रमांक 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 होता है। नोट— Decimal संख्याओं की sorting इकाई स्थान (right to left) से होती है।

Searching Algorithm

यह किसी दिए हुए array में से किसी संख्या को find (खोजने) की प्रक्रिया है। यह दो प्रकार की होती है –

1. Linear search
2. Binary search

Linear search

यह सामान्य तथा आसान तकनीक है। इसमें खोजी जाने वाली संख्या को एक-एक करके array की संख्याओं के साथ तब तक compar  किया जाता है जब तक या तो यह array समाप्त नहीं हो जाता अथवा खोजी जाने वाली संख्या array में मिल नहीं जाती है। Linear Search को sequential search भी कहा जाता है।\

Binary search

यह “divide and conquer” तकनीक पर आधारित होती है। बहुत ही तीव्र तथा योग्य तकनीक है। इसके लिए आवश्यक है कि दिए गए array में सभी संख्याऐं sorted हों। इस प्रकार की searching में search की जाने वाली संख्या की सर्वप्रथम array की middle value से तुलना की जाती है। यदि वह संख्या यहाँ नहीं है तो array को दो भागों में विभाजित कर दिया जाता है। साथ ही यह भी जाँचा जाता है कि खोजी जाने वाली संख्या middle value से कम है अथवा अधिक। यदि संख्या कम है। विभाजित array के पहले भाग में ही होगी अन्यथा विभाजित के दूसरे भाग में तथा जब तक संख्या मिल नहीं जाती है यही क्रम लगातार चलता रहता है।

array Hashing

Hashing तकनीक से इच्छित data को बड़े database में से quickly find (शीघ्रता से खोजा जा सकता है। इस तकनीक में सारी संख्याओं को एक निश्चित array index पर रखा जाता है, न कि क्रमिक रूप इसी प्रकार, खोजी जाने वाली value को भी array index में परिवर्तित किया जाता है तथा सीधे उसके index पर ही value को खोजा जाता है। संख्याओं को array index में बदलने के लिए hash function का उपयोग किया जाता है तथा जो array संख्याओं को index के आधार पर रखने तथा खोजने की सुविधा देता है, उसे hash table कहते हैं। किसी भी hash function का चयन करने के दो आधार होते हैं।

1. यह गणना करने में आसान होना चाहिए।
2. यह एक अद्वितीय अर्थात् unique address जुटाने में सक्षम होना चाहिए ताकि एक ही address अथवा index पर कम से कम संख्याऐं एकत्रित हो पाऐं।