Masivlarni tashkil etish

Tez saralash. O(n log n) vaqtda bajariladigan, ichki saralash usullarining eng 
samaradori bo‘lib hisoblangan tez tartiblashni ko‘rib chiqamiz. Bu algoritmda massivning 
A[1],...,A[n] elementlarini tartiblash uchun bu elementlardan massiv elementlari unga 
nisbatan tartiblanadigan tayanch element sifatida v kalitning qandaydir qiymati tanlanadi. 
Qulaylik uchun, tayanch element sifatida kalit qiymatlari taqsimotining medianaga eng yaqin 
bo‘lganini tanlab olish zarur. Chunki, tayanch element kalit qiymatlarini deyarli teng ikki 
qismga ajratadi.
Keyin massiv elementlari shunday joylashtiriladiki, qandaydir j indeks uchun barcha
A[1], ..., A[j] keltirilgan elementlar υ dan kichik kalit qiymatlarga, A[j+1], ...,
A[n] barcha elementlari υ ga teng yoki katta kalit qiymatlarga ega bo‘ladi. Keyin tez 
tartiblash protsedurasi A[1], .... A[j] va A[j+1], ..., A[n] elementlar to‘plamiga bu to‘plamlarni 
alohida tartiblash uchun rekursiv ishlatiladi. Birinchi to‘plamning kalit qiymatlari ikkinchi 
to‘plamning kalit qiymatlaridan kichik bo‘lgani uchun boshlang‘ich massiv to‘g‘ri 
tartiblanadi.
2.2 1-rasm. Tez tartiblash algoritmi etaplari.

---

14
Misol. 2.2 1-rasmda 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 butun sonlar ketma-ketligi ustida 
bajariladigan tez tartiblash algoritmining bajarilish qadamlari keltirilgan. Har bir qadamda υ 
ning qiymati eng chapdagi turli xil ikkita element-sonning kattasi sifatida tanlanadi.
Tartiblash protsedurani rekursiv chaqirish jarayonida alohida qism to‘plamlar bir xil kalitdan 
tashkil topganda tugatiladi. 2.2 1-rasmda har bir etap ikki qadamda ko‘rsatilgan: avval har bir 
alohida qism to‘plam uchun o‘zining qiymati tanlanadi va keyin bu qism to‘plamning 
elementlari tanlangan qiymatga mos ravishda joylashtiriladi, va xuddi shunday tartiblash 
protsedurasi rekursiv ishlatiladigan yana ikkita qism to‘plamga bo‘linadi.
Endi quicksort protsedurasidan tashqarida aniqlangan A massiv elementlari bilan 
ishlaydigan quicksort rekursiv protsedurasini ishlab chiqishni boshlaymiz. Quicksort(i,j) 
protsedurasi A[1], ..., A[n] elementlarni tartiblashi kerak. Bu protseduraning algoritmi 
2dasturda kiritilgan.
2-dastur. Tez tartiblash usuli protsedurasi
(1) 
if A[i], ..., A[j] ikkita turli xil kalitlarga ega bo‘lsa then begin
(2) 
v — topilgan ikkita turli xil kalitlarning kattasi bo‘lsin;
(3) 
A[x], ..., A[j] elementlar shunday joylashtiriladiki, qandaydir k, 
i+lteng kalitga ega bo‘lsin;
(4) 
quicksort{i, k-1) ,- (5) quicksort{k, j) end
Endi tez tartiblash algoritmining eskizini (2-dastur) haqiqiy quicksort dasturiga 
aylantiramiz. Bu dasturning kodi 3-dasturda keltirilgan. aggau[1..n] of recordtype turidagi A 
massivni saralash uchun quicksort(l, n) protsedurasini chaqirish kerak.
3-dastur. Tez tartiblash usuli protsedurasi procedure quicksort (i, j: integer); 
{A tashqi massivning A[i],...,A[j] elementlarini tartiblaydi}
var pivot: 
keytype; pivotindex: integer;
{kaliti pivot ga teng bo‘lgan A massiv elementi} k: integer;
{kalit>pivot bo‘lgan elementlar guruhining boshlang‘ich indeksi} begin
(1) 
pivotindex:= findpivot{i, j) ;
(2) 
if pivotindex <> 0 then begin {agar barcha kalitlar teng bo‘lsa, hech narsa 
bajarish kerak emas}
(3) 
pivot:= Alpivotindex] .key;
(4) 
k:= portition(i, j, pivot);
(5) 
quicksortd, k-1) ;
(6) 
quicksort{k, j) end end; {quicksort}

---

15