Xulosa. Saralash algoritmi Sorting algoritmi

Kiritish tartibi
Asosiy maqola: Kiritish tartibi
Kiritish tartibi kichik saralashlar va asosan saralangan ro'yxatlar uchun nisbatan samarali bo'lgan va ko'pincha murakkab algoritmlarning bir qismi sifatida ishlatiladigan oddiy saralash algoritmidir. Bu ro'yxatdagi elementlarni birma-bir olish va ularni o'zlarining to'g'ri holatiga hamyonimizga qanday pul qo'yishimizga o'xshash yangi tartiblangan ro'yxatga kiritish orqali ishlaydi.^[22] Massivda yangi ro'yxat va qolgan elementlar massivning bo'sh joyini bo'lishishi mumkin, ammo kiritish juda qimmat, shuning uchun quyidagi barcha elementlarni birma-bir almashtirish kerak. Shellsort (quyida ko'rib chiqing) - bu katta ro'yxatlar uchun samaraliroq bo'lgan qo'shilish tartibining bir variantidir.
Tanlov tartibida
Asosiy maqola: Tanlov tartibida
Tanlov tartibida bu joyida taqqoslash. Unda bor O(n²) murakkabligi, uni katta ro'yxatlarda samarasiz qiladi va umuman o'xshashidan yomonroq ishlaydi qo'shish tartibi. Tanlovni saralash soddaligi bilan ajralib turadi, shuningdek, muayyan vaziyatlarda murakkab algoritmlarga nisbatan ishlashning afzalliklariga ega.
Algoritm minimal qiymatni topadi, uni birinchi holatdagi qiymat bilan almashtiradi va ro'yxatning qolgan qismida ushbu amallarni takrorlaydi.^[23] Bu ko'proq emas n almashtirish, shuning uchun almashtirish juda qimmat bo'lgan joyda foydalidir.
Samarali navlar
Amaliy umumiy saralash algoritmlari deyarli har doim o'rtacha vaqt murakkabligi (va umuman olganda eng yomon holatdagi murakkablik) algoritmiga asoslanadi.n jurnal n), ulardan eng keng tarqalgani - yig'ma saralash, birlashma va tezkor tortish. Ularning har birining afzalliklari va kamchiliklari bor, eng muhimi, birlashma tartibini oddiy amalga oshirish O (n) qo'shimcha maydon va tezkor kortni oddiy bajarish O (n²) eng yomon murakkablik. Ushbu muammolarni yanada murakkab algoritm evaziga hal qilish yoki yaxshilash mumkin.
Ushbu algoritmlar tasodifiy ma'lumotlarda asimptotik jihatdan samarali bo'lsa, real ma'lumotlar uchun amaliy samaradorlik uchun turli xil modifikatsiyalar qo'llaniladi. Birinchidan, ushbu algoritmlarning qo'shimcha xarajatlari kichikroq ma'lumotlarda muhim ahamiyat kasb etadi, shuning uchun ko'pincha gibrid algoritm ishlatiladi, odatda ma'lumotlar etarlicha kichik bo'lgandan so'ng qo'shish tartibiga o'tadi. Ikkinchidan, algoritmlar allaqachon saralangan ma'lumotlar yoki deyarli saralangan ma'lumotlarda yomon ishlaydi - bular real dunyo ma'lumotlarida keng tarqalgan va ularni O (n) tegishli algoritmlar bo'yicha vaqt. Nihoyat, ular ham bo'lishi mumkin beqarorva barqarorlik ko'pincha biron bir tarzda kerakli xususiyatdir. Shunday qilib, ko'pincha murakkab algoritmlardan foydalaniladi, masalan Timsort (birlashma tartibiga asoslangan) yoki introsort (tez yig'ilishga asoslangan holda, yana uyumga tushish).