সর্টিং অ্যালগোরিদম

কম্পিউটার বিজ্ঞানে (ইংরেজি: computer science) সর্টিং অ্যালগোরিদম (ইংরেজি: Sorting algorithm) বলতে একটি নির্দিষ্ট ক্রমে সাজানো বা ক্রম অনুযায়ী একটি তালিকা তৈরী করাকে বোঝায়। মূলত সর্টিং দুই প্রকার। একটি বড় থেকে ছোট এবং অপরটি ছোট থেকে বড় ক্রমে সাজানো। সবচেয়ে ব্যবহৃত ক্রম হচ্ছে সংখ্যা (১,২,৩,৪.....) এবং আভিধানিক (ক,খ,গ.....) বা (A,B,C.....) ক্রম।

আনুষ্ঠানিকভাবে, যে কোনও সর্টিং অ্যালগরিদমের আউটপুট দুটি শর্ত পূরণ করতে হবে:

 আউটপুটটি মনোটোনিক ক্রমে রাখতে হবে। (প্রতিটি উপাদান প্রয়োজনীয় ক্রমানুসারে পূর্ববর্তী উপাদানের চেয়ে ছোট/বড় নয়)।
 আউটপুটটি ইনপুটের বিন্যাস হবে (একটি reordering, কিন্তু মূল উপাদান সব বজায় থাকবে)।

যদিও কিছু অ্যালগরিদম ক্রমিক অ্যাক্সেসের জন্য ডিজাইন করা হয়েছে, সর্বোচ্চ-পারফরমিং অ্যালগরিদমগুলি ধরে নেয় যে ডেটা একটি ডেটা স্ট্রাকচারে সংরক্ষণ করা হয় যা র‍্যান্ডম অ্যাক্সেসের অনুমতি দেয়।

 প্রকারভেদ 

 উর্ধক্রম (acsending): ছোট থেকে বড় । যেমন :      ১ ,২,৩ ...
 অধঃক্রম (decending):  বড় থেকে ছোট । যেমন :  ... ৩ ,২ ,১

 অ্যালগরিদমের তুলনা 
এই বিশ্লেষণে ধরে নেয়া হয়েছে যে প্রতিটি কি-টির দৈর্ঘ্য ধ্রুবক এবং সমস্ত তুলনা, সোয়াপ এবং অন্যান্য অপারেশন ধ্রুবক সময়ে এগিয়ে যেতে পারে।

লেজেন্ড:

 n হল সাজানোর জন্য রেকর্ডের সংখ্যা।
 তুলনা কলামে নিম্নলিখিত র‍্যাংকিং শ্রেণীবিভাগে বিভক্ত: "সেরা", "গড়" এবং "সবচেয়ে খারাপ" যদি প্রতিটি ক্ষেত্রে সময় জটিলতা দেওয়া হয়।
 "মেমোরি" দ্বারা অ্যালগরিদম কর্তৃক প্রয়োজনীয় অতিরিক্ত স্টোরেজের পরিমাণ নির্দেশ করে।
 রান টাইম এবং মেমরি প্রয়োজনীয়তা ভিতরে বড় O নোটেশন দ্বারা তালিকাভুক্ত, এজন্য লগারিদমের ভিত্তি কোন বিষয় না।
 এখানে নোটেশন log2 n মানে (log n)2.

 তুলনা ক্রম 
নিম্নলিখিত অংশটি  তুলনার সর্টের একটি টেবিল। গাণিতিক বিশ্লেষণ দেখায় যে একটি তুলনা সর্ট গড়ে O(n log n) এর চেয়ে ভাল কাজ সম্পাদন করতে পারে না।
+Comparison sortsনামসেরাগড়নিকৃষ্টমেমরিস্থায়ীত্বIn-placeপদ্ধতিOther notesHeapsort1নাYesSelectionAn optimized version of selection sort. Performs selection sort by constructing and maintaining a max heap to find the maximum in  time.IntrosortনাYesPartitioning & SelectionUsed in several STL implementations. Performs a combination of Quicksort, Heapsort, and Insertion sort.Merge sortnYesনাMergingHighly parallelizable (up to O(log n) using the Three Hungarians' Algorithm).In-Place Merge SortYesYesMergingVariation of Mergesort which uses an  in-place stable merge algorithm, such as rotate merge or symmerge.Tournament sortnYesনাSelectionAn optimization of Selection Sort, which uses a tournament tree to select the min/max.Tree sort(balanced)nYesনাInsertionWhen using a self-balancing binary search tree.Block sortn1YesYesInsertion & MergingCombine a block-based ⁠⁠ in-place merge algorithm with a bottom-up merge sort.Smoothsortn1নাYesSelectionAdaptive variant of heapsort based on the Leonardo sequence instead of a binary heap.TimsortnnYesনাInsertion & MergingMakes n-1 comparisons when the data is already sorted or reverse sorted.Patience sortingnnনানাInsertion & SelectionFinds all the longest increasing subsequences in O(n log n).CubesortnnYesনাInsertionMakes  comparisons when the data is already sorted or reverse sorted.QuicksortনাYesPartitioningQuicksort can be done in-place with O(log n) stack space.FluxsortnnYesনাPartitioning & MergingAn adaptive branchless stable introsort.CrumsortnনাYesPartitioning & MergingAn in-place, but unstable variant of Fluxsort.Library sortnনানাInsertionSimilar to a gapped insertion sort.Shellsort (Ciura) (Ciura) (Ciura)
(Pratt)1নাYesInsertionSmall code size. Complexity may vary depending on gap sequence. Pratt's sequence has a নিকৃষ্ট-case of . The (Extended) Ciura sequence গড়s  empirically.Comb sort1নাYesExchangingFaster than bubble sort on গড়.Insertion sortn1YesYesInsertionO(n + d), in the নিকৃষ্ট case over sequences that have d inversions.Bubble sortn1YesYesExchangingTiny code size.Cocktail shaker sortn1YesYesExchangingA bi-directional variant of Bubblesort.Gnome sortn1YesYesExchangingTiny code size.Odd–even sortn1YesYesExchangingCan be run on parallel processors easily.Strand sortnnYesনাSelectionSelection sort1নাYesSelectionTiny code size. নাted for its simplicity and small number of element moves. Makes exactly  swaps.Exchange sort1নাYesExchangingTiny code size.Cycle sort1নাYesSelectionIn-place with theoretically optimal number of writes.

 Non-comparison sorts 
The following table describes integer sorting algorithms and other sorting algorithms that are not comparison sorts. These algorithms are not limited to Ω(n log n) unless meet unit-cost random-access machine model as described below. 

 Complexities below assume n items to be sorted, with keys of size k, digit size d, and r the range of numbers to be sorted.
 Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that n ≪ 2k, where ≪ means "much less than".
 In the unit-cost random-access machine model, algorithms with running time of , such as radix sort, still take time proportional to Θ(n log n), because n is limited to be not more than , and a larger number of elements to sort would require a bigger k in order to store them in the memory.

+Non-comparison sortsNameBestগড়নিকৃষ্টMemoryStablen ≪ 2kNotesPigeonhole sort—YesYesCannot sort non-integers.Bucket sort (uniform keys)—YesনাAssumes uniform distribution of elements from the domain in the array.
Also cannot sort non-integers.Bucket sort (integer keys)—YesYesIf r is ⁠⁠, then গড় time complexity is ⁠⁠.Counting sort—YesYesIf r is ⁠⁠, then গড় time complexity is ⁠⁠.LSD Radix SortYesনা recursion levels, 2d for count array.
Unlike most distribution sorts, this can sort non-integers.MSD Radix Sort—YesনাStable version uses an external array of size n to hold all of the bins.
Same as the LSD variant, it can sort non-integers.MSD Radix Sort (in-place)—নানাd=1 for in-place,  recursion levels, no count array.SpreadsortnনানাAsymptotic are based on the assumption that n ≪ 2k, but the algorithm does not require this.Burstsort—নানাHas better constant factor than radix sort for sorting strings. Though relies somewhat on specifics of commonly encountered strings.FlashsortnnনানাRequires uniform distribution of elements from the domain in the array to run in linear time. If distribution is extremely skewed then it can go quadratic if underlying sort is quadratic (it is usually an insertion sort). In-place version is not stable.Postman sort——নাA variation of bucket sort, which works very similarly to MSD Radix Sort. Specific to post service needs.Recombinant sortনানাHashing, Counting, Dynamic Programming, Multidimensional data
Samplesort can be used to parallelize any of the non-comparison sorts, by efficiently distributing data into several buckets and then passing down sorting to several processors, with no need to merge as buckets are already sorted between each other.

 Others 
Some algorithms are slow compared to those discussed above, such as the bogosort with unbounded run time and the stooge sort which has O(n2.7) run time. These sorts are usually described for educational purposes to demonstrate how the run time of algorithms is estimated. The following table describes some sorting algorithms that are impractical for real-life use in traditional software contexts due to extremely poor performance or specialized hardware requirements.
NameBestগড়নিকৃষ্টMemoryStableComparisonOther notesBead sortnSS—NoWorks only with positive integers. Requires specialized hardware for it to run in guaranteed ⁠⁠ time. There is a possibility for software implementation, but running time will be ⁠⁠, where S is the sum of all integers to be sorted; in the case of small integers, it can be considered to be linear.Merge-insertion sortcomparisonscomparisonscomparisonsVariesNoYesMakes very few comparisons worst case compared to other sorting algorithms.
Mostly of theoretical interest due to implementational complexity and suboptimal data moves."I Can't Believe It Can Sort"1NoYesNotable primarily for appearing to be an erroneous implementation of either Insertion Sort or Exchange Sort.Spaghetti (Poll) sortnnnYesPollingThis is a linear-time, analog algorithm for sorting a sequence of items, requiring O(n) stack space, and the sort is stable. This requires n parallel processors. See spaghetti sort § Analysis.Sorting networkVariesVariesVariesVariesVaries (stable sorting networks require more comparisons)YesOrder of comparisons are set in advance based on a fixed network size.Bitonic sorter parallel parallel non-parallel1NoYesAn effective variation of Sorting networks. [disputed – discuss]BogosortnUnbounded1NoYesRandom shuffling. Used for example purposes only, as even the expected best-case runtime is awful.
Worst case is unbounded when using randomization, but a deterministic version guarantees  worst case.LinearSortEither  or nYesNoParody sorting algorithm to show the risk of overly relying on Big O notation - runs a merge sort and then sleeps until a fixed constant amount of time has elapsed from the function call, thus (wastefully) guaranteeing a fixed runtime below the hardcoded minimum.Stooge sortnNoYesSlower than most of the sorting algorithms (even naive ones) with a time complexity of O(nlog 3 / log 1.5 ) = O(n2.7095...) Can be made stable, and is also a sorting network.SlowsortnNoYesA multiply and surrender algorithm, antonymous with divide-and-conquer algorithm.Franceschini's method1YesYesMakes O(n) data moves in the worst case.  Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.
Theoretical computer scientists have invented other sorting algorithms that provide better than O(n log n) time complexity assuming certain constraints, including:

 Thorup's algorithm, a randomized integer sorting algorithm, taking O(n log log n) time and O(n) space.
 AHNR algorithm, an integer sorting algorithm which runs in  time deterministically, and also has a randomized version which runs in linear time when words are large enough, specifically  (where w is the word size).
 A randomized integer sorting algorithm taking  expected time and O(n) space.

 তালিকা 
 বাবল সর্ট
 হিপ সর্ট
 মার্জ সর্ট
 কুইক সর্ট
 সিলেকশন সর্ট
 ইনসার্শন সর্ট
 কিউব সর্ট
 শেল সর্ট
 বাইনারি ট্রি সর্ট
 কম্ব সর্ট
 কাউন্টিং সর্ট
 বাকেট সর্ট
 রেডিক্স সর্ট
 জোড়-বিজোড় সর্ট
 ইন্ট্রো সর্ট
 কিউব সর্ট
 টপোলজিকাল সর্ট
 কোয়ান্টাম সর্ট

বিষয়শ্রেণী:সর্টিং অ্যালগোরিদম
বিষয়শ্রেণী:অসম্পূর্ণ
বিষয়শ্রেণী:উপাত্ত প্রক্রিয়াজাতকরণ