शाटन की कलनविधि

कम्प्यूटर विज्ञान में उन कलनविधियों को अनुक्रमण कलनविधि (sorting algorithm) कहते हैं जो किसी सूची के अवयवों का मूल क्रम बदलकर किसी अन्य क्रमविशेष में व्यवस्थित करने के काम आतीं हैं। जैसे २, ७, ४, ५, ६ को अनुक्रमित करने पर २, ४, ५, ६, ७ मिलते हैं। दो प्रकार के क्रम सबसे अधिक प्रयुक्त होते हैं - संक्यात्मक क्रम (numerical order) तथा कोशक्रम (lexicographical order)। कम्प्यूटर प्रोग्रामों में अनुक्रमण का सम्भवतः सबसे अधिक उपयोग होता है। इसलिए दक्षतापूर्वक अनुक्रमण करने वाले अल्गोरिद्म बहुत महत्व रखते हैं। कुछ अन्य कलनविधियाँ तभी कार्य कर सकती हैं जब पहले आंक। दों को किसी क्रम में व्यवस्थित किया गया हो। उदाहरण के लिए खोजने (search algorithms) और विलय करने वाले (merge algorithms) अल्गोरिद्म (search and merge algorithms) ठीक से तभी काम करेंगे जब उनका उपयोग किसी अनुक्रमित सूची पर किया जाय। कम्प्यूटरी के आरम्भ से ही अनुक्रमण के प्रश्न पर बहुत अधिक अनुसंधान होता आया है। यद्यपि अनुक्रमण का कार्य बहुत ही सरल कार्य है किन्तु जब किसी वृहद सूची को दक्षतापूर्वक अनुक्रमित करना हो तब यह एक जटिल समस्या बन जाती है। प्रमुख विधियाँ बुद्वद अनुक्रमण (Bubble sort) चयन अनुक्रमण (Selection sort) निवेशन अनुक्रमण (Insertion sort) शेल अनुक्रमण (Shell sort) - यह बुलबुला अनुक्रमण का ही एक भिन्न रूप है। कंघा अनुक्रमण (Comb sort) विलय अनुक्रमण (Merge sort) हीप अनुक्रमण (Heapsort) - यह चयन अनुक्रमण का ही एक रूप है जो अपेक्षाकृत बहुत दक्ष है। द्रुत अनुक्रमण (Quicksort) - यह विभाजन द्वारा विजय (divide and conquer) पर आधारित अनुक्रमण अल्गोरिद्म है। यह सबसे तेज अनुक्रमण विधियों में से एक है। गनन अनुक्रमन (Counting sort) बकेट अनुक्रमण (Bucket sort) मूलांक अनुक्रमण (Radix sort) - यह संख्याओं के अंकों की तुलना करके सम्ख्याओं का अनुक्रमण करती है। वितरण अनुक्रमण (Distribution sort) टिम अनुक्रमण (Timsort) अनुक्रमण विधियों की तुलना E=mc^2 Comparison of algorithms नीचे की सारणी में n अनुक्रमित किए जाने वाले रेकार्डों की संख्या है। + तुलना अनुक्रमणविधि का नाम सर्वोत्तम मध्यम सबसे खराब स्मृति (Memory) स्थायित्व विधि टिप्पणीद्रुत अनुक्रमण20202505 Depends Partitioning Quicksort is usually done in place with O(log(n)) stack space.December 2010 Most implementations are unstable, as stable in-place partitioning is more complex. Naïve variants use an O(n) space array to store the partition.December 2010Merge sort20202015 Depends; worst case is Yes Merging Highly parallelizable (up to O(log(n))) for processing large amounts of data.In-place Merge sort50502300 Yes Merging Implemented in Standard Template Library (STL);http://www.sgi.com/tech/stl/stable_sort.html संग्रहीत प्रति 2 दिसंबर 2012 https://web.archive.org/web/20130111210431/http://www.sgi.com/tech/stl/stable_sort.html 11 जनवरी 2013 live can be implemented as a stable sort based on stable in-place merging.http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381 संग्रहीत प्रति 2 दिसंबर 2012 https://web.archive.org/web/20121015165623/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381 15 अक्तूबर 2012 live Heapsort20202000 No Selection Insertion sort15252500 Yes InsertionO(n + d), where d is the number of inversionsIntrosort20202005 No Partitioning & Selection Used in several STL implementationsSelection sort25252500 No Selection Stable with O(n) extra space, for example using lists.http://www.algolist.net/Algorithms/Sorting/Selection_sort संग्रहीत प्रति 2 दिसंबर 2012 https://web.archive.org/web/20121209184535/http://www.algolist.net/Algorithms/Sorting/Selection_sort 9 दिसंबर 2012 dead Used to sort this table in Safari or other Webkit web browser.http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp संग्रहीत प्रति 2 दिसंबर 2012 https://web.archive.org/web/20120321170841/http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp 21 मार्च 2012 dead Timsort15202015 Yes Insertion & Merging comparisons when the data is already sorted or reverse sorted.Shell sort1523 or23 Depends on gap sequence; best known is 00 No InsertionBubble sort15252500 Yes Exchanging Tiny code sizeBinary tree sort15202015 Yes Insertion When using a self-balancing binary search treeCycle sort50 —252500 No Insertion In-place with theoretically optimal number of writesLibrary sort50 —202515 Yes Insertion Patience sorting50 —50 —2015 No Insertion & Selection Finds all the longest increasing subsequences within O(n log n)Smoothsort15202000 No SelectionAn adaptive sort - comparisons when the data is already sorted, and 0 swaps.Strand sort15252515 Yes Selection Tournament sort50 —2020 Selection Cocktail sort15252500 Yes Exchanging Comb sort15152500 No ExchangingSmall code sizeGnome sort15252500 Yes Exchanging Tiny code sizeBogosort15454500 No Luck Randomly permute the array and check if sorted.http://www.springerlink.com/content/d7348168624070v7/जून 2020 InternetArchiveBot 50202000 Yes + गैर-तुलना अनुक्रमणName Best Average Worst Memory Stable n << 2k NotesPigeonhole sort03 — Yes YesBucket sort (uniform keys)03 — Yes No Assumes uniform distribution of elements from the domain in the array.2Bucket sort (integer keys)03 — Yes Yesr is the range of numbers to be sorted. If r = then Avg RT = Goodrich Michael T. Michael T. Goodrich Tamassia Roberto Roberto Tamassia 4.5 Bucket-Sort and Radix-Sort 241–243 John Wiley & Sons Algorithm Design: Foundations, Analysis, and Internet Examples 2002Counting sort03 — Yes Yesr is the range of numbers to be sorted. If r = then Avg RT = LSD Radix Sort03 — Yes NoMSD Radix Sort03 — Yes No Stable version uses an external array of size n to hold all of the binsMSD Radix Sort03 — No No In-Place. k / d recursion levels, 2d for count arraySpreadsort03 — No No Asymptotics are based on the assumption that n << 2k, but the algorithm does not require this. सन्दर्भ इन्हें भी देखें समानुक्रमण (collation) समानुक्रमण की कलनविधियाँ बाहरी कड़ियाँ Algorithm implementation Sorting Sorting algorithms A-level Mathematics OCR/D1/Algorithms#Sorting Algorithms Sorting algorithms Sorting Algorithm Animations - Graphical illustration of how different algorithms handle different kinds of data sets. Sequential and parallel sorting algorithms - Explanations and analyses of many sorting algorithms. Dictionary of Algorithms, Data Structures, and Problems - Dictionary of algorithms, techniques, common functions, and problems. Slightly Skeptical View on Sorting Algorithms Discusses several classic algorithms and promotes alternatives to the quicksort algorithm. श्रेणी:अनुक्रमण एल्गोरिद्म