Mirzo Ulug’bek nomidagi O’zbekiston Milliy universiteti Jizzax filiali “Amaliy matematika” fakulteti

Tez tartiblash variantlari. O‘rta holatda k-tartibli statistikani topish uchun tez tartiblash usuliga asoslangan protsedurani rekursiv ishlatiladi. Bu protsedurani select (tanlash) deb nomlaymiz. select(l, j, k) protsedurasi qandaydir katta A[1], ..., A[n] massivdan olingan A[i], ..., A[j] elementlar orasidan k – elementni topadi. select protsedurasi quyidagi harakatlarni bajaradi.

1. Tayanch elementni tanlash, masalan υ.

2. partition protsedurasini ishlatib, A[i], ..., A[j] elementlarni ikki guruhga bo‘lish. Birinchi A[i], ..., A[m-1] guruhda barcha yozuvlarning kalit υ dan kichik, ikkinchi A[m], ..., A[j] guruhda—υ ga teng yoki katta.

3. Agar k≤m-i bo‘lsa, u holda k-element birinchi guruhda joylashadi va unga yana select(i, m-1, k) protsedurasi qo‘llaniladi. Agar k>m-i bo‘lsa, u holda select(m, j, k-m+ i) protsedurasi chaqiriladi.

Bir xil qiymatlardagi kalitlarga ega bo‘lgan A[i], ..., A[j] elementlar uchun select(i, j, k) protsedurasi ertami-kech chaqiriladi (va shuning uchun i=j bo‘ladi). Bu elementlarning kalitlari izlanayotgan k-tartibli statistika qiymati bo‘ladi.

Tez tartiblash usulidagidek, select protsedurasi eng yomon holatda Ω(n2) dan kam bo‘lmagan vaqt talab qiladi. Masalan, agar eng kichik elementni topishda tayanch element sifatida har doim kalit qiymatlaridan eng kattasini olish kerak, u holda bu protsedura uchun bajarilish vaqti O(n2) tartibda bo‘ladi. Lekin o‘rta holatda select protsedurasi tez tartiblash algoritmiga nisbatan tez ishlaydi, o‘rtacha u O(n) vaqtda bajariladi. Bu algoritmlar orasidagi farq shundan iboratki, tez tartiblash protsedurasi ikki marta chaqirilganda, select protsedurasi bir marta chaqiriladi. Select protsedurasining tahlili tez tartiblash protsedurasining tahlilidek bo‘ladi. Bu protsedura avvalgi qadamda chaqirilgan to‘plamning bir qismi bo‘lib hisoblangan qism to‘plamda o‘zini takroran chaqiradi. Bu protseduraning har bir chaqirilishi protseduraning avvalgi chaqirilishi amalga oshirilgan to‘plamning 9/10 qismidan iborat bo‘lgan elementlar to‘plamida amalga oshiriladi. U holda, agar T(n) orqali n ta elementdan iborat to‘plamda select protsedurasiga ketgan vaqtni belgilasak, qandaydir o‘zgarmaslar uchun quyidagilarga ega bo‘lamiz:

T(n)≤T(9/10* n) + sn (1.14)

(1.14) T(n) = O(n) teng bo‘lishini ko‘rsatish qiyin emas.