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

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

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

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

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

প্রকারভেদ

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

অ্যালগরিদমের তুলনা

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

লেজেন্ড:

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

তুলনা ক্রম

নিম্নলিখিত অংশটি তুলনার সর্টের একটি টেবিল। গাণিতিক বিশ্লেষণ দেখায় যে একটি তুলনা সর্ট গড়ে O(n log n) এর চেয়ে ভাল কাজ সম্পাদন করতে পারে না।

Comparison sorts
নাম	সেরা	গড়	নিকৃষ্ট	মেমরি	স্থায়ীত্ব	In-place	পদ্ধতি	Other notes
Heapsort				1	না	Yes	Selection	An optimized version of selection sort. Performs selection sort by constructing and maintaining a max heap to find the maximum in time.
Introsort					না	Yes	Partitioning & Selection	Used in several STL implementations. Performs a combination of Quicksort, Heapsort, and Insertion sort.
Merge sort				n	Yes	না	Merging	Highly parallelizable (up to O(log n) using the Three Hungarians' Algorithm).
In-Place Merge Sort					Yes	Yes	Merging	Variation of Mergesort which uses an in-place stable merge algorithm, such as rotate merge or symmerge.
Tournament sort				n	Yes	না	Selection	An optimization of Selection Sort, which uses a tournament tree to select the min/max.
Tree sort			(balanced)	n	Yes	না	Insertion	When using a self-balancing binary search tree.
Block sort	n			1	Yes	Yes	Insertion & Merging	Combine a block-based ⁠⁠ in-place merge algorithm with a bottom-up merge sort.
Smoothsort	n			1	না	Yes	Selection	Adaptive variant of heapsort based on the Leonardo sequence instead of a binary heap.
Timsort	n			n	Yes	না	Insertion & Merging	Makes n-1 comparisons when the data is already sorted or reverse sorted.
Patience sorting	n			n	না	না	Insertion & Selection	Finds all the longest increasing subsequences in O(n log n).
Cubesort	n			n	Yes	না	Insertion	Makes comparisons when the data is already sorted or reverse sorted.
Quicksort					না	Yes	Partitioning	Quicksort can be done in-place with O(log n) stack space.
Fluxsort	n			n	Yes	না	Partitioning & Merging	An adaptive branchless stable introsort.
Crumsort	n				না	Yes	Partitioning & Merging	An in-place, but unstable variant of Fluxsort.
Library sort				n	না	না	Insertion	Similar to a gapped insertion sort.
Shellsort	(Ciura)	(Ciura)	(Ciura) (Pratt)	1	না	Yes	Insertion	Small code size. Complexity may vary depending on gap sequence. Pratt's sequence has a নিকৃষ্ট-case of . The (Extended) Ciura sequence গড়s empirically.
Comb sort				1	না	Yes	Exchanging	Faster than bubble sort on গড়.
Insertion sort	n			1	Yes	Yes	Insertion	O(n + d), in the নিকৃষ্ট case over sequences that have d inversions.
Bubble sort	n			1	Yes	Yes	Exchanging	Tiny code size.
Cocktail shaker sort	n			1	Yes	Yes	Exchanging	A bi-directional variant of Bubblesort.
Gnome sort	n			1	Yes	Yes	Exchanging	Tiny code size.
Odd–even sort	n			1	Yes	Yes	Exchanging	Can be run on parallel processors easily.
Strand sort	n			n	Yes	না	Selection
Selection sort				1	না	Yes	Selection	Tiny code size. নাted for its simplicity and small number of element moves. Makes exactly swaps.
Exchange sort				1	না	Yes	Exchanging	Tiny code size.
Cycle sort				1	না	Yes	Selection	In-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 ≪ 2^k, 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 sorts
Name	Best	Memory	Stable	n ≪ 2^k	Notes
Pigeonhole sort	—		Yes	Yes	Cannot 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)	—		Yes	Yes	If r is ⁠⁠, then গড় time complexity is ⁠⁠.
Counting sort	—		Yes	Yes	If r is ⁠⁠, then গড় time complexity is ⁠⁠.
LSD Radix Sort			Yes	না	recursion levels, 2^d 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.
Spreadsort	n		না	না	Asymptotic are based on the assumption that n ≪ 2^k, 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.
Flashsort	n	n	না	না	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(n^2.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.

Name	Best	গড়	নিকৃষ্ট	Memory	Stable	Comparison	Other notes
Bead sort	n	S	S		—	No	Works 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 sort	comparisons	comparisons	comparisons	Varies	No	Yes	Makes 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"				1	No	Yes	Notable primarily for appearing to be an erroneous implementation of either Insertion Sort or Exchange Sort.
Spaghetti (Poll) sort	n	n	n		Yes	Polling	This 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 network	Varies	Varies	Varies	Varies	Varies (stable sorting networks require more comparisons)	Yes	Order of comparisons are set in advance based on a fixed network size.
Bitonic sorter	parallel	parallel	non-parallel	1	No	Yes	An effective variation of Sorting networks. ^{[disputed – discuss]}
Bogosort	n		Unbounded	1	No	Yes	Random 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.
LinearSort		Either or		n	Yes	No	Parody 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 sort				n	No	Yes	Slower than most of the sorting algorithms (even naive ones) with a time complexity of O(n^{log 3 / log 1.5} ) = O(n^2.7095...) Can be made stable, and is also a sorting network.
Slowsort				n	No	Yes	A multiply and surrender algorithm, antonymous with divide-and-conquer algorithm.
Franceschini's method				1	Yes	Yes	Makes 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.

তালিকা