Massiv elementlarini saralash usullarining ichida quicksort

Download 0,98 Mb. Pdf ko'rish
bet	4/11
Sana	29.05.2024
Hajmi	0,98 Mb.
	#256363

1 2 3 4 5 6 7 8 9 10 11

Bog'liq
Tez saralash (Quick sort)

Saralash masalasini qo’yilishini quyidagicha yozish mumkin .

Saralash
–
bu berilgan to’plam elementlarini biror bir tartibda joylashtirish
jarayonidir. Saralashni maqsadi tartiblangan to’plamda kerakli elementni topishni
osonlashtirishdan iborat. Saralash dasturlarni translyasiya qilinayotganda,
ma’lumotlar majmuasini tashqi xotirada tashkil qilinayotganda, kutubxonalar,
kataloglar, ma’lumotlar bazasi yaratilayotganda tadbiq qilinadi. Ma’lumki,
saralashning turli hil algoritmlari mavjud. Sababi, bitta masalani saralash uchun juda
ko’plab turli hil algoritmlardan foydalanish mumkin. Berilgan masalani hal qilishda
ba’zilari mukammal bo’lishi mumkin. Shuning uchun saralash masalasida
algoritmlarni qiyosiy tahlilini o’tkazish zarurati paydo bo’ladi.
Saralash masalasini qo’yilishini quyidagicha yozish mumkin
.
Faraz qilaylik,
a
1
, a
2
,…, a
n
, elementlar ketma-ketligi berilgan bo’lsin. U holda
saralash algoritmi elementlarni massivga shunday joylashtiradiki, natijada ular
qandaydir munosabatga nisbatan
f(a
k1
)

f(a
k2
)

…

f(a
kn
)
tartibga ega bo’ladi
.
Odatda
f tartiblash funksiyasi qandaydir maxsus qoida bilan hisoblanmasdan, balki
elementni kalit qiymati bo’yicha massiv elementlari tartiblanadi.
Ma’lumotlarga qayta ishlov berilayotganda ma’lumotni informasion
maydonini hamda uni mashinda joylashishini (adresini) bilish zarur.
Saralashni ikkita turi mavjud:

ichki saralash – bu operativ xotiradagi saralash;

tashqi saralash – tashqi xotirada saralash.

Saralash bu ma’lumotlarni kalitlari bo’yicha xotirada regulyar ko’rinishda
joylashtirishdir. Regulyarlik deganda ma’lumotlar kalit qiymatlari bo’yicha
massivda boshidan oxirigacha o’sishi yoki kamayishi tushiniladi.

8
Agar saralanayotgan yozuvlar xotirada katta xajmni egallasa, u holda ularni
almashtirishlar katta sarf (vaqt va xotira ma’nosida) talab qiladi. Ushbu sarfni
kamaytishi maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda
faqatgina ma’lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi.
Yuqoridagi usul adreslar jadvalini saralash usuli deyiladi.
Saralanayotganda bir hil kalitlar uchrashi mumkin, bu holda saralanagandan
keyin bir hil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, ushbu tartibda
qoldirilishi maqsadga muvofiq bo’ladi (Bir hil kalitlilar o’zlariga nisbatan). Bunday
usulga turg’un saralash deyiladi.
Saralash samaradorligini bir necha mezonlar bo’yicha baholash mumkin:

saralashga ketgan vaqt.

saralash uchun talab qilingan operativ xotira;

Download 0,98 Mb.

1 2 3 4 5 6 7 8 9 10 11

Download 0,98 Mb.

Pdf ko'rish