Xulosa. Saralash algoritmi Sorting algoritmi

Thorup algoritmi, cheklangan kattalikdagi domendan kalitlarni saralash uchun tasodifiy algoritm O(n log log n) vaqt va O(n) bo'sh joy.^[20]

Tasodifiy butun sonni saralash algoritmni qabul qilish  kutilgan vaqt va O(n) bo'sh joy.^[21]

Mashhur saralash algoritmlari
Saralash algoritmlari juda ko'p bo'lsa-da, amaliy dasturlarda bir nechta algoritmlar ustunlik qiladi. Kiritish saralashi kichik ma'lumotlar to'plamlari uchun keng qo'llaniladi, katta ma'lumotlar to'plamlari uchun asimptotik jihatdan samarali saralash, birinchi navbatda, yig'indilarni saralash, birlashtirish tartiblari yoki tezkorlar. Samarali dasturlar odatda a dan foydalanadi gibrid algoritm, umumiy saralash uchun asimptotik jihatdan samarali algoritmni rekursiyaning pastki qismidagi kichik ro'yxatlar uchun qo'shish bilan birlashtirish. Yuqori darajada sozlangan dasturlar kabi murakkab variantlardan foydalaniladi, masalan Timsort (birlashtirish saralash, qo'shish tartibini va qo'shimcha mantiq), Android, Java va Python-da ishlatiladigan va introsort (quicksort va heap sort), ba'zilarida ishlatilgan (variant shaklida) C ++ saralash dasturlari va .NET-da.
Belgilangan oraliqdagi raqamlar kabi cheklangan ma'lumotlar uchun, tarqatish turlari sanash sort yoki radix sort kabi keng qo'llaniladi. Bubble sort va variantlari amalda kamdan kam qo'llaniladi, lekin odatda o'quv va nazariy munozaralarda uchraydi.
Ob'ektlarni jismoniy tartiblashda (masalan, qog'ozlar, testlar yoki kitoblar) alfavit qilishda odamlar intuitiv ravishda odatda kichik to'plamlar uchun qo'shilish turlaridan foydalanadilar. Kattaroq to'plamlar uchun odamlar ko'pincha birinchi chelakni, masalan, boshlang'ich harflar bilan, va bir nechta chelaklar juda katta to'plamlarni amaliy saralashga imkon beradi. Ko'pincha bo'shliq nisbatan arzon, masalan, erga yoki katta maydonga narsalarni yoyish, ammo operatsiyalar qimmatga tushadi, ayniqsa ob'ektni uzoq masofaga ko'chirish - mos yozuvlar joylashuvi muhim ahamiyatga ega. Birlashtirish turlari jismoniy ob'ektlar uchun ham amaliydir, chunki ikkita qo'l ishlatilishi mumkin, har bir ro'yxat birlashtirilishi mumkin, boshqa algoritmlar, masalan, yig'ish tartibida yoki tezkor tartiblash, odam uchun juda mos emas. Kabi boshqa algoritmlar kutubxona, bo'sh joy qoldiradigan qo'shilish tartibining bir varianti ham jismoniy foydalanish uchun amaliydir.
Oddiy navlar
Eng oddiy ikkita turdan biri - qo'shimchalarni saralash va tanlash saralashi, ikkalasi ham kichik ma'lumotlarda samarali bo'ladi, chunki qo'shimcha xarajatlar past, ammo katta ma'lumotlarda samarali emas. Kiritish saralashi amalda tanlov saralashiga qaraganda tezroq bo'ladi, chunki taqqoslashlar kamligi va deyarli saralangan ma'lumotlarda yaxshi ishlashi va shuning uchun amalda afzal ko'rilgan, ammo tanlov saralash kamroq yozishlardan foydalanadi va shu bilan yozish ishlashi cheklovchi omil bo'lganda ishlatiladi.