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

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

साँचा:asbox कम्प्यूटर विज्ञान में उन कलनविधियों को अनुक्रमण कलनविधि (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 अनुक्रमित किए जाने वाले रेकार्डों की संख्या है।

**तुलना अनुक्रमण**
विधि का नाम	सर्वोत्तम	मध्यम	सबसे खराब	स्मृति (Memory)	स्थायित्व	विधि	टिप्पणी
द्रुत अनुक्रमण	20 <math>\mathcal{} n \log n</math>	20 <math>\mathcal{} n \log n</math>	25 <math>\mathcal{} n^2</math>	05 <math>\mathcal{} \log n</math>	Depends	Partitioning	Quicksort is usually done in place with O(log(n)) stack space.साँचा:citation needed 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.साँचा:citation needed
Merge sort	20 <math>\mathcal{} {n \log n} </math>	20 <math>\mathcal{} {n \log n} </math>	20 <math>\mathcal{} {n \log n} </math>	15 Depends; worst case is <math> \mathcal{} n </math>	Yes	Merging	Highly parallelizable (up to O(log(n))) for processing large amounts of data.
In-place Merge sort	50 <math> \mathcal{} - </math>	50 <math> \mathcal{} - </math>	23 <math> \mathcal{} {n \left(\log n \right)^2} </math>	00 <math> \mathcal{} {1} </math>	Yes	Merging	Implemented in Standard Template Library (STL);^[१] can be implemented as a stable sort based on stable in-place merging.^[२]
Heapsort	20 <math>\mathcal{} {n \log n} </math>	20 <math>\mathcal{} {n \log n} </math>	20 <math>\mathcal{} {n \log n} </math>	00 <math>\mathcal{} {1} </math>	No	Selection
Insertion sort	15 <math> \mathcal{} n </math>	25 <math> \mathcal{} n^2 </math>	25 <math> \mathcal{} n^2 </math>	00 <math> \mathcal{} {1} </math>	Yes	Insertion	O(n + d), where d is the number of inversions
Introsort	20 <math>\mathcal{} n \log n</math>	20 <math>\mathcal{} n \log n</math>	20 <math>\mathcal{} n \log n</math>	05 <math>\mathcal{} \log n</math>	No	Partitioning & Selection	Used in several STL implementations
Selection sort	25 <math> \mathcal{} n^2 </math>	25 <math> \mathcal{} n^2 </math>	25 <math> \mathcal{} n^2 </math>	00 <math> \mathcal{} {1} </math>	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	15 <math> \mathcal{} {n} </math>	20 <math> \mathcal{} {n \log n} </math>	20 <math> \mathcal{} {n \log n} </math>	15 <math> \mathcal{} n </math>	Yes	Insertion & Merging	<math>\mathcal{} {n} </math> comparisons when the data is already sorted or reverse sorted.
Shell sort	15 <math>\mathcal{} n</math>	23 <math>\mathcal{} n (\log n)^2</math> or <math>\mathcal{} n^{3/2}</math>	23 Depends on gap sequence; best known is <math>\mathcal{} n (\log n)^2</math>	00 <math>\mathcal{} 1</math>	No	Insertion
Bubble sort	15 <math>\mathcal{} n</math>	25 <math>\mathcal{} n^2</math>	25 <math>\mathcal{} n^2</math>	00 <math>\mathcal{} {1}</math>	Yes	Exchanging	Tiny code size
Binary tree sort	15 <math>\mathcal{} n</math>	20 <math>\mathcal{} {n \log n} </math>	20 <math>\mathcal{} {n \log n} </math>	15 <math>\mathcal{} n </math>	Yes	Insertion	When using a self-balancing binary search tree
Cycle sort	50 —	25 <math> \mathcal{} n^2 </math>	25 <math> \mathcal{} n^2 </math>	00 <math>\mathcal{} {1} </math>	No	Insertion	In-place with theoretically optimal number of writes
Library sort	50 —	20 <math> \mathcal{} {n \log n} </math>	25 <math> \mathcal{} n^2 </math>	15 <math> \mathcal{} n </math>	Yes	Insertion
Patience sorting	50 —	50 —	20 <math>\mathcal{} n \log n</math>	15 <math>\mathcal{} n</math>	No	Insertion & Selection	Finds all the longest increasing subsequences within O(n log n)
Smoothsort	15 <math>\mathcal{} {n} </math>	20 <math>\mathcal{} {n \log n} </math>	20 <math>\mathcal{} {n \log n} </math>	00 <math>\mathcal{} {1} </math>	No	Selection	An adaptive sort - <math>\mathcal{} {n} </math> comparisons when the data is already sorted, and 0 swaps.
Strand sort	15 <math>\mathcal{} n </math>	25 <math>\mathcal{} n^2</math>	25 <math>\mathcal{} n^2</math>	15 <math>\mathcal{} n</math>	Yes	Selection
Tournament sort	50 —	20 <math>\mathcal{} n \log n</math>	20 <math>\mathcal{} n \log n</math>			Selection
Cocktail sort	15 <math>\mathcal{} n</math>	25 <math>\mathcal{} n^2</math>	25 <math> \mathcal{} n^2 </math>	00 <math>\mathcal{} {1} </math>	Yes	Exchanging
Comb sort	15 <math>\mathcal{} n</math>	15 <math>\mathcal{} n \log n</math>	25 <math> \mathcal{} n^2 </math>	00 <math> \mathcal{} {1} </math>	No	Exchanging	Small code size
Gnome sort	15 <math> \mathcal{} n </math>	25 <math> \mathcal{} n^2 </math>	25 <math> \mathcal{} n^2 </math>	00 <math> \mathcal{} {1} </math>	Yes	Exchanging	Tiny code size
Bogosort	15 <math> \mathcal{} n </math>	45 <math> \mathcal{} n \cdot n! </math>	45 <math> \mathcal{} {n \cdot n! \to \infty} </math>	00 <math> \mathcal{} {1} </math>	No	Luck	Randomly permute the array and check if sorted.
^[५]	50 <math> \mathcal{} - </math>	20 <math> \mathcal{} n \log n </math>	20 <math> \mathcal{} {n \log n} </math>	00 <math> \mathcal{} {1} </math>	Yes

गैर-तुलना अनुक्रमण
Name	Best	Average	Worst	Memory	Stable	n << 2^k	Notes
Pigeonhole sort	03 —	<math>\;n + 2^k</math>	<math>\;n + 2^k</math>	<math>\;2^k</math>	Yes	Yes
Bucket sort (uniform keys)	03 —	<math>\;n+k</math>	<math>\;n^2 \cdot k</math>	<math>\;n \cdot k</math>	Yes	No	Assumes uniform distribution of elements from the domain in the array.^[६]
Bucket sort (integer keys)	03 —	<math>\;n+r</math>	<math>\;n+r</math>	<math>\;n+r</math>	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>^[७]
Counting sort	03 —	<math>\;n+r</math>	<math>\;n+r</math>	<math>\;n+r</math>	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>^[६]
LSD Radix Sort	03 —	<math>\;n \cdot \frac{k}{d}</math>	<math>\;n \cdot \frac{k}{d}</math>	<math>\mathcal{} n </math>	Yes	No	^[६]^[७]
MSD Radix Sort	03 —	<math>\;n \cdot \frac{k}{d}</math>	<math>\;n \cdot \frac{k}{d}</math>	<math>\mathcal{} n + \frac{k}{d} \cdot 2^d </math>	Yes	No	Stable version uses an external array of size n to hold all of the bins
MSD Radix Sort	03 —	<math>\;n \cdot \frac{k}{d}</math>	<math>\;n \cdot \frac{k}{d}</math>	<math>\frac{k}{d} \cdot 2^d</math>	No	No	In-Place. k / d recursion levels, 2^d for count array
Spreadsort	03 —	<math>\;n \cdot \frac{k}{d}</math>	<math>\;n \cdot \left({\frac{k}{s} + d} \right)</math>	<math>\;\frac{k}{d} \cdot 2^d</math>	No	No	Asymptotics are based on the assumption that n << 2^k, but the algorithm does not require this.

सन्दर्भ

↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
↑ स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।
↑ http://www.springerlink.com/content/d7348168624070v7/साँचा:category handler साँचा:main other साँचा:main other^{[dead link]}
↑ ^अ ^आ ^इ साँचा:Introduction to Algorithms
↑ ^अ ^आ साँचा:cite book

इन्हें भी देखें

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

साँचा:wikibooks साँचा:wikibooks

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.

[1] स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।

[2] स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।

[3] स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।

[4] स्क्रिप्ट त्रुटि: "citation/CS1" ऐसा कोई मॉड्यूल नहीं है।

[5] ttp://www.springerlink.com/content/d7348168624070v7/साँचा:category handler साँचा:main other साँचा:main other^{[dead link]}

[clrs-6] अ ^आ ^इ साँचा:Introduction to Algorithms

[gt-7] अ ^आ साँचा:cite book

[१]

[२]

[३]

[४]

[५]

[६]

[७]