शाटन की कलनविधि का स्रोत देखें

{{आधार}} 
[[कम्प्यूटर विज्ञान]] में उन [[अल्गोरिद्म|कलनविधियों]] को '''अनुक्रमण कलनविधि''' (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) 

== अनुक्रमण विधियों की तुलना ==
==Comparison of algorithms==
नीचे की सारणी में ''n'' अनुक्रमित किए जाने वाले रेकार्डों की संख्या है।

{|class="wikitable sortable"
|+ '''तुलना अनुक्रमण'''
!विधि का नाम !! सर्वोत्तम !! मध्यम !! सबसे खराब<br /> !! स्मृति (Memory) !! स्थायित्व !! विधि<br /> !! width="350"|टिप्पणी
<!-- Sorting Guide:
     00 - constant,
     05 - lg(n),
     10 - n^c (0 < c < 1),
     15 - n,
     20 - n*lg(n) or lg(n!),
     23 - n*(lg(n))^2 or n^c (1 < c < 2),
     25 - n^2,
     30 - n^c (c > 2),
     40 - c^n (c > 1),
     45 - n!,
     50 - miscellaneous -->
|- align="center"
|[[द्रुत अनुक्रमण]]
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|style="background:#ffdddd"|{{Sort|25|<math>\mathcal{} n^2</math>}}
|style="background:#ffffdd"|{{Sort|05|<math>\mathcal{} \log n</math>}}
|style="background:#ffffdd"| Depends
| Partitioning
| align="left" | Quicksort is usually done in place with O(log(''n'')) stack space.{{citation needed|date=December 2010}} Most implementations are unstable, as stable in-place partitioning is more complex. [[Naïve algorithm|Naïve]] variants use an O(''n'') space array to store the partition.{{citation needed|date=December 2010}}<!-- see talk page discussion for December 2010 -->
|- align="center"
|[[Merge sort]]
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ffdddd"|{{Sort|15|Depends; worst case is <math> \mathcal{} n </math>}}
|style="background:#ddffdd"| Yes
| Merging
| align="left" | [[Merge sort#Parallel processing|Highly parallelizable]] (up to O(log(''n''))) for processing large amounts of data.
|- align="center"
|nowrap|[[In-place]] [[Merge sort]]
|{{Sort|50|<math> \mathcal{} - </math>}}
|{{Sort|50|<math> \mathcal{} - </math>}}
|style="background:#ffffdd"|{{Sort|23|<math> \mathcal{} {n \left(\log n \right)^2} </math>}}
|style="background:#ddffdd"|{{Sort|00|<math> \mathcal{} {1} </math>}}
|style="background:#ddffdd"| Yes
| Merging
| align="left" | Implemented in Standard Template Library (STL);<ref>{{Cite web |url=http://www.sgi.com/tech/stl/stable_sort.html |title=संग्रहीत प्रति |access-date=2 दिसंबर 2012 |archive-url=https://web.archive.org/web/20130111210431/http://www.sgi.com/tech/stl/stable_sort.html |archive-date=11 जनवरी 2013 |url-status=live }}</ref> can be implemented as a stable sort based on stable in-place merging.<ref>{{Cite web |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381 |title=संग्रहीत प्रति |access-date=2 दिसंबर 2012 |archive-url=https://web.archive.org/web/20121015165623/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381 |archive-date=15 अक्तूबर 2012 |url-status=live }}</ref>
|- align="center"
|[[Heapsort]]
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|00|<math>\mathcal{} {1} </math>}}
|style="background:#ffdddd"| No
| Selection
| align="left" | 
|- align="center"
|[[Insertion sort]]
|style="background:#ddffdd"|{{Sort|15|<math> \mathcal{} n </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ddffdd"|{{Sort|00|<math> \mathcal{} {1} </math>}}
|style="background:#ddffdd"| Yes
| Insertion
|align=left|O(''n'' + ''d''), where ''d'' is the number of [[Permutation groups#Transpositions.2C simple transpositions.2C inversions and sorting|inversions]]
|- align="center"
|[[Introsort]]
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|style="background:#ffffdd"|{{Sort|05|<math>\mathcal{} \log n</math>}}
|style="background:#ffdddd"| No
| Partitioning & Selection
|align="left"| Used in several [[Standard Template Library|STL]] implementations
|- align="center"
|[[Selection sort]]
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ddffdd"|{{Sort|00|<math> \mathcal{} {1} </math>}}
|style="background:#ffffdd"| No
| Selection
|align=left| Stable with O(n) extra space, for example using lists.<ref>{{Cite web |url=http://www.algolist.net/Algorithms/Sorting/Selection_sort |title=संग्रहीत प्रति |access-date=2 दिसंबर 2012 |archive-url=https://web.archive.org/web/20121209184535/http://www.algolist.net/Algorithms/Sorting/Selection_sort |archive-date=9 दिसंबर 2012 |url-status=dead }}</ref> Used to sort this table in Safari or other Webkit web browser.<ref>{{Cite web |url=http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp |title=संग्रहीत प्रति |access-date=2 दिसंबर 2012 |archive-url=https://web.archive.org/web/20120321170841/http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp |archive-date=21 मार्च 2012 |url-status=dead }}</ref>
|- align="center"
|[[Timsort]]
|style="background:#ddffdd"|{{Sort|15|<math> \mathcal{} {n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math> \mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math> \mathcal{} {n \log n} </math>}}
|style="background:#ffdddd"|{{Sort|15|<math> \mathcal{} n </math>}}
|style="background:#ddffdd"| Yes
| Insertion & Merging
| align="left" | <math>\mathcal{} {n} </math> comparisons when the data is already sorted or reverse sorted.
|- align="center"
|[[Shell sort]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n</math>}}
|style="background:#ffffdd"|{{Sort|23|<math>\mathcal{} n (\log n)^2</math><br /><br />or<br /><br /><math>\mathcal{} n^{3/2}</math>}}
|style="background:#ffffdd"|{{Sort|23|Depends on gap sequence; best known is <math>\mathcal{} n (\log n)^2</math>}}
|style="background:#ddffdd"|{{Sort|00|<math>\mathcal{} 1</math>}}
|style="background:#ffdddd"| No
| Insertion
|align=left|
|- align="center"
|[[Bubble sort]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n</math>}}
|style="background:#ffdddd"|{{Sort|25|<math>\mathcal{} n^2</math>}}
|style="background:#ffdddd"|{{Sort|25|<math>\mathcal{} n^2</math>}}
|style="background:#ddffdd"|{{Sort|00|<math>\mathcal{} {1}</math>}}
|style="background:#ddffdd"| Yes <!-- Dispute earlier No. Equal values are never swapped, so they never get out of order -->
| Exchanging
|align=left| Tiny code size
|- align="center"
|[[Binary tree sort]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n</math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ffdddd"|{{Sort|15|<math>\mathcal{} n </math>}}
|style="background:#ddffdd"| Yes
| Insertion
|align="left"| When using a [[self-balancing binary search tree]]
|- align="center"
|[[Cycle sort]]
|{{Sort|50|&mdash;}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ddffdd"|{{Sort|00|<math>\mathcal{} {1} </math>}}
|style="background:#ffdddd"| No
| Insertion
|align=left| In-place with theoretically optimal number of writes
|- align="center"
|[[Library sort]]
|{{Sort|50|&mdash;}}
|style="background:#ddffdd"|{{Sort|20|<math> \mathcal{} {n \log n} </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ffdddd"|{{Sort|15|<math> \mathcal{} n </math>}}
|style="background:#ddffdd"| Yes
| Insertion
|align=left| 
|- align="center"
|[[Patience sorting]]
|{{Sort|50|&mdash;}}
|{{Sort|50|&mdash;}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|style="background:#ffdddd"|{{Sort|15|<math>\mathcal{} n</math>}}
|style="background:#ffdddd"| No
| Insertion & Selection
| align="left" | Finds all the [[longest increasing subsequence]]s within O(''n'' log ''n'')
|- align="center"
|[[Smoothsort]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} {n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|00|<math>\mathcal{} {1} </math>}}
|style="background:#ffdddd"| No
| Selection
| align="left" |An [[adaptive sort]] - <math>\mathcal{} {n} </math> comparisons when the data is already sorted, and 0 swaps.
|- align="center"
|[[Strand sort]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n </math>}}
|style="background:#ffdddd"|{{Sort|25|<math>\mathcal{} n^2</math>}}
|style="background:#ffdddd"|{{Sort|25|<math>\mathcal{} n^2</math>}}
|style="background:#ffdddd"|{{Sort|15|<math>\mathcal{} n</math>}}
|style="background:#ddffdd"| Yes
| Selection
| align="left" | 
|- align="center"
|[[Tournament sort]]
|{{Sort|50|&mdash;}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|style="background:#ddffdd"|{{Sort|20|<math>\mathcal{} n \log n</math>}}
|
|
| Selection
| align="left" | 
|- align="center"
|[[Cocktail sort]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n</math>}}
|style="background:#ffdddd"|{{Sort|25|<math>\mathcal{} n^2</math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ddffdd"|{{Sort|00|<math>\mathcal{} {1} </math>}}
|style="background:#ddffdd"| Yes
| Exchanging
|align=left| 
|- align="center"
|[[Comb sort]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n</math>}}
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n \log n</math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ddffdd"|{{Sort|00|<math> \mathcal{} {1} </math>}}
|style="background:#ffdddd"| No
| Exchanging
|align="left"|Small code size
|- align="center"
|[[Gnome sort]]
|style="background:#ddffdd"|{{Sort|15|<math> \mathcal{} n </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ffdddd"|{{Sort|25|<math> \mathcal{} n^2 </math>}}
|style="background:#ddffdd"|{{Sort|00|<math> \mathcal{} {1} </math>}}
|style="background:#ddffdd"| Yes
| Exchanging
|align=left| Tiny code size
|- align="center"
|[[Bogosort]]
|style="background:#ddffdd"|{{Sort|15|<math> \mathcal{} n </math>}}
|style="background:#ffdddd"|{{Sort|45|<math> \mathcal{} n \cdot n! </math>}}
|style="background:#ffdddd"|{{Sort|45|<math> \mathcal{} {n \cdot n! \to \infty} </math>}}
|style="background:#ddffdd"|{{Sort|00|<math> \mathcal{} {1} </math>}}
|style="background:#ffdddd"| No
| Luck
| align="left" | Randomly permute the array and check if sorted.
|- align="center"
|<ref>http://www.springerlink.com/content/d7348168624070v7/{{Dead link|date=जून 2020 |bot=InternetArchiveBot }}</ref>
|{{Sort|50|<math> \mathcal{} - </math>}}
|style="background:#ddffdd"|{{Sort|20|<math> \mathcal{} n \log n </math>}}
|style="background:#ddffdd"|{{Sort|20|<math> \mathcal{} {n \log n} </math>}}
|style="background:#ddffdd"|{{Sort|00|<math> \mathcal{} {1} </math>}}
|style="background:#ddffdd"| Yes
|
| align="left" |
|}


{|class="wikitable sortable"
|+ गैर-तुलना अनुक्रमण
!Name !! Best !! Average !! Worst<br /> !! Memory<br /> !! Stable !! ''n'' << 2<sup>''k''</sup> !! Notes<br />
|- align="center"
|[[Pigeonhole sort]]
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n + 2^k</math>
|style="background:#ddffdd"|<math>\;n + 2^k</math>
|<math>\;2^k</math>
|style="background:#ddffdd"| Yes
| Yes
|
|- align="center"
|[[Bucket sort]] (uniform keys)
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n+k</math>
|style="background:#ffdddd"|<math>\;n^2 \cdot k</math>
|<math>\;n \cdot k</math>
|style="background:#ddffdd"| Yes
| No
| Assumes uniform distribution of elements from the domain in the array.<ref name="clrs">{{Introduction to Algorithms|edition=2}}</ref>
|- align="center"
|[[Bucket sort]] (integer keys)
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n+r</math>
|style="background:#ddffdd"|<math>\;n+r</math>
|<math>\;n+r</math>
|style="background:#ddffdd"| Yes
| Yes
|r is the range of numbers to be sorted. If r = <math>\mathcal{O}\left({n} \right)</math> then Avg RT = <math>\mathcal{O}\left({n} \right)</math><ref name="gt">{{cite book
 | last1 = Goodrich | first1 = Michael T. | author1-link = Michael T. Goodrich
 | last2 = Tamassia | first2 = Roberto | author2-link = Roberto Tamassia
 | contribution = 4.5 Bucket-Sort and Radix-Sort
 | pages = 241–243
 | publisher = John Wiley & Sons
 | title = Algorithm Design: Foundations, Analysis, and Internet Examples
 | year = 2002}}</ref>
|- align="center"
|[[Counting sort]]
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n+r</math>
|style="background:#ddffdd"|<math>\;n+r</math>
|<math>\;n+r</math>
|style="background:#ddffdd"| Yes
| Yes
|r is the range of numbers to be sorted. If r = <math>\mathcal{O}\left({n} \right)</math> then Avg RT = <math>\mathcal{O}\left({n} \right)</math><ref name="clrs"/>
|- align="center"
|[[Radix sort#Least significant digit radix sorts|LSD Radix Sort]]
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n \cdot \frac{k}{d}</math>
|style="background:#ddffdd"|<math>\;n \cdot \frac{k}{d}</math>
|<math>\mathcal{} n </math>
|style="background:#ddffdd"| Yes
| No
|<ref name="clrs"/><ref name="gt"/>
|- align="center"
|[[Radix sort#Most significant digit radix sorts|MSD Radix Sort]]
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n \cdot \frac{k}{d}</math>
|style="background:#ddffdd"|<math>\;n \cdot \frac{k}{d}</math>
|<math>\mathcal{} n + \frac{k}{d} \cdot 2^d </math>
|style="background:#ddffdd"| Yes
| No
| Stable version uses an external array of size n to hold all of the bins
|- align="center"
|[[Radix sort#Most significant digit radix sorts|MSD Radix Sort]]
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n \cdot \frac{k}{d}</math>
|style="background:#ddffdd"|<math>\;n \cdot \frac{k}{d}</math>
|<math>\frac{k}{d} \cdot 2^d</math>
|style="background:#ffdddd"| No
| No
| In-Place. k / d recursion levels, 2<sup>d</sup> for count array
|- align="center"
|[[Spreadsort]]
|{{Sort|03|&mdash;}}
|style="background:#ddffdd"|<math>\;n \cdot \frac{k}{d}</math>
|style="background:#ddffdd"|<math>\;n \cdot \left({\frac{k}{s} + d} \right)</math>
|<math>\;\frac{k}{d} \cdot 2^d</math>
|style="background:#ffdddd"| No
| No
| Asymptotics are based on the assumption that n << 2<sup>k</sup>, but the algorithm does not require this.
|}

== सन्दर्भ ==
<references/>

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

== बाहरी कड़ियाँ ==
{{wikibooks|Algorithm implementation|Sorting|Sorting algorithms}}
{{wikibooks|A-level Mathematics|OCR/D1/Algorithms#Sorting Algorithms|Sorting algorithms}}
* [https://web.archive.org/web/20150303022622/http://www.sorting-algorithms.com/ Sorting Algorithm Animations] - Graphical illustration of how different algorithms handle different kinds of data sets.
* [https://web.archive.org/web/20121213233414/http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm Sequential and parallel sorting algorithms] - Explanations and analyses of many sorting algorithms.
* [https://web.archive.org/web/20050624234059/http://www.nist.gov/dads/ Dictionary of Algorithms, Data Structures, and Problems] - Dictionary of algorithms, techniques, common functions, and problems.
* [https://web.archive.org/web/20121022104106/http://www.softpanorama.org/Algorithms/sorting.shtml Slightly Skeptical View on Sorting Algorithms] Discusses several classic algorithms and promotes alternatives to the [[quicksort]] algorithm.

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