Saralash haqida. Saralash usullari va ularning turlari. Bubble Sort saralash algoritmi va uning dasturi

Algoritm samaradorligi:
Taqqoslashlar soni M = .
Almashtirishlar soni C_min = 3(n - 1), C_max = 3(n - 1)
(n² tartib).
Ushbu usul bo’yicha saralash bajarilsa, eng yomon xolda taqqoslashlar va almashtirishlar soni tartibi n² bo’ladi.


2. Saralash usullari va ularning turlari.

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.

Bu misolda biz kichigidan kattasiga qarab saralash bajaramiz biz izlayotgan eliment eng pasda bulsaxam biz uni taqoslashlar bilan yuqoriga pufakcha usulida qalqitib chiqaramiz bunday misollarni kuplab keltirishimiz mumkun asosiy maqsadimiz bu saralash algoretmining qulayligin urgatishdan ibotrat buladi . Saralashga biz yana bir misol bilan javob beramiz.
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.
Ular quyidagilar:
1. Bubble sort saralash algoritmi
2. Selection sort saralash algoritmi
3. Insertion sort saralash algoritmi
4. Quick sort saralash algoritmi
5. Merge sort saralash algoritmi
Quyida biz ushbu saralash algoritmlaridan bir nechtasini ko`rib o`tamiz,