Saralashning sodda sxemalari. Eng sodda tartiblash usullaridan biri bo‘lib «pufakcha» usuli hisoblanadi. Bu algoritmning asosiy g‘oyasini yozish uchun tartiblanishi kerak bo‘lgan yozuvlar vertikal joylashgan massivda saqlanadi deb faraz qilamiz. Kalit maydonning kichik qiymatli yozuvlari «yengil» va shuning uchun pufakcha kabi ular yuqoriga «suzib chiqadi». Massiv bo‘ylab birinchi o‘tishda massivning birinchi yozuvi olinadi va uning kaliti navbatma-navbat keyingi yozuvlarning kalitlari bilan solishtirib boriladi. Agar nisbatan «og‘ir» kalitli yozuvlar uchrasa, u holda bu yozuvlar joyini almashtiradi. Nisbatan «yengil» yozuvlar uchraganda bu yozuv taqqoslash uchun etolon bo‘ladi va keyingi barcha yozuvlar shu kalit bilan solishtiriladi. Natijada eng kichik qiymatli kalit massivning eng yuqorisiga chiqadi. Massiv bo‘ylab ikkinchi o‘tishda massivning massivni birinchi o‘tishda topilgan yozuvdan keyin joylashgan og‘irligi bo‘yicha ikkinchi kalit olinadi. Massiv bo‘ylab ikkinchi va keyingi o‘tishlarda oldingi o‘tishlarda topilgan yozuvlarni ko‘rib chiqish shart emas, chunki ular qolgan yozuvlarga qaraganda kichik kalitlarga ega.
Boshqacha qilib aytganda, t – o‘tishda i pozitsiya yuqorida turgan elementlar tekshirilmaydi. 8.1-dasturda ushbu algoritm keltirilgan.
«pufakcha» algoritmi
(1) for i:= I to n - 1 do
(2) for j:= 1 downto i + 1 do
(3) if A[j].key < A[j - 1].key then
(4) swap(A[j], A[j - 1])
swap protsedurasi yozuvlarning o‘rnini almashtirish uchun ko‘plab tartiblash algoritmlarida ishlatiladi, uning kodi quyidagi dasturda keltirilgan.
8.1-dastur. swap protsedurasi
procedure swap ( var x, u: recordtype )
{swap x va u yozuvlarning o‘rnini almashtiradi}
var
temp: recordtype;
begin
temp:= x;
x:= y;
y:= temp;
end; { swap }
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.
1.1- rasmda Tez tartiblash algoritmi etaplari keltirilgan.
Misol. Yuqoridagi 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. 1.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 1.2-dasturda kiritilgan.
1.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+l
uchun A[i], ..., A[k-1] lar v dan kichik, A[k], ..., A[j] esa v dan katta yoki teng kalitga ega bo‘lsin;
(4) quicksort{i, k-1) ,-
(5) quicksort{k, j)
end
Endi tez tartiblash algoritmining eskizini (1.2-dastur) haqiqiy quicksort dasturiga aylantiramiz. Bu dasturning kodi 1.3-dasturda keltirilgan. aggau[1..n] of recordtype turidagi A massivni saralash uchun quicksort(l, n) protsedurasini chaqirish kerak.
1.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}
“CHo‘ntak” saralash. Ko‘p hollarda O(n log n) dan kam bo‘lgan tartiblash vaqtini olish mumkin, lekin tartiblanayotgan kalitlar haqida qo‘shimcha ma’lumot kerak bo‘ladi.
1.5-misol. Faraz qilamiz, kalit qiymatlar 1 dan to n gacha bo‘lgan butun sonlar bo‘lib hisoblansin, ular takrorlanmaydi va tartiblanayotgan elementlar soni ham n ga teng. Agar A va V orqali aggau[1..n] of recordtype massivni ifodalansa, tartiblanishi kerak bo‘lgan n ta element birinchi A massivda joylashadi, u holda V massivga kalitlarni quyidagi qiymatlarda navbatma-navbat joylashtirib borishni tashkillashtirish mumkin:
for i:= 1 to n do
V[A[i].key]:= A[i]; (8.4)
Bu kod A[i] element V massivning qaerida joylashishini hisoblab beradi. Butun bir sikl O(n) vaqt tartibiga ega va barcha kalitlar qiymatlari turli xil bo‘lganda va 1 dan to n intervaldagi butun sonlar bo‘lganda yaxshi ishlaydi.
O(n) vaqtda A massiv elementlarini, lekin ikkinchi V massivni ishlatmasdan tartiblaydigan boshqa usullar ham mavjud. Navbatma-navbat A[1], ..., A[n] elementlarga murojaat qilamiz. Agar A[i] yacheyka j kalitga ega bo‘lsa va j≠i bo‘lsa, u holda A[i] va A[j] yacheykalardagi yozuvlar o‘rnini almashtiradi. Agar bu almashtirishdan keyin A[i] yacheyka k kalitga ega bo‘lsa va k≠i bo‘lsa, u holda A[i] va A[k] orasida o‘rin almashtirishlar bo‘ladi va h.k. Har bir o‘rin almashtirish hech bo‘lmaganda bitta yozuvni kerakli tartibda joylashtiradi. SHuning uchun A massiv elementlarini tartiblaydigan ushbu algoritm O(n) bajarilish vaqtiga ega bo‘ladi.
for i:= 1 to n do
while A[i].key <> i do
swap(A[i], A[A[i].key]);
(1.4) dastur — bu «cho‘ntak» saralashga oddiy misol, bu erda aniqlangan qiymatli kalitlarni saqlash uchun «cho‘ntak» lar ishlatadi. Berilgan yozuv r qiymatli kalitga ega bo‘lsa, u holda bu yozuvni yozuvlar uchun «cho‘ntak»ga joylashtiramiz. Dasturda (1.4) «cho‘ntak» bo‘lib V massivning elementlari hisoblanadi, bu erda B[i] – i qiymatli kalitga ega bo‘lgan yozuvlar uchun «cho‘ntak». «Cho‘ntak» sifatidagi massivlarin faqat oddiy hollarda ishlatish mumkin (bitta «cho‘ntak»da bittadan ortiq yozuv bo‘lmagan taqdirda). Bundan tashqari, massivlarni «cho‘ntak» lar sifatida ishlatishda «cho‘ntak» ichida elementlarni tartiblash zaruriyati paydo bo‘lmaydi, chunki bitta «cho‘ntak» bittadan ko‘p bo‘lmagan yozuvdan iborat, algoritm shunday yaratilganki, massivdagi elementlar to‘g‘ri tartibda joylashadi.
Lekin umumiy holda bitta «cho‘ntak» da bir nechta yozuvlarni saqlash, shuningdek bir nechta «cho‘ntak»larni bittaga birlashtirish mumkinligini e’tiborga olish kerak. Aniqlik uchun A massiv elementlari recordtype ma’lumotlar turiga, yozuv kalitlari esa – keytype turiga ega deb hisoblaymiz. recordtype turidagi ro‘yxat elementlarini listtype (ro‘yxat turi) ma’lumotlar turi orqali ifodalab olamiz. Listtype turi ro‘yxatning ixtiyoriy turi bo‘lishi mumkin, lekin hozirgi holatda bizga ko‘proq bog‘langan ro‘yxatlar to‘g‘ri keladi. Ro‘yxatning umumiy uzunligi fiksirlangan va n ga teng deb faraq qilishimiz mumkin.
Shuningdek array[keytype] of listtype turidagi V massiv ham kerak. Bu ro‘yxatlarni saqlovchi massiv «cho‘ntak»i bo‘lib hisoblanadi. V massivning indeksi keytype ma’lumotlar turiga ega, chunki bu massivning har bir elementi kalitning bitta qiymatiga mos keladi. SHunday qilib, 9-dasturni umumlashtirish mumkin, chunki endi «cho‘ntak»lar keraklicha hajmga ega. «Cho‘ntak»larni qanday birlashtirish mumkinligini ko‘rib chiqamiz. a1, a2, .... ai va b1, b2, … bj ro‘yxatlar ustida ro‘yxatlar konkatenatsiyasi operatsiyasini bajarish kerak, natijada a1, a2, .... ai i b1, b2, … bj ro‘yxatga ega bo‘lamiz. L1L2, ro‘yxatlarning birlashmasidan hosil bo‘lgan L1 ro‘yxatni egallovchi konkatenatsiya CONCATENATED(L1, L2) operatsiyasini tadbiq etish uchun ro‘yxatlarning ixtiyoriy ifodalanishidan foydalanish mumkin.
Ro‘yxat sarlavhalariga qo‘shishda konkatenatsiya operatori yanada samarali bajarilishi uchun ro‘yxatning oxirgi elementlariga ko‘rsatkichlarni ishlatish mumkin.
1.4-rasmda punktir chiziqlar bilan L1 i L2 ro‘yxatlarni bitta L1 ro‘yxatga konkatenatsiyasida o‘zgargan ko‘rsatkichlar ko‘rsatilgan.
Endi yozuvlarning «cho‘ntak» saralashining dasturin tuzsak bo‘ladi. Bu dastur 1.5-dasturda ko‘rsatilgan, dastur ro‘yxatlar ustida bajariladigan bazaviy operatorlarni ishlatib tuzilgan.
1.5-dastur. binsort dasturi (cho‘ntak saralash)
procedure binsort;
{A massiv elementlarini tartiblaydi, tartiblangan ro‘yxatni V[lowkey] «cho‘ntak»ga yozadi}
var
i: integer;
v: keytype;
begin
{"cho‘ntak"ka yozuvlarni kiritish boshlanadi}
(1) for i:= 1 to n do
{ A[i] elementni «cho‘ntak» boshiga joylashtirish}
(2) INSERT(A[i], FIRST(B[A[i].key]), B[A[i].key]);
(3) for v:= succ(lowkey) to highkey do
(4) CONCATENATE(B[lowkey] , B[v])
end; { binsort }
1.4-rasm. Bog‘langan ro‘yxatlar konkatenatsiyasi.
|
