Xulosa. Saralash algoritmi Sorting algoritmi

Saralashni birlashtirish
Asosiy maqola: Saralashni birlashtirish
Saralashni birlashtirish allaqachon saralangan ro'yxatlarni yangi tartiblangan ro'yxatga birlashtirish qulayligidan foydalanadi. Har ikkala elementni taqqoslash bilan boshlanadi (ya'ni, 1 bilan 2, keyin 3 bilan 4 ...) va agar birinchisi ikkinchisidan keyin kelishi kerak bo'lsa, ularni almashtirish. Keyinchalik, natijada olingan ikkita ro'yxatning har birini to'rtta ro'yxatga birlashtiradi, so'ngra to'rtta ro'yxatni birlashtiradi va hokazo; oxirgi ikki ro'yxat yakuniy saralangan ro'yxatga birlashtirilguncha.^[24] Bu erda tavsiflangan algoritmlardan biri bu juda katta ro'yxatlarning o'lchovidir, chunki uning eng yomon ish vaqti O (n jurnal n). Bundan tashqari, u nafaqat massivlarga, balki ro'yxatlarga ham osonlikcha qo'llaniladi, chunki u tasodifiy kirishni emas, balki ketma-ket kirishni talab qiladi. Biroq, u qo'shimcha O (n) kosmik murakkablik va oddiy dasturlarda juda ko'p nusxalarni o'z ichiga oladi.
Birlashtirish navi murakkab algoritmda ishlatilganligi sababli amaliy qo'llanmalar uchun nisbatan yaqinda ommalashgan Timsort, bu dasturlash tillarida standart tartib uchun ishlatiladi Python^[25] va Java (sifatida JDK7^[26]). Birlashtirish tartibining o'zi odatdagi tartibdir Perl,^[27] boshqalar qatorida va kamida 2000 yildan beri Java-da ishlatilgan JDK1.3.^[28]
Heapsort
Asosiy maqola: Heapsort
Heapsort ning ancha samarali versiyasidir tanlov saralash. Shuningdek, u ro'yxatning eng katta (yoki eng kichik) elementini aniqlab, ro'yxatning oxiriga (yoki boshiga) qo'yib, so'ngra ro'yxatning qolgan qismida davom etish orqali ishlaydi, ammo bu vazifani a deb nomlangan ma'lumotlar tuzilishi yordamida samarali bajaradi. uyum, maxsus turi ikkilik daraxt.^[29] Ma'lumotlar ro'yxati uyumga aylantirilgandan so'ng, ildiz tuguni eng katta (yoki eng kichik) element bo'lishiga kafolat beradi. U olib tashlanib, ro'yxatning oxiriga qo'yilganda, uyum qayta tartibga solinadi, shunda qolgan eng katta element ildizga o'tadi. To'pni ishlatib, keyingi eng katta elementni topish O (log) ni oladi n) O, o'rniga vaqt (n) oddiy tanlov tartibidagi kabi chiziqli skanerlash uchun. Bu Heapsort-ga O (n jurnal n) vaqt, va bu ham eng yomon murakkablik.