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

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

प्रमुख विधियाँ संपादित करें

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

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

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       Depends; worst case is   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);[1] can be implemented as a stable sort based on stable in-place merging.[2]
Heapsort         No Selection
Insertion sort         Yes Insertion O(n + d), where d is the number of inversions
Introsort         No Partitioning & Selection Used in several STL implementations
Selection sort         No Selection Stable with O(n) extra space, for example using lists.[3] Used to sort this table in Safari or other Webkit web browser.[4]
Timsort         Yes Insertion & Merging   comparisons when the data is already sorted or reverse sorted.
Shell sort    

or

 
Depends on gap sequence; best known is     No Insertion
Bubble sort         Yes Exchanging Tiny code size
Binary tree sort         Yes Insertion When using a self-balancing binary search tree
Cycle sort       No Insertion In-place with theoretically optimal number of writes
Library sort       Yes Insertion
Patience sorting     No Insertion & Selection Finds all the longest increasing subsequences within O(n log n)
Smoothsort         No Selection An 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 Exchanging Small code size
Gnome sort         Yes Exchanging Tiny code size
Bogosort         No Luck Randomly permute the array and check if sorted.
[5]         Yes


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

सन्दर्भ संपादित करें

  1. "संग्रहीत प्रति". मूल से 11 जनवरी 2013 को पुरालेखित. अभिगमन तिथि 2 दिसंबर 2012.
  2. "संग्रहीत प्रति". मूल से 15 अक्तूबर 2012 को पुरालेखित. अभिगमन तिथि 2 दिसंबर 2012.
  3. "संग्रहीत प्रति". मूल से 9 दिसंबर 2012 को पुरालेखित. अभिगमन तिथि 2 दिसंबर 2012.
  4. "संग्रहीत प्रति". मूल से 21 मार्च 2012 को पुरालेखित. अभिगमन तिथि 2 दिसंबर 2012.
  5. http://www.springerlink.com/content/d7348168624070v7/[मृत कड़ियाँ]
  6. साँचा:Introduction to Algorithms
  7. Goodrich, Michael T.; Tamassia, Roberto (2002). "4.5 Bucket-Sort and Radix-Sort". Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. पपृ॰ 241–243.

इन्हें भी देखें संपादित करें

बाहरी कड़ियाँ संपादित करें