DSA Bubble Sort (pufakchali saralash)

Bubble Sort

Bubble Sort — massivni eng kichik qiymatdan eng katta qiymatgacha saralaydigan algoritm.

Bubble Sort algoritmi qiymatlar massivini saralaganda bu qanday ko‘rinishini ko‘rish uchun simulyatsiyani ishga tushiring. Massivdagi har bir qiymat ustun bilan tasvirlangan.

"Bubble" (pufakcha) so‘zi ushbu algoritmning ishlash usulidan kelib chiqqan: u eng katta qiymatlarni pufakchalar kabi "yuqoriga suzib chiqaradi".

Bubble Sort algoritmini va uni o‘zingiz qanday amalga oshirishni to‘liq tushunish uchun o‘qishda davom eting.

Qo‘lda bajarib ko‘rish

Bubble Sort algoritmini dasturlash tilida amalga oshirishdan oldin, g‘oyani tushunib olish uchun qisqa massiv bo‘ylab faqat bir marta qo‘lda o‘tib chiqaylik.

1-qadam: Saralanmagan massivdan boshlaymiz.

2-qadam: Dastlabki ikkita qiymatni ko‘rib chiqamiz. Kichikroq qiymat birinchi turibdimi? Ha, shuning uchun ularni almashtirishimiz shart emas.

3-qadam: Bir qadam oldinga o‘tib, 12 va 9 qiymatlarini ko‘rib chiqamiz. Kichikroq qiymat birinchi turibdimi? Yo‘q.

4-qadam: Demak, 9 birinchi turishi uchun ularni almashtirishimiz kerak.

5-qadam: Bir qadam oldinga o‘tib, 12 va 11 ni ko‘rib chiqamiz.

6-qadam: 11 soni 12 dan oldin turishi uchun ularni almashtirishimiz kerak.

7-qadam: 12 va 3 ni ko‘rib chiqamiz. Ularni almashtirishimiz kerakmi? Ha.

8-qadam: 3 birinchi turishi uchun 12 va 3 ni almashtiramiz.

Yuqoridagi 8 ta qadamni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Algoritmni to‘liq tushunishimiz va uni dasturlash tilida amalga oshira olishimiz uchun ushbu birinchi o‘tishda nima sodir bo‘lganini tushunib olishimiz kerak.

Eng katta qiymat — 12 ga nima bo‘lganini ko‘ryapsizmi? U pufakcha kabi massiv oxiriga, ya’ni o‘z joyiga suzib chiqdi. Ammo massivning qolgan qismi saralanmaganicha qolmoqda.

Shunday qilib, Bubble Sort algoritmi massiv bo‘ylab qayta-qayta o‘tib chiqishi kerak va har safar navbatdagi eng katta qiymat o‘zining to‘g‘ri o‘rniga suzib chiqadi. Saralash eng kichik qiymat — 3 massiv boshida qolguncha davom etadi. Demak, 5 ta qiymatli massivni saralash uchun massiv bo‘ylab 4 marta o‘tishimiz kerak.

Algoritm massiv bo‘ylab har safar o‘tganda massivning qolgan saralanmagan qismi qisqarib boradi.

To‘liq qo‘lda bajarib ko‘rish quyidagicha ko‘rinadi:

Endi o‘rganganlarimizdan foydalanib, Bubble Sort algoritmini dasturlash tilida amalga oshiramiz.

Bubble Sort’ni amalga oshirish

Bubble Sort algoritmini dasturlash tilida amalga oshirish uchun bizga quyidagilar kerak:

1. Saralanadigan qiymatlarga ega massiv.
2. Massiv bo‘ylab o‘tadigan va birinchi qiymat keyingisidan katta bo‘lsa, qiymatlarni almashtiradigan ichki sikl. Bu sikl har safar bajarilganda bitta kamroq qiymat bo‘ylab o‘tishi kerak.
3. Ichki sikl necha marta bajarilishi kerakligini boshqaradigan tashqi sikl. n ta qiymatli massiv uchun bu tashqi sikl n-1 marta bajarilishi kerak.

Natijaviy kod quyidagicha ko‘rinadi:

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(n-1):
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]

print("Sorted array:", my_array)

Bubble Sort’ni takomillashtirish

Bubble Sort algoritmini yana biroz takomillashtirish mumkin.

Tasavvur qiling, massiv deyarli saralangan va eng kichik sonlar boshida turibdi, masalan, quyidagicha:

my_array = [7, 3, 9, 12, 11]

Bu holda massiv birinchi o‘tishdan keyin saralangan bo‘ladi, ammo Bubble Sort algoritmi elementlarni almashtirmagan holda ishlashda davom etaveradi, bunga esa hojat yo‘q.

Agar algoritm massiv bo‘ylab biror qiymatni almashtirmasdan bir marta o‘tib chiqsa, demak, massiv to‘liq saralangan bo‘ladi va algoritmni to‘xtatishimiz mumkin, masalan:

my_array = [7, 3, 9, 12, 11]

n = len(my_array)
for i in range(n-1):
    swapped = False
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]
            swapped = True
    if not swapped:
        break

print("Sorted array:", my_array)

Bubble Sort’ning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Bubble Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Bubble Sort algoritmi massivdagi har bir qiymat bo‘ylab sikl bilan o‘tib, uni yonidagi qiymat bilan taqqoslaydi. Demak, \(n\) ta qiymatli massiv uchun bitta siklda \(n\) ta shunday taqqoslash bajarilishi kerak.

Bitta sikldan keyin esa massiv bo‘ylab qayta-qayta, jami \(n\) marta o‘tiladi.

Bu jami \(n \cdot n\) ta taqqoslash bajarilishini anglatadi, shuning uchun Bubble Sort’ning vaqt murakkabligi quyidagicha:

\[ \underline{\underline{O(n^2)}} \]

Bubble Sort vaqt murakkabligini tasvirlovchi grafik quyidagicha ko‘rinadi:

Ko‘rib turganingizdek, massiv hajmi oshirilganda bajarilish vaqti juda tez ortadi.

Yaxshiyamki, bundan tezroq saralash algoritmlari ham bor, masalan, keyinroq ko‘rib chiqadigan Quicksort algoritmi.

Quyida Bubble Sort’ni simulyatsiya qilishingiz mumkin, bu yerda qizil punktir chiziq nazariy vaqt murakkabligi \(O(n^2)\) ni bildiradi. Qiymatlar soni \(n\) ni tanlab, haqiqiy Bubble Sort kodini ishga tushirishingiz mumkin: unda amallar sanaladi va ularning soni quyidagi grafikda ko‘k xoch bilan belgilanadi. Nazariya amaliyotga qanchalik mos keladi?

[,,,,]