Qarshi davlat universiteti fizika-matematika fakulteti

Algoritm samaradorligi:
taqqoslashlar soni M = ,
almashtirishlar soni C_max = 3 .

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 – 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.