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

कम्प्यूटर विज्ञान में उन कलनविधियों को अनुक्रमण कलनविधि (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)  स्थायित्व  विधि टिप्पणीद्रुत अनुक्रमण Depends Partitioning Quicksort is usually done in place with O(log(n)) stack space. 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.Merge sort Yes Merging Highly parallelizable (up to O(log(n))) for processing large amounts of data.In-place Merge sort Yes Merging Implemented in Standard Template Library (STL); can be implemented as a stable sort based on stable in-place merging.Heapsort No Selection Insertion sort Yes InsertionO(n + d), where d is the number of inversionsIntrosort No Partitioning & Selection Used in several STL implementationsSelection sort No Selection Stable with O(n) extra space, for example using lists. Used to sort this table in Safari or other Webkit web browser.Timsort Yes Insertion & Merging  comparisons when the data is already sorted or reverse sorted.Shell sort No InsertionBubble sort Yes  Exchanging Tiny code sizeBinary tree sort Yes Insertion When using a self-balancing binary search treeCycle sort No Insertion In-place with theoretically optimal number of writesLibrary sort Yes Insertion Patience sorting No Insertion & Selection Finds all the longest increasing subsequences within O(n log n)Smoothsort No SelectionAn adaptive sort -  comparisons when the data is already sorted, and 0 swaps.Strand sort Yes Selection Tournament sort Selection Cocktail sort Yes Exchanging Comb sort No ExchangingSmall code sizeGnome sort Yes Exchanging Tiny code sizeBogosort No Luck Randomly permute the array and check if sorted.http://www.springerlink.com/content/d7348168624070v7/ Yes

+ गैर-तुलना अनुक्रमणName  Best  Average  Worst  Memory  Stable  n << 2k  NotesPigeonhole sort Yes YesBucket sort (uniform keys) Yes No Assumes uniform distribution of elements from the domain in the array.Bucket sort (integer keys) Yes Yesr is the range of numbers to be sorted. If r =  then Avg RT = Counting sort Yes Yesr is the range of numbers to be sorted. If r =  then Avg RT = LSD Radix Sort Yes NoMSD Radix Sort Yes No Stable version uses an external array of size n to hold all of the binsMSD Radix Sort No No In-Place. k / d recursion levels, 2d for count arraySpreadsort No No Asymptotics are based on the assumption that n << 2k, but the algorithm does not require this.

 सन्दर्भ 

 इन्हें भी देखें
 समानुक्रमण (collation)
 समानुक्रमण की कलनविधियाँ

 बाहरी कड़ियाँ 

 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.

श्रेणी:अनुक्रमण एल्गोरिद्म