Urganch Davlat Universiteti 202-“kidt” guruhi tolibi Boltaboyev Jamshidning algaritmlar va berilganlar strukturasi fanidan tayyorlagan mustaqil ishi mavzu: Bubble Sort (Pufaksimon saralash) algoritmi


Download 139.97 Kb.
bet1/2
Sana22.04.2022
Hajmi139.97 Kb.
#648601
  1   2
Bog'liq
Jamshid Boltaboyev
Sobirova Sevara O\'KTAMOVNA, Floyda algoritmi-uz, 2 5258426772294211085, Amaliyot Choriyev Q.




Urganch Davlat Universiteti
202-“KIDT” guruhi tolibi Boltaboyev Jamshidning algaritmlar va berilganlar strukturasi fanidan tayyorlagan


MUSTAQIL ISHI


Mavzu: Bubble Sort (Pufaksimon saralash) algoritmi

2022y
Bubble sort~~~, baʼzan choʻkuvchi saralash deb ham ataladi, bu oddiy tartiblash algoritmi boʻlib, u roʻyxat boʻylab qayta-qayta qadam bosadi, qoʻshni elementlarni taqqoslaydi va agar ular notoʻgʻri tartibda boʻlsa, ularni almashtiradi. Ro'yxat bo'yicha o'tish ro'yxat tartiblashtirilgunga qadar takrorlanadi. Taqqoslash turi bo'lgan algoritm kichikroq yoki kattaroq elementlarning ro'yxatning yuqori qismiga "qabariq" chiqishi uchun nomlangan.

Ushbu oddiy algoritm real dunyoda foydalanishda yomon ishlaydi va birinchi navbatda ta'lim vositasi sifatida ishlatiladi. Python va Java kabi mashhur dasturlash tillariga o'rnatilgan saralash kutubxonalari tomonidan tezkor saralash, timsort yoki birlashtirish kabi samaraliroq algoritmlar qo'llaniladi.


Pufakchali saralashning boshqa koʻpgina algoritmlarga nisbatan birdan-bir muhim afzalligi, hatto tezkor saralash, lekin qoʻshish tartibida emas, bu roʻyxatning tartiblanganligini samarali aniqlash qobiliyatining algoritmga oʻrnatilganligidir. Ro'yxat allaqachon tartiblangan bo'lsa (eng yaxshi holat), qabariqli tartiblashning murakkabligi faqat {\displaystyle O(n)}O(n) ga teng. Aksincha, ko'pchilik boshqa algoritmlar, hatto o'rtacha kattalikdagi murakkabligi yaxshiroq bo'lganlar ham, to'plamda butun saralash jarayonini bajaradi va shuning uchun murakkabroqdir. Biroq, qo'shish tartibi nafaqat bu afzalliklarga ega, balki u sezilarli darajada saralangan ro'yxatda ham yaxshiroq ishlaydi (kam sonli inversiyalarga ega). Bundan tashqari, agar bu xatti-harakat so'ralsa, uni algoritm ishga tushishidan oldin ro'yxatni tekshirish orqali boshqa har qanday algoritmga qo'shish mumkin.



Bosqichma-bosqich misol
“5 1 4 2 8” raqamlari massivini oling va pufakchali tartiblash yordamida massivni eng kichik sondan eng katta raqamga tartiblang. Har bir bosqichda qalin harf bilan yozilgan elementlar taqqoslanadi. Uchta o'tish kerak bo'ladi;

Birinchi o'tish


( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Bu yerda algoritm dastlabki ikki elementni taqqoslaydi va 5 > 1 dan keyin almashinadi.
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 dan beri almashtirish
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 dan beri almashtirish
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Endi bu elementlar tartibda boʻlgani uchun (8 > 5), algoritm ularni almashtirmaydi.
Ikkinchi o'tish
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), 4 > 2 dan beri almashtirish
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
Endi massiv allaqachon tartiblangan, lekin algoritm uning tugallanganligini bilmaydi. Algoritm tartiblanganligini bilish uchun hech qanday almashishsiz qo'shimcha bitta to'liq o'tish kerak.

Uchinchi Pass


( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )


Download 139.97 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling