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

मुक्त ज्ञानकोश विकिपीडिया से
नेविगेशन पर जाएँ खोज पर जाएँ

साँचा:asbox कम्प्यूटर विज्ञान में उन कलनविधियों को अनुक्रमण कलनविधि (sorting algorithm) कहते हैं जो किसी सूची के अवयवों का मूल क्रम बदलकर किसी अन्य क्रमविशेष में व्यवस्थित करने के काम आतीं हैं। जैसे २, ७, ४, ५, ६ को अनुक्रमित करने पर २, ४, ५, ६, ७ मिलते हैं। दो प्रकार के क्रम सबसे अधिक प्रयुक्त होते हैं - संक्यात्मक क्रम (numerical order) तथा कोशक्रम (lexicographical order)। कम्प्यूटर प्रोग्रामों में अनुक्रमण का सम्भवतः सबसे अधिक उपयोग होता है। इसलिए दक्षतापूर्वक अनुक्रमण करने वाले अल्गोरिद्म बहुत महत्व रखते हैं। कुछ अन्य कलनविधियाँ तभी कार्य कर सकती हैं जब पहले आंक। दों को किसी क्रम में व्यवस्थित किया गया हो। उदाहरण के लिए खोजने (search algorithms) और विलय करने वाले (merge algorithms) अल्गोरिद्म (search and merge algorithms) ठीक से तभी काम करेंगे जब उनका उपयोग किसी अनुक्रमित सूची पर किया जाय।

कम्प्यूटरी के आरम्भ से ही अनुक्रमण के प्रश्न पर बहुत अधिक अनुसंधान होता आया है। यद्यपि अनुक्रमण का कार्य बहुत ही सरल कार्य है किन्तु जब किसी वृहद सूची को दक्षतापूर्वक अनुक्रमित करना हो तब यह एक जटिल समस्या बन जाती है।

प्रमुख विधियाँ

  • हीप अनुक्रमण (Heapsort) - यह चयन अनुक्रमण का ही एक रूप है जो अपेक्षाकृत बहुत दक्ष है।
  • द्रुत अनुक्रमण (Quicksort) - यह विभाजन द्वारा विजय (divide and conquer) पर आधारित अनुक्रमण अल्गोरिद्म है। यह सबसे तेज अनुक्रमण विधियों में से एक है।

अनुक्रमण विधियों की तुलना

Comparison of algorithms

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

तुलना अनुक्रमण
विधि का नाम सर्वोत्तम मध्यम सबसे खराब
 स्मृति (Memory) स्थायित्व विधि
 टिप्पणी
द्रुत अनुक्रमण <math>\mathcal{} n \log n</math> <math>\mathcal{} n \log n</math> <math>\mathcal{} n^2</math> <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 <math>\mathcal{} {n \log n} </math> <math>\mathcal{} {n \log n} </math> <math>\mathcal{} {n \log n} </math> 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 <math> \mathcal{} - </math> <math> \mathcal{} - </math> <math> \mathcal{} {n \left(\log n \right)^2} </math> <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 <math>\mathcal{} {n \log n} </math> <math>\mathcal{} {n \log n} </math> <math>\mathcal{} {n \log n} </math> <math>\mathcal{} {1} </math> No Selection
Insertion sort <math> \mathcal{} n </math> <math> \mathcal{} n^2 </math> <math> \mathcal{} n^2 </math> <math> \mathcal{} {1} </math> Yes Insertion O(n + d), where d is the number of inversions
Introsort <math>\mathcal{} n \log n</math> <math>\mathcal{} n \log n</math> <math>\mathcal{} n \log n</math> <math>\mathcal{} \log n</math> No Partitioning & Selection Used in several STL implementations
Selection sort <math> \mathcal{} n^2 </math> <math> \mathcal{} n^2 </math> <math> \mathcal{} n^2 </math> <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 <math> \mathcal{} {n} </math> <math> \mathcal{} {n \log n} </math> <math> \mathcal{} {n \log n} </math> <math> \mathcal{} n </math> Yes Insertion & Merging <math>\mathcal{} {n} </math> comparisons when the data is already sorted or reverse sorted.
Shell sort <math>\mathcal{} n</math> <math>\mathcal{} n (\log n)^2</math>

or

<math>\mathcal{} n^{3/2}</math> 		Depends on gap sequence; best known is <math>\mathcal{} n (\log n)^2</math> <math>\mathcal{} 1</math> No Insertion
Bubble sort <math>\mathcal{} n</math> <math>\mathcal{} n^2</math> <math>\mathcal{} n^2</math> <math>\mathcal{} {1}</math> Yes Exchanging Tiny code size
Binary tree sort <math>\mathcal{} n</math> <math>\mathcal{} {n \log n} </math> <math>\mathcal{} {n \log n} </math> <math>\mathcal{} n </math> Yes Insertion When using a self-balancing binary search tree
Cycle sort — <math> \mathcal{} n^2 </math> <math> \mathcal{} n^2 </math> <math>\mathcal{} {1} </math> No Insertion In-place with theoretically optimal number of writes
Library sort — <math> \mathcal{} {n \log n} </math> <math> \mathcal{} n^2 </math> <math> \mathcal{} n </math> Yes Insertion
Patience sorting — — <math>\mathcal{} n \log n</math> <math>\mathcal{} n</math> No Insertion & Selection Finds all the longest increasing subsequences within O(n log n)
Smoothsort <math>\mathcal{} {n} </math> <math>\mathcal{} {n \log n} </math> <math>\mathcal{} {n \log n} </math> <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 <math>\mathcal{} n </math> <math>\mathcal{} n^2</math> <math>\mathcal{} n^2</math> <math>\mathcal{} n</math> Yes Selection
Tournament sort — <math>\mathcal{} n \log n</math> <math>\mathcal{} n \log n</math> Selection
Cocktail sort <math>\mathcal{} n</math> <math>\mathcal{} n^2</math> <math> \mathcal{} n^2 </math> <math>\mathcal{} {1} </math> Yes Exchanging
Comb sort <math>\mathcal{} n</math> <math>\mathcal{} n \log n</math> <math> \mathcal{} n^2 </math> <math> \mathcal{} {1} </math> No Exchanging Small code size
Gnome sort <math> \mathcal{} n </math> <math> \mathcal{} n^2 </math> <math> \mathcal{} n^2 </math> <math> \mathcal{} {1} </math> Yes Exchanging Tiny code size
Bogosort <math> \mathcal{} n </math> <math> \mathcal{} n \cdot n! </math> <math> \mathcal{} {n \cdot n! \to \infty} </math> <math> \mathcal{} {1} </math> No Luck Randomly permute the array and check if sorted.
[५] <math> \mathcal{} - </math> <math> \mathcal{} n \log n </math> <math> \mathcal{} {n \log n} </math> <math> \mathcal{} {1} </math> Yes


गैर-तुलना अनुक्रमण
Name Best Average Worst
 Memory
 Stable n << 2k Notes
Pigeonhole sort — <math>\;n + 2^k</math> <math>\;n + 2^k</math> <math>\;2^k</math> Yes Yes
Bucket sort (uniform keys) — <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) — <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 — <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 — <math>\;n \cdot \frac{k}{d}</math> <math>\;n \cdot \frac{k}{d}</math> <math>\mathcal{} n </math> Yes No [६][७]
MSD Radix Sort — <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 — <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, 2d for count array
Spreadsort — <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 << 2k, but the algorithm does not require this.

सन्दर्भ

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

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

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

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

"https://hiwiki.iiit.ac.in/index.php?title=शाटन_की_कलनविधि&oldid=138629" से लिया गया