Mavzu: Pufakcha usuli bilan saralash algoritimi Reja: I. Kirish II. Bubble sort algoritmi xossalari 1.Pufakcha usuli 2. Pufakcha usulida saralash algoritmi 3.Pufakcha usulida amaliy ish III. Xulosa IV. Foydalanilgan adabiyotlar Kirish 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 jurnalida o'quvchilar familiyasi alifbo tartibiga ko'ra saralangan bo'ladi. Masalan bizga sonlar qatori berilgan: 8, 23, 0, -50, 100. Bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz mumkin. Bu saralashni amalga oshirish jarayoni Saralash algoritmi deyiladi. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Yuqoridagi sonli qatorni kichigidan kattasiga qarab tartiblaganimizda -50, 0, 8, 23, 100 ko'rinishiga keladi. Biz buni qanday amalga oshirdik. Bunda har xil usuldan foydalanish mumkin va mana

shu algoritm turlaridir Biz algoritmlardan bittasidan foydalanib yuqoridagi sonli qatorni tartiblaymiz. Avval, sonli qatordan eng kichigini topamiz va uni ro'yxatning boshiga qo'yamiz. Har bir sonni boshqasi bilan solishtirib chiqamiz. Agar son o'zidan keyingi sondan kichik bo'lsa, son shu joyida qoladi, agar katta bo'lsa sonlarning o'rnini almashtiramiz. 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) Saralangan tartib quyidagi holatga keldi: 1, 3, 22, 23, 45, 54; 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`ladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralashdan 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 sababli 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. Saralash algoritmimning turlari  Bubble sort  Selection sort  Insertion sort  Quick sort  Merge sort II. Bubble sort Pufakcha saralash, ba'zan cho'ktiruvchi saralash deb ataladi, oddiy tartiblash algoritmi bo'lib, u kiritilgan ro'yxat elementini element bo'yicha qayta-qayta bosib o'tadi, joriy elementni undan keyingisi bilan

taqqoslaydi va kerak bo'lganda ularning qiymatlarini almashtiradi. Ro yxat bo yicha bu o tishlar o tish vaqtida hech qanday almashtirish ʻ ʻ ʻ ʻ amalga oshirilmaguncha takrorlanadi, ya ni ro yxat to liq tartiblangan. ʼ ʻ ʻ Taqqoslash turi bo'lgan algoritm kattaroq elementlarni ro'yxatning yuqori qismiga ko'tarilishi uchun nomlangan. Pufakchani saralash nimaga o'xshaydi? Agar dasturchi yoki tahlilchi bir qator raqamlarni o'sish tartibida joylashtirmoqchi bo'lsa, pufakchani tartiblash usuli bu erda ko'rsatilgan misolga o'xshaydi.

Algoritm bir vaqtning o'zida ikkita elementni ko'rib chiqadi, chapdan o'ngga o'sish tartibida bo'lmaganlarni o'zgartiradi va keyin hech qanday raqamni almashtirmasdan o'tishni tugatmaguncha butun ketma-ketlikni aylanishni davom ettiradi. Bubble Sort uchun Python dasturi Bubble Sort - bu eng oddiy tartiblash algoritmi bo'lib, agar ular noto'g'ri tartibda bo'lsa, ulashgan elementlarni qayta-qayta almashtirish orqali ishlaydi. Pufakchali tartiblash ikki qo‘shni elementni solishtiradigan va ularni mo‘ljallangan tartibda bo‘lguncha almashtiradigan tartiblash algoritmidir. Yuzaga ko'tarilgan suvdagi havo pufakchalarining harakati kabi, massivning har bir elementi har bir iteratsiyada oxirigacha harakat qiladi. Shuning uchun u pufakchali turlanish deb ataladi. Pufakchali saralash algoritmining mohiyati kichik qiymatlarning ro’yxat yuqorisiga itarilib, yirik qiymatlarning ro’yxat pastiga surilishiga