Pufakchali saralash (bubble sort)
Pufakcha saralash
Bubble Sort - massivni eng past qiymatdan eng yuqori qiymatga saralaydigan algoritm.
{{ msgDone }}
Bubble Sort algoritmi qiymatlar massivini saralaganda qanday ko‘rinishini ko‘rish uchun simulyatsiyani ishga tushiring. Massivdagi har bir qiymat ustun bilan ifodalanadi.
"Bubble" so‘zi ushbu algoritm qanday ishlashidan kelib chiqqan bo‘lib, u eng yuqori qiymatlarni "qabariq" qiladi.
Qanday ishlaydi:
- Massiv bo‘ylab o‘ting, bir vaqtning o‘zida bitta qiymat.
- Har bir qiymat uchun qiymatni keyingi qiymat bilan solishtiring.
- Agar qiymat keyingi qiymatdan yuqori bo‘lsa, eng yuqori qiymat oxirgi bo‘lishi uchun qiymatlarni almashtiring.
- Massivda qancha qiymatlar mavjud bo‘lsa, shuncha marta massivdan o‘ting.
Qo‘lda yugurish
Biz dasturlash tilida Bubble Sort algoritmini amalga oshirishdan oldin, keling, qisqa massivni faqat bir marta qo‘lda ishlaylik, shunchaki fikrni tushunish uchun.
1-qadam: Biz tartiblanmagan massivdan boshlaymiz.
[7, 12, 9, 11, 3]
2-qadam: Biz ikkita birinchi qiymatni ko‘rib chiqamiz. Eng past qiymat birinchi o‘rinda turadimi? Ha, shuning uchun biz ularni almashtirishimiz shart emas.
[7, 12, 9, 11, 3]
3-qadam: Oldinga bir qadam tashlang va 12 va 9 qiymatlariga qarang. Eng past qiymat birinchi o‘rinda turadimi? Yo‘q.
[7, 12, 9, 11, 3]
4-qadam: Shunday qilib, biz ularni almashtirishimiz kerak, shunda 9 birinchi bo‘ladi.
[7, 9, 12, 11, 3]
5-qadam: 12 va 11 ga qarab, oldinga bir qadam tashlash.
[7, 9, 12, 11, 3]
6-qadam: 11 ni 12 dan oldin kelishi uchun almashtirishimiz kerak.
[7, 9, 11, 12, 3]
7-qadam: 12 va 3 ga qarab, biz ularni almashtirishimiz kerakmi? Ha.
[7, 9, 11, 12, 3]
8-qadam: 3 birinchi bo‘lishi uchun 12 va 3 ni almashtiring.
[7, 9, 11, 3, 12]
Boshqa almashtirishlar kerak bo‘lmaguncha takrorlang va siz tartiblangan massivni olasiz:
Python-da Bubble Sort-ni qo‘llang
Python-da Bubble Sort algoritmini amalga oshirish uchun bizga kerak:
- Saralash uchun qiymatlari bo‘lgan massiv.
- Agar birinchi qiymat keyingi qiymatdan yuqori bo‘lsa, massivdan o‘tadigan va qiymatlarni almashtiradigan ichki sikl. Bu sikl har safar ishlaganda bir kam qiymatdan o‘tishi kerak.
- Ichki pastadir necha marta ishlashi kerakligini boshqaradigan tashqi sikl. n qiymatli massiv uchun bu tashqi sikl n-1 marta ishlashi kerak.
Olingan kod quyidagicha ko‘rinadi:
Misol
Pythonda qabariqni saralash algoritmini yarating:
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(n-1):
for j in range(n-i-1):
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]
print(mylist)
Misolni ishga tushirish »
Pufakcha tartibni yaxshilash
Bubble Sort algoritmi biroz yaxshilanishi mumkin.
Tasavvur qiling-a, massiv deyarli tartiblangan, boshida eng past raqamlar bilan, masalan:
mylist = [7, 3, 9, 12, 11]
Bunday holda, massiv birinchi ishga tushirilgandan keyin saralanadi, lekin Bubble Sort algoritmi elementlarni almashtirmasdan ishlashda davom etadi va bu shart emas.
Agar algoritm hech qanday qiymatlarni almashtirmasdan massivdan bir marta o‘tib ketsa, massiv tartiblangan bo‘lishi kerak va biz algoritmni quyidagicha to‘xtatishimiz mumkin:
Misol
Improved Bubble Sort algorithm:
mylist = [7, 3, 9, 12, 11]
n = len(mylist)
for i in range(n-1):
swapped = False
for j in range(n-i-1):
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]
swapped = True
if not swapped:
break
print(mylist)
Misolni ishga tushirish »
Pufakchani saralash vaqtining murakkabligi
Bubble Sort algoritmi massivdagi har bir qiymatni yonidagi qiymat bilan taqqoslab, aylanib chiqadi. Shunday qilib, \(n\) qiymatlar massivi uchun bitta siklda \(n\) shunday taqqoslashlar bo‘lishi kerak.
Va bir sikldan keyin massiv qayta-qayta \(n\) marta aylantiriladi.
Bu shuni anglatadiki, jami \(n \cdot n\) taqqoslashlar mavjud, shuning uchun Bubble Sort uchun vaqt murakkabligi: \( O(n^2) \)
Bubble Sort vaqt murakkabligini tavsiflovchi grafik quyidagicha ko‘rinadi:
Ko‘rib turganingizdek, massiv hajmi kattalashganda ish vaqti juda tez oshadi.
Yaxshiyamki, bundan ham tezroq saralash algoritmlari mavjud, masalan Tez tartiblash, biz ularni keyinroq ko‘rib chiqamiz.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!