Mavzu: murakkab saralash algortmlari juda ham katta sonlar bilan ishlash

Keling, Merge Sort texnikasining rasmini ko'raylik.

Yuqoridagi rasmda, birlashtirish tartiblash texnikasi har bir pastki chiziqda bitta element mavjud bo'lmaguncha, dastlabki massivni subarrayslarga qayta-qayta ajratib qo'yganini ko'ramiz. Bu amalga oshirilgandan so'ng, subarrayslar mustaqil ravishda saralanadi va to'liq tartiblangan qatorni yaratish uchun birlashtiriladi.
Shell sort (Qobiqsimon saralash)- bu qo'shishni saralash texnikasining kengaytmasi. Indertion sort-da, biz faqat keyingi element bilan shug'ullanamiz, holbuki qobiq tartibida biz ota-onalar ro'yxatidan kichikroq ro'yxatlar yaratib, o'sish yoki bo'shliqni ta'minlaymiz. Ichki ro'yxatdagi elementlar bir-biriga zid bo'lmasligi kerak, aksincha ular bir-biridan farq qiladigan "gap_value" dir.
Shell sort qo'shilish tartibiga qaraganda tezroq bajariladi va qo'shilish turiga qaraganda kamroq harakatlarni talab qiladi.

Agar biz bo'shliqni ta'minlasak, unda har bir element 3 ta alohida bo'lgan quyidagi quyi ro'yxatlarga ega bo'lamiz.
Keyin ushbu uchta pastki ro'yxatni saralaymiz.

Tarkiblangan sub-massivlarni birlashtirgandan so'ng biz yuqoridagi qator deyarli tartiblangan. Endi biz massivni tartiblash uchun ushbu massivda joylashtirish tartibini amalga oshirishimiz mumkin.
Shunday qilib, biz tegishli kattalashtirish yordamida massivni pastki ro'yxatlarga ajratamiz va keyin ularni birlashtirsak, deyarli saralangan ro'yxatni olamiz. Ushbu ro'yxatdagi qo'shishni tartiblash usuli bajarilishi mumkin va qator asl qo'shib qo'yish turiga qaraganda kamroq harakatda tartiblangan.
Qisqichbaqasimon tartib qo'shib qo'yish tartibida juda katta yaxshilanish vazifasini bajaradi va qatorni tartiblash uchun hatto qadamlarning yarmini ham bajarmaydi.
9.Heapsort (To’plab saralash)
Heapsort - bu ro'yxat tartibida to'plash uchun ma'lumotlarning tuzilishi (min-evap yoki max-heap) ishlatiladigan usul. Dastlab biz tartiblanmagan ro'yxatdagi uyumni yaratamiz va shuningdek, qatorni tartiblash uchun to'plardan foydalanamiz.
Heapsort samarali, ammo tez emas yoki birlashtirish.

Yuqoridagi rasmda ko'rsatilgandek, avval saralanadigan massiv elementlaridan maksimal darajada uyum hosil qilamiz. Keyin biz to'pni kesib, oxirgi va birinchi elementni almashtiramiz. Hozirgi vaqtda oxirgi element allaqachon saralangan. Keyin biz yana qolgan elementlardan maksimal uyumni quramiz.
To'pni yana kesib o'ting va birinchi va oxirgi elementlarni almashtiring va saralangan ro'yxatga oxirgi elementni qo'shing. Bu jarayon uyada saralangan ro'yxatning birinchi elementiga aylanadigan bitta element qolmaguncha davom etadi.
Hozirgacha biz barcha asosiy tartiblash usullarini qisqacha muhokama qildik. Biz ushbu usullarning har birini keyingi darsliklarimizda batafsil o'rganamiz va har bir texnikani tushunish uchun turli xil misollar keltiramiz.

10. Large number sort(Katta sonlarni saralash)

Algoritm g’oyasi: Katta sonlarni satr kurinishida olib uzunligi bo’yicha saralanadi,agar uzinlig teng bo’lsa taqqoslanadi.

Izox: Vaqtning murakkabligi: O (k * n log n), bu erda k - eng uzun raqamning uzunligi. Bu erda sort () funktsiyasi O (n Log n) saralash algoritmidan foydalaniladi.