Sonlar berilishi: 23, 54, 3, 22, 1, 45

Bugungi mavzuimiz algoritmlashning to`rt asosiy yo`nalishlaridan biri hisoblangan saralash algoritmlariga bag`ishlanadi. 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 maktab jismoniy tarbiya darsi. Bu dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familyalar ketma-ketligiga qarab topshirishadi. Shu yerning o`zida 2ta saralashdan foydalanilyapti. Biri, bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalidagi o`rinlar bo`ycha.
Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz):
Sonlar berilishi: 23, 54, 3, 22, 1, 45;
Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turipti)
Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son)
Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)
Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi)1111
Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma`lumki, bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi. Dasturlashga talab ortib bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ldi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralshdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, shu sabali 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:

Bubble sort

Selection sort
Insertion sort
Quick sort
Merge sort
Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous.
VIII bo’lim. 0-dars
Yangi bo’limimiz dasturlashda eng muhim mavzulardan bo’lgan saralash mavzusiga bag’ishlanadi. Biror bir ma’lumotni saralash yoki qandaydir qolipga solish juda ham muhim. Sababi, tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va xatoliklarga moyil bo’ladi.
Tasavvur qilaylik sizda telefon raqamlari saqlanadigan daftarchasi bor (hali qo’l telefonlari ommalashmagan vaqtni eslang) va undagi nomlar tartibsiz holda yozilgan. Siz, aytaylik, Nodir ismli do’stingizning raqamini topishingiz uchun bu daftarchani boshidan boshlab axtarib chiqishga majbur bo’lasiz, bu esa ko’p vaqtni oladi. Lekin, agar ular alifbo tartibida saralab qo’yilgan bo’lsa, siz to’g’ri N harfiga o’tib izlashni boshlaysiz va vaqtdan bir necha barobarga yutasiz. (Chiziqli va Ikkilik saralash mavzularini eslang)
Biz bu bo’limda saralash deganda, eng oddiy bo’lgan arraydagi ma’lumotlarni saralashni nazarda tutamiz va bu kabi saralash algoritmlarining olti xilini ko’rib chiqamiz:
Selection sort (Tanlab saralash)
Bubble sort (Pufakchali saralash)
Insertion sort (Joylashtirib saralash)
Quick sort (Tezkor saralash)
Merge sort (Qo’shib saralash)
Radix sort
Ularning deyarli hammasi (6-sidan tashqari) ma’lumotlarni taqqoslab ko’rish orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi. Birinchi 3 ta algoritm O(n²) vaqtda ishlasa, 4–5 lari O(nlogn) vaqtda ishlaydi. Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi.
Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:
Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin.
Buni tushunish uchun quyidagi misolni keltiramiz. Bu yerda turli xil saralash algoritmlarining ishlashi vizual holda bir biri bilan taqqoslangan. Birinchi holatda kiruvchi ma’lumotlar, ya’ni saralanishi kerak bo’lgan ma’lumotlar ixtiyoriy turda va holatda:
Image for post
Source: toptal.com
Bu holatda Heap, Merge, Quick sort kabi algoritmlar o’z ishini boshidagi 3 ta algoritmdan ko’ra ancha tez yakunlayapti.
Endi esa bu misolga e’tibor bering. Endi saralanishi kerak bo’lgan ma’lumotlar to’liq bo’lmasa ham, deyarli saralangan holatda:
Image for post
Source: toptal.com
Bu holda e’tibor bergan bo’lsangiz, Insertion sort (birinchi turgani) algoritmi yuqorida aytilgan murakkab algoritmlardan ko’ra bir necha barobar tez ishlashini ko’rishingiz mumkin.
Biz yuqorida faqat ikki xil holatni, ixtiyoriy va deyarli saralangan ma’lumotlarni saralagan holatni ko’rib chiqdik. Bunday holatlar esa ko’plab topiladi, masalan teskari saralangan, bir turdagi ma’lumotlar ko’p yoki kam bo’lgan va h.k ma’lumotlarni saralash. Har bir holat uchun ma’lum bir algoritmlar qolganlaridan ko’ra tezroq yoki sekinroq ishlab qolishi mumkin.
Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi.
Saralash algoritmlarida turg’unlik (stability) deganda, ikkita bir xil elementning ilk holatdagi bir biriga nisbatan o’rninini saralashdan keyin ham saqlab qolishiga aytiladi.
Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan algoritm saraladan keyin doim birinchi 1 sonini ikkinchi 1 sonidan doim oldin joylashtirsa, bu algoritm turg’un saralovchi algoritm deyiladi.
Yana haqli savol tug’ilishi mumkin, “Bu narsaning kimga keragi bor, baribir natija 1 1 2 3 4 5 bo’ladiku?” degan. Albatta, bu holatda turg’unlik ahamiyati sezilmasligi mumkin. Lekin, aytaylik siz biror korxona ishchilari ma’lumotlarini ularning nomiga ko’ra saralagan paytda turg’unlik kerak bo’lib qolishi mumkin. Ya’ni, birinchi Nodirbek ma’lumotlari, ikkinchi Nodirbek ma’lumotlaridan keyin turishi kerak degan kabi.
Saralash algoritmlari ichidagi Quick Sort ko’p hollarda Merge yoki Heap sortdan tez ishlagani bilan u turg’un saralash algoritmi hisoblanmaydi (Turg’un holga keltirishning iloji bor).
Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan tizim samaradorligiga ta’sir qilishi mumkin. Shu sababdan, turli xil saralash algoritmlari ishlashini o’rganish va tushunish professional dasturchi uchun muhim hislatlardan biri hisoblanadi.
Bu darsimizda sizlar bilan saralash haqida umumiy tushunchani va saralash algoritmlari bir-biridan qanday farqlanishini ko’rib chiqdik. Keyingi darslardan sarlash algoritmlarini ko’rib chiqish mobaynida bu narsalar haqida yana batafsilroq gaplashamiz.
Maqolani sizga yoqqan bo’lsa unga qarsak (clap) chalib qo’yishni esdan chiqarmang. 50 tagacha qarsak chalish mumkin. Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing! Bizning Telegram va YouTube kanallarimizga, hamda Mediumdagi sahifamizga obuna bo’lishni unutmang.