Bubble sort (Pufakchali saralash)
“Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous.
VIII bo’lim. 2-dars
Saralash bo’limining birinchi darsida Selection sort algoritmini ko’rib chiqqan edik. Bu darsimizda yana bir eng sodda saralash algoritmlaridan biri bo’lgan Bubble sort algoritmini ko’rib chiqamiz.
Bubble sort algoritmi g’oyasi
Bubble sort algoritmi juda ham oddiy ishlaydi. U shunchaki array boshidan yurib ikkita qo’shni elementlarni ularning katta kichikligiga qarab joyini almashtiradi. Bu orqali har bir to’liq yurib chiqishdan keyin arraydagi eng katta (yoki eng kichik) element arrayning eng oxiriga o’tib qoladi.
Ushbu xusiyatiga ko’ra bu algoritm ba’zida Sink sort (Cho’kib saralash) deb ham ataladi. Lekin, albatta, Bubble sort nomi ko’proq jarangdorroq eshitiladi.
Yuqoridagi animatsiyada arrayning boshidan emas, orqasidan yurib chiqilgani sababli har bir array bo’ylab yurib chiqishda eng kichik element boshiga o’tib qolmoqda. Bu narsa algoritm qanday implementatsiya qilinganiga bog’liq.
Algoritm qadamlari
Ko’rib turganingizdek algoritm g’oyasi juda ham oddiy. Endi uni qadamma-qadam keltirib o’tamiz.
- Array boshidan uning oxirgi elementidan bitta oldingi elementigacha yurib chiqamiz.
- Har bir yurib chiqishda ichki takrorlanish orqali qo’shni elementlarni bir-biri bilan solishtirib, katta elementni o’ng tomonga joylashtirib ketamiz. (O’sish tartibidagi saralashda)
- Har bir tashqi takrorlanish qadami tugagandan so’ng bizda array oxiridan boshlab array saralanib boradi. Shu sababli har safar ichki takrorlanishda bu qismni qayta ko’rib chiqish shart emas.
- Tashqi takrorlanish tugaganda bizda saralangan massiv hosil bo’ladi.
Algoritm murakkabligi
Bubble sort algoritmining ishlash tezligi ham O(n²) hisoblanadi (n — array uzunligi). Ya’ni yuqorida ko’rib o’tganimizdek, bitta tashqi takrorlanish har bir qadamida arrayni to’liq ko’rib chiqish kerak bo’ladi.
Video darsimizni ko’rishdan oldin uning implementatsiyasiga o’zingiz mustaqil urinib ko’ring.
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.
Muallif: Qudratxo’ja Musayev
Manba: @AlgorithmUz telegram kanali
YouTube kanalimiz: Algorithms Uzbekistan
“Eng yaxshi reklama — bu mamnun mijoz tomonidan qilingan reklama” — Philip Kotler
