Merge sort va Quick sort
Oldingi qismda bubble, selection va insertion sortni ko'rib chiqdik. Uchalasi ham O(n²) vaqt murakkabligiga ega — ya'ni massiv hajmi ikki barobar oshsa, bajariladigan ish taxminan to'rt barobar ko'payadi. Ming elementli massiv uchun bu chidasa bo'ladi, lekin million elementli massivda O(n²) algoritm amalda ishlamay qoladi.
Muammo qayerda? Uchala algoritm ham har bir elementni qolgan deyarli barcha elementlar bilan taqqoslaydi. Agar massivni kichikroq bo'laklarga ajratib, har bo'lakni alohida saralab, keyin natijalarni aqlli tarzda birlashtirsak-chi? Aynan shu g'oya merge sort va quick sort algoritmlarining negizida yotadi. Ikkalasi ham rekursiya orqali ishlaydi va O(n log n) o'rtacha vaqt beradi — bu amaliy dasturlarda ishlatiladigan saralash algoritmlarining asosidir.
Note
Bu maqola rekursiya g'oyasiga tayanadi. Agar tayanch holat, rekursiv chaqiruv va call stack tushunchalari notanish bo'lsa, avval Rekursiya mavzusini ko'rib chiqish tavsiya etiladi.
Bo'lib yechish g'oyasi
Ikkala algoritm ham bo'lib yechish (divide and conquer) strategiyasiga asoslanadi: muammoni kichikroq mustaqil qismlarga bo'lish, har birini alohida yechish va natijalarni birlashtirish. Farq shu qismlarni qanday hosil qilish va qachon "asosiy ish" bajarilishida.
Katta bir kitob to'plamini betartib holda tasavvur qiling. Uni yakka o'zingiz tartiblashning ikki yo'li bor. Birinchisi — to'plamni ikkiga bo'lib, ikkala yarmini alohida odamlarga berib saralatish, keyin ikkita saralangan uyumni birlashtirish. Bu merge sortning mantig'i: avval bo'l, keyin birlashtirganda tartibla.
Ikkinchi yo'l — bitta kitobni "mezon" qilib tanlash, undan kichik nomdagi kitoblarni chapga, kattasini o'ngga ajratish. Shundan keyin chap va o'ng uyumlarning har biri bilan xuddi shu ishni takrorlash. Bu quick sortning mantig'i: avval tartibla (mezon atrofida), keyin bo'l.
Ikkala yondashuv ham massivni kichraytirib boradi va oxir-oqibat bitta yoki nol elementli bo'lakka yetadi — bu rekursiyaning tayanch holati.
Merge sort
Asosiy g'oya
Merge sort massivni doimo teng ikkiga bo'ladi, har yarmini rekursiv saralaydi, so'ng ikkita saralangan yarmni bitta saralangan massivga birlashtiradi. Butun algoritmning og'irligi aslida birlashtirish bosqichida — chunki bo'lishning o'zi hech qanday taqqoslash talab qilmaydi, faqat massivni ikkiga ajratadi.
FUNCTION merge_sort(array)
IF array uzunligi <= 1
RETURN array
middle = array uzunligi / 2
chap = merge_sort(array[0 : middle])
ong = merge_sort(array[middle : oxiri])
RETURN merge(chap, ong)
Tayanch holat — uzunligi 0 yoki 1 bo'lgan massiv. Bunday massiv allaqachon saralangan hisoblanadi, chunki uni tartibga solish uchun hech narsa qilish shart emas.
Birlashtirish (merge) qanday ishlaydi
merge funksiyasi ikkita alohida saralangan massivni oladi va ularni bitta saralangan massivga birlashtiradi. G'oya sodda: ikkala massivning boshidan ko'rsatkich yuritib, har safar kichikroq elementni natija massiviga qo'shib boriladi.
FUNCTION merge(chap, ong)
natija = bo'sh massiv
i = 0
j = 0
WHILE i < chap uzunligi VA j < ong uzunligi
IF chap[i] <= ong[j]
natija ga chap[i] qo'sh
i = i + 1
ELSE
natija ga ong[j] qo'sh
j = j + 1
// Bitta massivda elementlar tugagach, qolganini to'g'ridan-to'g'ri ko'chirish
WHILE i < chap uzunligi
natija ga chap[i] qo'sh
i = i + 1
WHILE j < ong uzunligi
natija ga ong[j] qo'sh
j = j + 1
RETURN natija
chap[i] <= ong[j] shartida teng bo'lganda chap massivdan olish tasodifiy emas — bu tanlov merge sortni barqaror (stable) qiladi: teng qiymatli elementlarning asl tartibi saqlanadi.
Bosqichma-bosqich tahlil
[8, 3, 5, 1, 9, 2] massivini saralaylik.
Bo'lish bosqichi — massiv rekursiv ravishda yarimlanadi:
[8, 3, 5, 1, 9, 2]
|
/-------\
[8, 3, 5] [1, 9, 2]
| |
/---\ /---\
[8,3] [5] [1,9] [2]
| |
/---\ /---\
[8] [3] [1] [9]
Har bir bo'linish tayanch holatga — bitta elementli massivga — yetguncha davom etadi.
Birlashtirish bosqichi — endi natijalar pastdan yuqoriga qarab yig'iladi:
[8] va [3] → [3, 8]
[1] va [9] → [1, 9]
[3, 8] va [5] → [3, 5, 8]
[1, 9] va [2] → [1, 2, 9]
[3, 5, 8] va [1, 2, 9] → [1, 2, 3, 5, 8, 9]
Diqqat qiling: birlashtirish bosqichida hech qachon "orqaga qaytib" qayta tartiblashga hojat yo'q — chunki birlashtirilayotgan ikkala tomon allaqachon o'z ichida saralangan.
Nima uchun O(n log n)?
Bu savolga javob berish uchun ikki narsani hisoblash kerak: necha daraja (level) bo'lish sodir bo'ladi va har darajada jami qancha ish bajariladi.
Massiv har safar ikkiga bo'linadi. n elementli massiv 1 elementgacha necha marta ikkiga bo'linishi mumkinligi — bu aynan log₂n savoli. Demak, rekursiya daraxtining balandligi O(log n).
Har bir darajada, bo'laklar soni ko'p bo'lsa-da, ularning umumiy uzunligi doim n ga teng — chunki bo'laklar asl massivni to'liq qoplaydi. Birlashtirish operatsiyasi o'zi qo'shilayotgan elementlar soniga chiziqli bog'liq, shuning uchun har bir darajada jami O(n) ish bajariladi.
O(log n) daraja, har darajada O(n) ish — natija O(n · log n). Bu rekursiv formula ko'rinishida:
Bu formulani Rekursiya mavzusidagi "Har darajada chiziqli ish" bo'limida batafsilroq ko'rgan edik.
Xotira murakkabligi
Merge sort odatda O(n) qo'shimcha xotira talab qiladi. Buning sababi — merge funksiyasi natijani yangi massivga yozadi, mavjud massiv ustida joyida (in-place) ishlamaydi. Har darajada yangi vaqtinchalik massivlar yaratiladi, lekin ular birlashtirilgach ishlatilmay qoladi; klassik implementatsiyada bir vaqtning o'zida saqlanadigan qo'shimcha xotira O(n) darajasida qoladi.
Bundan tashqari, rekursiv chaqiruvlar O(log n) chuqurlikdagi call stack xotirasini ham talab qiladi. Lekin bu O(n) yordamchi massiv xotirasi oldida kichikroq hissa.
Warning
Merge sortni "joyida" (qo'shimcha O(1) xotira bilan) amalga oshirish nazariy jihatdan mumkin, lekin bunday variantlar ancha murakkab va sekinroq bo'ladi. Amaliyotdagi ko'pchilik implementatsiya O(n) qo'shimcha xotiraga tayanadi.
Merge sortning xususiyatlari
| Xususiyat | Qiymat | Izoh |
|---|---|---|
| Eng yaxshi holat | O(n log n) |
Kirish tartibiga bog'liq emas |
| O'rtacha holat | O(n log n) |
|
| Eng yomon holat | O(n log n) |
Har doim bir xil — bu muhim afzallik |
| Xotira murakkabligi | O(n) |
Birlashtirish uchun qo'shimcha massiv |
| Barqarorlik | Barqaror | Teng elementlar tartibi saqlanadi |
| Joyida ishlashi | Yo'q (klassik variantda) | Qo'shimcha massiv talab qiladi |
Merge sortning eng katta afzalligi shu — uning eng yomon holati ham O(n log n). Kirish massivi qanday tartibda bo'lishidan qat'i nazar, ishlash vaqti deyarli bir xil qoladi. Bu uni katta va bashorat qilib bo'lmaydigan ma'lumotlar uchun ishonchli tanlov qiladi.
Quick sort
Asosiy g'oya
Quick sort merge sortdan farqli o'laroq, "avval bo'l, keyin birlashtirganda tartibla" emas, balki "avval tartibla (qisman), keyin bo'l" tamoyiliga asoslanadi. Bu jarayonning markazida pivot — massivdan tanlab olinadigan bitta element — turadi.
Algoritm massivni pivot atrofida shunday qayta joylashtiradiki, pivotdan kichik barcha elementlar uning chap tomonida, katta yoki teng elementlar o'ng tomonida joylashadi. Bu jarayon partitsiyalash (partition) deyiladi. Partitsiyalashdan keyin pivot aynan o'z yakuniy o'rnida turadi — uni boshqa hech qachon siljitish shart emas. Shundan so'ng chap va o'ng qismlar mustaqil ravishda xuddi shu tarzda rekursiv saralanadi.
FUNCTION quick_sort(array, past, oxiri)
IF past < oxiri
pivot_index = partition(array, past, oxiri)
quick_sort(array, past, pivot_index - 1)
quick_sort(array, pivot_index + 1, oxiri)
Tayanch holat — past >= oxiri bo'lgan holat, ya'ni bo'lak bitta yoki nol elementdan iborat.
Partitsiyalash qanday ishlaydi
Eng ko'p ishlatiladigan variantlardan biri — oxirgi elementni pivot sifatida tanlash (Lomuto sxemasi):
FUNCTION partition(array, past, oxiri)
pivot = array[oxiri]
i = past - 1 // kichik elementlar chegarasi
FOR j = past DAN oxiri - 1 GACHA
IF array[j] < pivot
i = i + 1
array[i] VA array[j] JOYINI ALMASHTIR
array[i + 1] VA array[oxiri] JOYINI ALMASHTIR
RETURN i + 1
i o'zgaruvchisi "hozirgacha pivotdan kichik topilgan elementlar chegarasi"ni belgilaydi. j massiv bo'ylab yuradi: pivotdan kichik element topilsa, u i chegarasi ichiga almashtiriladi. Aylanish tugagach, pivot i + 1 pozitsiyaga qo'yiladi — bu uning yakuniy, to'g'ri o'rni.
Bosqichma-bosqich tahlil
[7, 2, 1, 6, 8, 5, 3] massivini saralaylik. Pivot sifatida oxirgi element — 3 — tanlanadi.
[7, 2, 1, 6, 8, 5, 3] pivot = 3, i = -1
j=0: 7 < 3? Yo'q
j=1: 2 < 3? Ha → i=0, array[0] va array[1] almashadi
[2, 7, 1, 6, 8, 5, 3]
j=2: 1 < 3? Ha → i=1, array[1] va array[2] almashadi
[2, 1, 7, 6, 8, 5, 3]
j=3: 6 < 3? Yo'q
j=4: 8 < 3? Yo'q
j=5: 5 < 3? Yo'q
Aylanish tugadi. Pivotni i+1=2 o'ringa qo'yamiz:
array[2] va array[6] almashadi
[2, 1, 3, 6, 8, 5, 7]
↑
pivot o'z joyida
Endi 3dan chapda faqat undan kichik elementlar (2, 1), o'ngida faqat undan katta elementlar (6, 8, 5, 7) turibdi. Ikkala tomon endi mustaqil ravishda xuddi shu jarayondan o'tadi — bu rekursiv qadam.
Nima uchun pivot tanlovi muhim?
Quick sortning tezligi to'g'ridan-to'g'ri pivot massivni qanchalik "teng" ikkiga bo'lishiga bog'liq.
Agar pivot har safar massivni taxminan teng ikkiga bo'lsa, rekursiya daraxti merge sortga o'xshab O(log n) chuqurlikda bo'ladi, har darajada O(n) ish (partitsiyalash) bajariladi — natija O(n log n).
Agar massiv allaqachon saralangan bo'lib, pivot sifatida doim oxirgi (eng katta) element tanlansa, partitsiyalash har safar bitta tomonni bo'sh, ikkinchisini n - 1 elementli qilib qoldiradi:
Bu holda rekursiya daraxtining chuqurligi O(n) bo'lib qoladi, har darajada O(n) ish bajariladi — umumiy vaqt O(n²) ga tushib qoladi. Bu — quick sortning eng yomon holati.
T(n) = T(n - 1) + O(n) → eng yomon holat, O(n²)
T(n) = 2T(n/2) + O(n) → muvozanatli holat, O(n log n)
Shu sababli amaliy implementatsiyalarda pivotni tasodifiy tanlash yoki "medianani uchtadan tanlash" (birinchi, o'rta va oxirgi elementlar orasidan mediananini olish) kabi strategiyalar qo'llaniladi. Bu eng yomon holatni yo'qotmaydi, lekin uni juda kam ehtimolli qiladi.
Quick sortning xususiyatlari
| Xususiyat | Qiymat | Izoh |
|---|---|---|
| Eng yaxshi holat | O(n log n) |
Pivot har safar massivni taxminan teng bo'lganda |
| O'rtacha holat | O(n log n) |
Tasodifiy kirishda amalda kuzatiladi |
| Eng yomon holat | O(n²) |
Pivot doim eng kichik yoki eng katta bo'lganda |
| Xotira murakkabligi | O(log n) o'rtacha |
Faqat rekursiya call stacki, qo'shimcha massiv yo'q |
| Barqarorlik | Barqaror emas | Almashtirishlar teng elementlar tartibini buzishi mumkin |
| Joyida ishlashi | Ha | Massiv o'zining ichida qayta joylashtiriladi |
Quick sort joyida (in-place) ishlaydi — merge sortdagidek qo'shimcha O(n) massiv kerak emas, faqat almashtirish amallari bajariladi. Aynan shu sababli amaliyotda ko'pincha merge sortdan tezroq ishlaydi, garchi nazariy eng yomon holati yomonroq bo'lsa ham.
Warning
Quick sortning O(log n) xotira ko'rsatkichi rekursiya muvozanatli bo'lgan holatga tegishli. Eng yomon holatda (doimo noteng bo'linish) rekursiya chuqurligi O(n) ga yetib, katta massivlarda stack overflow xavfini tug'diradi.
Merge sort va quick sortni taqqoslash
| Mezon | Merge sort | Quick sort |
|---|---|---|
| Eng yomon vaqt | O(n log n) |
O(n²) |
| O'rtacha vaqt | O(n log n) |
O(n log n) |
| Qo'shimcha xotira | O(n) |
O(log n) o'rtacha |
| Barqarorlik | Barqaror | Odatda barqaror emas |
| Joyida ishlashi | Yo'q | Ha |
| Amaliy tezlik | Yaxshi va barqaror | Ko'pincha tezroq, lekin kafolatsiz |
| Katta fayllar / tashqi xotira | Qulay (ketma-ket o'qish) | Noqulay |
Ikkalasi ham O(n log n) "kutilgan" toifaga kiradi, lekin ularning kafolatlari boshqacha. Merge sort — kafolatlangan O(n log n), narxi qo'shimcha xotira. Quick sort — odatda tezroq va xotira tejamkor, narxi noyob holatlarda O(n²)ga tushib qolish xavfi.
Real qo'llanishlar
Dasturlash tillarining standart saralash funksiyalari ko'pincha bu ikki algoritmning gibrid variantlaridan foydalanadi. Masalan, ko'p tillar kichik bo'laklar uchun insertion sortga, katta massivlar uchun quick sort yoki merge sortga o'tadigan gibrid algoritm ishlatadi — chunki kichik massivda O(n²) algoritmning doimiy koeffitsienti kichik bo'lib, amalda tezroq ishlaydi.
Tashqi saralash (external sorting) — massiv xotiraga sig'maydigan darajada katta bo'lganda (masalan, disk yoki tarmoqdan o'qiladigan gigabaytlab ma'lumot), merge sort ustunlik qiladi. Sababi — merge bosqichi ma'lumotni ketma-ket o'qiydi, disk bilan ishlashda tasodifiy kirishdan ancha arzon.
Barqarorlik talab qilinganda — masalan, buyurtmalar ro'yxatini avval sana, keyin narx bo'yicha saralash kerak bo'lsa, ikkinchi saralash birinchisining natijasini buzmasligi kerak. Bunda merge sortning barqarorligi muhim ahamiyat kasb etadi.
Tezlik ustuvor bo'lgan umumiy holatlarda — xotiradagi oddiy massivlarni saralashda, barqarorlik shart bo'lmasa, quick sort odatda tezroq amaliy natija beradi, chunki u joyida ishlaydi va qo'shimcha massiv ajratmaydi.
Keng tarqalgan xatolar
Merge funksiyasida chegarani noto'g'ri hisoblash
middle indeksini hisoblashda yoki bo'laklarni kesishda bitta elementni ikki marta kiritish yoki umuman tashlab ketish oson xato. Har bir bo'linishdan keyin ikkala bo'lak yig'indisi asl massiv uzunligiga teng ekanini tekshirish foydali.
Partitsiyalashda pivotni almashtirishni unutish
Lomuto sxemasida aylanish tugagach array[i + 1] bilan array[oxiri]ni almashtirish shart. Bu qadam tashlab ketilsa, pivot hech qachon o'z to'g'ri joyiga tushmaydi.
Rekursiya chegaralarini noto'g'ri uzatish
Quick sortda quick_sort(array, past, pivot_index - 1) va quick_sort(array, pivot_index + 1, oxiri) chaqiruvlarida pivot indeksini qayta kiritib yuborish cheksiz rekursiyaga yoki noto'g'ri natijaga olib keladi. Pivot allaqachon o'z joyida turgani uchun uni keyingi rekursiv chaqiruvlarga kiritish shart emas.
Eng yomon holatni e'tiborsiz qoldirish
Har doim birinchi yoki oxirgi elementni pivot qilib tanlash, saralangan yoki deyarli saralangan kirishlarda quick sortni O(n²)ga tushirib qo'yadi. Tasodifiy yoki median-based pivot tanlash bu xavfni kamaytiradi.
Merge sortni "joyida" deb noto'g'ri hisoblash
Merge sort massivni o'zgartiradi, lekin bu jarayon vaqtinchalik qo'shimcha massivlar orqali bajariladi. Uni bubble yoki selection sort kabi O(1) qo'shimcha xotirali deb hisoblash xato.
Qachon merge sort, qachon quick sort tanlash kerak?
- Barqarorlik kerak bo'lsa — merge sort tanlanadi.
- Eng yomon holatda ham kafolatlangan
O(n log n)kerak bo'lsa (masalan, real-time tizimlarda) — merge sort xavfsizroq. - Xotira cheklangan va tezlik muhim bo'lsa — quick sort odatda ustun, chunki u joyida ishlaydi.
- Ma'lumot diskdan yoki tarmoqdan ketma-ket o'qilsa — merge sortning ketma-ket kirish xususiyati qulayroq.
- Kirish massivi tez-tez saralangan yoki deyarli saralangan bo'lishi kutilsa — oddiy quick sort xavfli, tasodifiy pivotli variant yoki merge sort afzalroq.
Ikkala algoritm ham O(n²) algoritmlar ustidan sifat sakrashini ko'rsatadi, lekin "eng yaxshisi" degan yagona javob yo'q — tanlov ma'lumot xususiyatlari va tizim talablariga bog'liq.
Eng muhim xulosa
Merge sort va quick sort ikkalasi ham bo'lib yechish strategiyasiga tayanadi, lekin ishni turli tartibda bajaradi: merge sort avval bo'ladi va birlashtirganda tartiblaydi, quick sort esa avval qisman tartiblaydi (pivot atrofida) va keyin bo'ladi. Shu farq ularning xotira profili, barqarorligi va eng yomon holat xatti-harakatidagi tafovutni keltirib chiqaradi.
Ikkalasining ham asosida rekursiya yotadi — massiv har safar kichikroq bo'lakka bo'linadi, tayanch holatga (bitta yoki nol elementli massiv) yetgach, natijalar pastdan yuqoriga qarab yig'iladi. Rekursiya daraxtining chuqurligi va har darajadagi ish miqdorini tushunish — bu algoritmlarning nima uchun O(n log n) (yoki quick sortda O(n²)) ekanini tushunishning kaliti.
Keyingi qismda rekursiya g'oyasini amaliy masalalar orqali mustahkamlaymiz: son darajaga ko'tarish, ikki saralangan massivni birlashtirish va massivdagi k-chi eng katta elementni topish.