الگوریتمهای مرتبسازی(Sorting algorithms) در این جدول، n تعداد دادهها و k تعداد دادهها با کلیدهای متفاوت است. ستونهای بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان میدهد و حافظه بیانگر مقدار حافظهٔ کمکی (علاوه بر خود دادهها) است.
| نام | بهترین | میانگین | بدترین | حافظه | پایدار | مقایسهای | روش | توضیحات |
|---|---|---|---|---|---|---|---|---|
| مرتب سازی حبابی (Bubble sort) | (O(n | — | (O(n2 | (O(1 | بله | بله | جابجایی | Times are for best variant |
| Cocktail sort | (O(n | — | (O(n2 | (O(1 | بله | بله | جابجایی | |
| Comb sort | (O(n log n | — | (O(n log n | (O(1 | خیر | بله | جابجایی | |
| Gnome sort | (O(n | — | (O(n2 | (O(1 | بله | بله | جابجایی | |
| Selection sort | (O(n2 | (O(n2 | (O(n2 | (O(1 | خیر | بله | گزینشی | |
| Insertion sort | (O(n | — | (O(n2 | (O(1 | بله | بله | درجی | |
| Shell sort | (O(n log n | — | (O(n log2n | (O(1 | خیر | بله | درجی | Times are for best variant |
| Binary tree sort | (O(n log n | — | (O(n log n | (O(1 | بله | بله | درجی | |
| Library sort | (O(n | (O(n log n | (O(n2 | ε+1)n) | بله | بله | درجی | |
| Merge sort | (O(n log n | — | (O(n log n | (O(n | بله | بله | Merging | |
| In-place merge sort | (O(n log n | — | (O(n log n | (O(1 | بله | بله | Merging | Times are for best variant |
| Heapsort | (O(n log n | — | (O(n log n | (O(1 | خیر | بله | گزینشی | |
| Smoothsort | (O(n | — | (O(n log n | (O(1 | خیر | بله | گزینشی | |
| Quicksort | (O(n log n | (O(n log n | (O(n2 | (O(n | خیر | بله | Partitioning | Naive variants use (O(n space |
| Introsort | (O(n log n | (O(n log n | (O(n log n | (O(n | خیر | بله | Hybrid | |
| Pigeonhole sort | (O(n+k | — | (O(n+k | (O(k | بله | خیر | Indexing | |
| Bucket sort | (O(n | (O(n | (O(n2 | (O(k | بله | خیر | Indexing | |
| Counting sort | (O(n+k | — | (O(n+k | (O(n+k | بله | خیر | Indexing | |
| Radix sort | (O(nk | — | (O(nk | (O(n | بله | خیر | Indexing | |
| Patience sorting | (O(n | — | (O(n log n | (O(n | خیر | بله | درجی | تمام زیر دنبالههای صعودی را با (O(n log (log(n پیدا میکند. |
این جدول الگوریتمهایی را توضیح میدهد که به علت اجرای بسیار ضعیف و یا نیاز به سختافزار خاص، کاربرد زیادی ندارند.
| نام | بهترین | میانگین | بدترین | حافظه | پایدار | مقایسهای | توضیحات |
|---|---|---|---|---|---|---|---|
| Bogosort | (O(n | O(n × n!) | بدون حد | (O(1 | خیر | بله | |
| Stooge sort | (O(n2.71 | — | (O(n2.71 | (O(1 | خیر | بله | |
| Bead sort | (O(n | — | (O(n | — | N/A | خیر | به سختافزار مخصوص نیاز دارد. |
| Pancake sorting | (O(n | — | (O(n | — | خیر | بله | به سختافزار مخصوص نیاز دارد. |
| Sorting networks | (O(log n | — | (O(log n | — | بله | بله | Requires a custom circuit of size (O(log n |
|+|
نوشته شده توسط در یکشنبه هفتم آبان 1385 و ساعت 1:2
