K-chi eng katta element
Sinfda 30 ta o‘quvchining test balli bor va sizga “uchinchi eng yuqori ball qancha?” deb so‘rashadi. Buning eng oson yo‘li — barcha ballarni kamayish tartibida saralab, uchinchi o‘ringa qarash. Lekin agar sizga faqat bitta savolga javob kerak bo‘lsa — nega butun ro‘yxatni saralashga vaqt sarflash kerak? Aynan shu savol bu masalaning markazida turadi: massivni to‘liq saralamasdan, undagi k-chi eng katta elementni qanday tezroq topish mumkin.
Masala
Saralanmagan massiv va k soni berilgan. Massivdagi k-chi eng katta elementni toping (eng katta element 1-chi hisoblanadi, ikkinchi eng katta — 2-chi, va hokazo).
KIRISH: array = [3, 2, 1, 5, 6, 4], k = 2
NATIJA: 5
(saralansa: [6, 5, 4, 3, 2, 1] — 2-chi eng katta 5)
KIRISH: array = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
NATIJA: 4
Diqqat qiling: “k-chi eng katta” — bu “k-chi noyob eng katta” degani emas. Takroriy qiymatlar alohida-alohida hisoblanadi.
Naiv yechim: to‘liq saralash
Eng ochiq yo‘l — massivni kamayish tartibida saralash va k - 1 indeksdagi elementni olish:
FUNCTION KTH_LARGEST_NAIVE(array, k)
saralangan = array ni kamayish tartibida sarala
RETURN saralangan[k - 1]
Bu yechim to‘g‘ri, lekin ortiqcha ish qiladi. Bizga faqat bitta elementning to‘g‘ri o‘rni kerak, holbuki merge sort yoki quick sort yordamida saralash butun massivni to‘liq tartiblaydi — bu O(n log n) vaqt talab qiladi.
Yaxshiroq g‘oya: quickselect
Quick sort mavzusida ko‘rgan partitsiyalash (partition) operatsiyasini eslang: u massivni pivot atrofida qayta joylashtiradi va pivotni o‘zining yakuniy, to‘g‘ri o‘rniga qo‘yadi. Muhim kuzatuv shuki — partitsiyalashdan so‘ng biz pivotning aniq qaysi indeksda turishini bilamiz.
Quick sort partitsiyalashdan keyin ikkala tomonni ham rekursiv saralaydi. Lekin bizga faqat bitta indeksdagi element kerak — demak, pivot izlanayotgan indeksdan chapda yoki o‘ngda ekanligiga qarab, faqat bitta tomonni davom ettirish kifoya. Ikkinchi tomonni butunlay tashlab yuborish mumkin. Bu yondashuv quickselect deb ataladi.
G‘oyani indeksga o‘tkazish
“K-chi eng katta” tushunchasini ishlatish qulayroq bo‘lishi uchun uni o‘sish tartibida saralangan massivdagi indeksga aylantiramiz. n elementli massivda k-chi eng katta element, o‘sish tartibida saralanganda, n - k indeksda turadi:
array = [3, 2, 1, 5, 6, 4], n = 6, k = 2
o‘sish tartibida: [1, 2, 3, 4, 5, 6]
↑
indeks n - k = 4 → qiymat 5
Demak, masala “o‘sish tartibida saralanganda n - k indeksda qanday qiymat turadi?” degan savolga aylanadi.
Algoritm
FUNCTION QUICKSELECT(array, past, oxiri, target_index)
IF past = oxiri
RETURN array[past]
pivot_index = PARTITION(array, past, oxiri)
IF pivot_index = target_index
RETURN array[pivot_index]
IF target_index < pivot_index
RETURN QUICKSELECT(array, past, pivot_index - 1, target_index)
RETURN QUICKSELECT(array, pivot_index + 1, oxiri, target_index)
PARTITION funksiyasi — Merge sort va Quick sort maqolasidagi bilan bir xil. Farq shu — bu yerda partitsiyalashdan keyin faqat bitta rekursiv chaqiruv bo‘ladi, ikkalasi emas.
FUNCTION KTH_LARGEST(array, k)
n = array uzunligi
target_index = n - k
RETURN QUICKSELECT(array, 0, n - 1, target_index)
Bosqichma-bosqich tahlil
array = [3, 2, 1, 5, 6, 4], k = 2 bo‘lsin. n = 6, demak target_index = 6 - 2 = 4.
Pivot sifatida har doim oxirgi elementni tanlaymiz (Lomuto sxemasi).
1-chaqiruv: QUICKSELECT(array, 0, 5, 4), pivot = 4
target_index (4) > pivot_index (3) — demak, faqat o‘ng tomonni davom ettiramiz: QUICKSELECT(array, 4, 5, 4).
2-chaqiruv: QUICKSELECT(array, 4, 5, 4), pivot = 5
target_index (4) = pivot_index (4) — topildi! array[4] = 5 qaytariladi.
Natija — 5, xuddi kutilganidek. E’tibor bering: chap tomondagi [3, 2, 1, 4] qismi hech qachon qayta ko‘rilmadi — biz faqat kerakli tomonni davom ettirdik.
Nima uchun bu tezroq?
Quick sortda har ikkala tomon ham rekursiv davom etadi, shuning uchun umumiy ish T(n) = 2T(n/2) + O(n), ya’ni O(n log n). Quickselectda esa faqat bitta tomon davom etadi:
Bu yerda rekursiya daraxti chiziqli emas, lekin har darajada ish miqdori yarmiga kamayib boradi:
1-daraja: n ta element ustida ish → O(n)
2-daraja: n/2 ta element ustida ish → O(n/2)
3-daraja: n/4 ta element ustida ish → O(n/4)
...
Bu geometrik qatorning yig‘indisi O(n) + O(n/2) + O(n/4) + ... ≈ O(2n) = O(n) ga teng — chunki har hadning yig‘indisi asosiy hadning ikki barobaridan oshmaydi. Shu sababli quickselectning o‘rtacha vaqt murakkabligi O(n) — bu to‘liq saralashning O(n log n)idan tezroq.
Warning
Bu natija pivot massivni har safar taxminan teng ikkiga bo‘lgan holatga tegishli. Quick sort maqolasida ko‘rilganidek, agar pivot doim eng kichik yoki eng katta element bo‘lib chiqsa (masalan, saralangan massivda doim oxirgi elementni tanlash), har chaqiruv massivni faqat bitta elementga kamaytiradi va eng yomon holatda vaqt murakkabligi O(n²) ga tushib qoladi.
Murakkablik jadvali
| Yondashuv | O‘rtacha vaqt | Eng yomon vaqt | Xotira |
|---|---|---|---|
| To‘liq saralash | O(n log n) |
O(n log n) |
O(n) yoki O(log n) (algoritmga bog‘liq) |
| Quickselect | O(n) |
O(n²) |
O(log n) o‘rtacha (call stack) |
Min-heap (k o‘lchamli) |
O(n log k) |
O(n log k) |
O(k) |
Quickselect eng yomon holatda saralashdan yomonroq bo‘lishi mumkin, lekin amaliyotda — ayniqsa pivot tasodifiy tanlansa — o‘rtacha holatdagi O(n) juda ishonchli natija beradi. Agar eng yomon holatni ham kafolatlash kerak bo‘lsa (masalan, real-time tizimda), o‘lchami k bo‘lgan min-heap yondashuvi barqarorroq tanlov, chunki uning eng yomon holati ham o‘rtachasi bilan bir xil.
Pivot tanlovining ahamiyati
Xuddi quick sortdagidek, pivotni doim birinchi yoki oxirgi element qilib tanlash — massiv allaqachon saralangan yoki deyarli saralangan bo‘lganda eng yomon holatga olib keladi. Amaliy implementatsiyalarda pivotni tasodifiy tanlash keng qo‘llaniladi:
FUNCTION PARTITION_RANDOM(array, past, oxiri)
tasodifiy_index = past DAN oxiri GACHA tasodifiy son
array[tasodifiy_index] VA array[oxiri] JOYINI ALMASHTIR
RETURN PARTITION(array, past, oxiri) // qolgani odatdagidek
Bu o‘zgarish eng yomon holatni yo‘qotmaydi, lekin uni deyarli imkonsiz darajada kam ehtimolli qiladi — chunki noqulay kirish massivi tasodifiy tanlangan pivotga moslashib qololmaydi.
Edge case’lar
k = 1
Bu holatda massivdagi eng katta elementni topish so‘ralmoqda. target_index = n - 1, ya’ni massivning oxirgi indeksi (o‘sish tartibida saralanganda). Algoritm bu holatni alohida shartsiz to‘g‘ri hisoblaydi.
k = n
Bu — massivdagi eng kichik elementni topish bilan bir xil. target_index = 0.
k massiv uzunligidan katta yoki nolga teng
k <= 0 yoki k > n bo‘lsa, savolning o‘zi ma’nosiz — massivda shuncha element yo‘q. Bu holat funksiyaga kirishdan oldin tekshirilishi va aniq xato sifatida qaytarilishi kerak, aks holda target_index massiv chegarasidan tashqariga chiqib ketadi.
Takroriy qiymatlar
array = [5, 5, 5, 5], k = 2 bo‘lsa, natija baribir 5 bo‘lishi kerak — chunki har bir nusxa alohida element sifatida hisoblanadi. Partitsiyalash algoritmi (< va >= solishtiruvlari) buni to‘g‘ri boshqaradi, lekin buni loyihalashda “k-chi noyob qiymat” bilan “k-chi element” tushunchalarini aralashtirmaslik kerak — bu ikkita boshqa-boshqa masala.
Bo‘sh massiv
Bo‘sh massivda hech qanday k uchun javob yo‘q. Bu holat ham kirish tekshiruvida alohida ko‘rib chiqilishi kerak.
Real qo‘llanish
Top-N tavsiyalar va reytinglar. Onlayn-do‘kon “eng ko‘p sotilgan 10 ta mahsulot”ni ko‘rsatishi kerak bo‘lganda, millionlab mahsulotni to‘liq saralashning hojati yo‘q — faqat yuqori N ta kerak. Quickselectga o‘xshash yondashuvlar (yoki min-heap) bunday holatlarda saralashdan tezroq ishlaydi.
Statistik medianani topish. Massivning medianasi — bu aslida k = n/2 bo‘lgan xususiy holat. Katta ma’lumotlar to‘plamida medianani tezkor topish uchun aynan shu texnika ishlatiladi.
Ma’lumotlar bazasida LIMIT va ORDER BY birga kelganda. “Eng qimmat 5 ta mahsulotni ko‘rsat” so‘rovi bajarilganda, ba’zi bazalar butun jadvalni saralash o‘rniga shunga o‘xshash tanlash strategiyalaridan foydalanadi, ayniqsa natija hajmi jadval hajmidan ancha kichik bo‘lganda.
Keng tarqalgan xatolar
kni to‘g‘ridan-to‘g‘ri indeks sifatida ishlatish
k-chi eng katta va k-indeksdagi element bir xil narsa emas. target_index = n - k formulasini unutish yoki uni noto‘g‘ri hisoblash noto‘g‘ri elementni qaytarishga olib keladi.
Ikkala tomonni ham rekursiv davom ettirish
Bu xato quickselectni oddiy quick sortga aylantirib qo‘yadi — natija baribir to‘g‘ri chiqadi, lekin O(n) o‘rtacha vaqt afzalligi yo‘qoladi, chunki butun massiv saralanib chiqadi.
Pivot indeksini target bilan solishtirmaslik
Har safar faqat bitta tomonni tanlab davom ettirish yetarli emas — avval pivot_indexni target_index bilan solishtirib, agar ular teng bo‘lsa, natija allaqachon topilganini aniqlash kerak. Aks holda algoritm keraksiz chaqiruvlar qilishda davom etadi yoki hatto noto‘g‘ri tomonni tanlab qo‘yishi mumkin.
Har doim bir xil pivotni tanlash
Doimo birinchi yoki oxirgi elementni pivot qilib tanlash — saralangan yoki maxsus tuzilgan kirishlarda O(n²) eng yomon holatga olib kelishi mumkin. Tasodifiy pivot tanlash bu xavfni sezilarli darajada kamaytiradi.
Eng muhim xulosa
K-chi eng katta elementni topish masalasi shuni ko‘rsatadiki, ba’zida to‘liq javobni (butun saralangan massivni) topish shart emas — faqat javobning bir qismi kerak bo‘lsa, algoritmni shunga moslab qisqartirish mumkin. Quickselect aynan shu g‘oyaga asoslanadi: quick sortning partitsiyalash operatsiyasidan foydalanib, lekin faqat kerakli tomonni davom ettirib, o‘rtacha holatda O(n log n) o‘rniga O(n) vaqtga erishadi.
Bu masala, ayni paytda, rekursiyaning muhim bir xususiyatini ham ko‘rsatadi: ikkita rekursiv chaqiruv o‘rniga bittasini tanlash orqali butun rekursiya daraxtining shaklini — va shu bilan birga algoritmning murakkabligini — tubdan o‘zgartirish mumkin. Bu g‘oya keyingi mavzularda, xususan greedy va dynamic programming yondashuvlarida yana uchraydi, chunki ularda ham “barcha variantlarni ko‘rib chiqish” bilan “faqat kerakli yo‘lni tanlash” orasidagi farq algoritmning tezligini belgilaydi.