Masivlarni tashkil etish

“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.
4-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];
(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]); (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 (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 

---

16
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. a
1
, a
2
, .... a
i 
va b
1
, b
2
, … b
j 
ro‘yxatlar ustida ro‘yxatlar konkatenatsiyasi operatsiyasini bajarish kerak, 
natijada a
1
, a
2
, .... a
i 
i b
1
, b
2
, … b
j 
ro‘yxatga ega bo‘lamiz. L
1
L
2
, ro‘yxatlarning birlashmasidan 
hosil bo‘lgan L
1 
ro‘yxatni egallovchi konkatenatsiya CONCATENATED(L
1
, L
2
) 
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.
2.2 2-rasmda Punktir chiziqlar bilan L
1 
i L
2 
ro‘yxatlarni bitta L
1 
ro‘yxatga 
konkatenatsiyasida o‘zgargan ko‘rsatkichlar ko‘rsatilgan.
Endi yozuvlarning «cho‘ntak» saralashining dasturin tuzsak bo‘ladi. Bu dastur
5-dasturda ko‘rsatilgan, dastur ro‘yxatlar ustida bajariladigan bazaviy operatorlarni 
ishlatib tuzilgan.
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 }

---

17
2.2 2-rasm. Bog‘langan ro‘yxatlar konkatenatsiyasi