Xulosa. Saralash algoritmi Sorting algoritmi

Quicksort
Asosiy maqola: Quicksort
Quicksort a algoritmni ajratish va yutish a ga asoslangan bo'lim operatsiya: massivni ajratish, element deb nomlangan burilish tanlangan.^[30][31] Burilishdan kichik bo'lgan barcha elementlar undan oldin va barcha katta elementlar undan keyin harakatlanadi. Buni chiziqli vaqt ichida samarali bajarish mumkin va joyida. Keyinchalik kichik va katta sublistlar rekursiv tartibda saralanadi. Bu o'rtacha vaqt murakkabligini O (n jurnal n), kam xarajatli va shuning uchun bu mashhur algoritm. Quicksort-ning samarali qo'llanilishi (joyida bo'linish bilan) odatda beqaror va biroz murakkab, ammo amalda eng tez tartiblash algoritmlari qatoriga kiradi. Uning oddiy O (log) bilan birga n) bo'sh joydan foydalanish, tezkor saralash eng mashhur saralash algoritmlaridan biri bo'lib, ko'plab standart dasturlash kutubxonalarida mavjud.
Quicksort haqida muhim ogohlantirish shundaki, uning eng yomon ko'rsatkichi O (n²); Bu kamdan-kam hollarda, sodda dasturlarda (birinchi yoki oxirgi elementni pivot sifatida tanlash) bu tartiblangan ma'lumotlar uchun sodir bo'ladi, bu odatiy hol. Quicksortdagi eng murakkab masala - bu yaxshi burilish elementini tanlashdir, chunki burilishlarning doimiy ravishda yomon tanlovi O ning pasayishiga olib kelishi mumkin (n²) ishlash, lekin pivotlarni yaxshi tanlash O (n jurnal n) asimptotik jihatdan maqbul bo'lgan ishlash. Masalan, agar har bir qadamda o'rtacha burilish sifatida tanlanadi, keyin algoritm O (n jurnaln). Kabi mediani topish medianlar medianasi tanlash algoritmi ammo O (n) tartiblanmagan ro'yxatlarda ishlash va shuning uchun saralash bilan katta xarajatlarni amalga oshiradi. Amalda tasodifiy burilishni tanlash deyarli aniq O (n jurnaln) ishlash.
Shellsort

Shell sorti, ko'pikli sortdan farq qiladi, chunki u elementlarni ko'p sonli harakatga keltiradi pozitsiyalarni almashtirish.
Asosiy maqola: Qobiq navlari
Shellsort tomonidan ixtiro qilingan Donald Shell 1959 yilda.^[32] Bu buyurtma elementlarini bir vaqtning o'zida bir nechta pozitsiyadan chiqib ketish orqali qo'shish tartibini yaxshilaydi. Shellsortning kontseptsiyasi shundan iboratki, qo'shish tartibini amalga oshiradi  vaqt, bu erda $ k $ - joyidan ikkita element orasidagi eng katta masofa. Bu shuni anglatadiki, ular umuman olganda O(n²), lekin asosan saralangan, faqat bir nechta elementlari bo'lmagan ma'lumotlar uchun ular tezroq ishlaydi. Shunday qilib, avval elementlarni uzoqdan saralash va saralash uchun elementlar orasidagi bo'shliqni asta-sekin qisqartirish orqali yakuniy saralash ancha tezroq hisoblab chiqiladi. Bitta dasturni ma'lumotlar ketma-ketligini ikki o'lchovli massivda joylashtirish va keyin qo'shma tartib yordamida massiv ustunlarini saralash deb ta'riflash mumkin.
Shellsortning eng yomon vaqt murakkabligi - bu ochiq muammo va ma'lum bo'lgan murakkabliklar bilan ishlatilgan bo'shliqlar ketma-ketligiga bog'liq O(n²) ga O(n^4/3) va Θ (n jurnal² n). Bu, Shellsort ekanligi bilan birlashtirilgan joyida, faqat nisbatan kam miqdordagi kodga muhtoj va undan foydalanishni talab qilmaydi chaqiruv to'plami, kabi xotira yuqori darajadagi holatlarda foydalidir o'rnatilgan tizimlar va operatsion tizim yadrolari.
Bubble sort va variantlari

Ushbu bo'lim emas keltirish har qanday manbalar. Iltimos yordam bering ushbu bo'limni yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Manbaga ega bo'lmagan materialga qarshi chiqish mumkin va olib tashlandi. (2019 yil may) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Bubble sort, va kabi variantlar qobiq saralash va mexnat turi, oddiy, juda samarasiz saralash algoritmlari. Tahlil qilish qulayligi tufayli ular kirish matnlarida tez-tez uchraydi, ammo amalda kamdan kam qo'llaniladi.