1.2. Massiv elementlarini saralash va saralash usullari haqida
Saralash deb , berilgan obyektlar ketma – ketligini ma’lum mantiqiy tartibda
qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq
bo`lishi mumkin. Misol uchun jismoniy tarbiya darslarida talabalar bo`ylariga qarab
safda turadi, lekin o`quv jurnalida esa ularning universitetga qabul qilingan o`rni
bo`yicha joylashgan. Shu yerning o`zida ikkita saralashdan foydalanilayapti.
Birinchisi bo`y uzunligi bo`yicha , ikkinchisi esa o`quv jurnalidagi yozilgan o`rinlari
bo`yicha.
Saralash jarayoni qanday bo`ladi degan savolga javob berishga urinib
ko`ramiz. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanar ekan. Bu
jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma
6
– bir tahlil qilib chiqamiz. Buning uchun saralanmagan (tartiblanmagan) sonlar
ketma ketligini olamiz:
Quyidagi sonlar berilgan bo`lsin: 23, 54, 3, 22, 1, 45;
1. Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;
2. Yana 1 da qilgan ishimizni takrorlaymiz: 3, 22, 1, 23, 45, 54;
3. Yuqoridagi amalni yana bajaramiz: 3, 1, 22, 23, 45, 54;
4. Oxirgi marta almashtiramiz: 1, 3, 22, 23, 45, 54;
Demak miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma’lumki,
bizning miyamiz o`zi qulay hisoblagan yo`nalish bo`yicha ketadi va biz uchun faqat
bitta saralash algoritmi mavjud. Ammo dasturlashda bu mulohazamiz noto`g`ri
hisoblanar ekan. Dasturlashda saralash usullarining bir qanchasi mavjud.
Dasturlashga talab ortib bu soha rivojlanib borgani sari unda bir qator sohalardagi
kabi tezlikni oshirish mjuammosi paydo bo`ldi. Chunki ilk kompyuterlarda
kompyuter tizimining 30% tezligi, operativ xotirasini saralashga sarflanar edi. Shu
o`rinda savol tug`iladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Bu
savolga javob berish uchun hozirda keng foydalanilayotgan Total Commander
dasturi ishlash prinsipini eslashimiz kifoya. Unda bir necha xil saralash mavjud: fayl
turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish
tartibida saralash mumkin. Hozirgi tizimlarda esa 30% emas anchagina kamroq
tezlik va xotira sarflanadi. Chunki tezlik masalasi tobora yuqoriga chiqayotgan va
ishlanayotgan ma’lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi
algoritmlardan foydalanish maqsadga muvofiq emas. Ma’lumotlar o`lchami juda
katta, shu sababli ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish
uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni yechimi sifatida bir
necha turdagi algoritmlardan foydalaniladi.
Ular quyidagilar:
1. Bubble sort saralash algoritmi
2. Selection sort saralash algoritmi
3. Insertion sort saralash algoritmi
4. Quick sort saralash algoritmi
7
5. Merge sort saralash algoritmi
|