Kif 611. 22 guruh talabasi Turdimuhammadova durdona

Kif 611. 22 guruh talabasi Turdimuhammadova durdona

Malumotlar tuzilmasi va algoritimlar

BUBBLE SORT

BUBBLE SORT

PUFAKCHA USULI

“Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous.

“Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous.

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.

1 - rasm

1-rasm uchun

Bu usulning g’oyasi: ro’yxat elementlari quyidan yuqoriga (oxirgi elementdan birinchi elementga) yo’nalishida qiymatlarning har biri jufti bilan taqqoslanadi. Agar quyidagi element qiymati yuqoridagi jufti qiymatidan kichik bo’lsa, u holda ularning o’rni almashtiriladi va h.k. (6.3-rasm). Ya’ni, Pufakchali saralashning asosiy g’oyasi ro’yxatning kichik qiymatli elementlarini ro’yxatning yuqori qismiga chiqarish, shu vaqtning o’zida katta qiymatli elementlarini esa quyi qismiga tushurishdan iborat.

Pufakcha saralashda ro’yxat bo’yicha bir necha o’tishlar bajariladi.

Pufakcha saralashda ro’yxat bo’yicha bir necha o’tishlar bajariladi.

Har bir o’tishda qo’shni elementlar taqqoslanadi. Agar qo’shni

elementlar noto’g’ri tartibda joylashgan bo’lsa, u holda qo’shni

elementlar o’rni almashtiriladi.

Har bir o’tish ro’yxat boshidan boshlanadi. Dastlab 1 va 2, keyin 2 va

3, keyin 3 va 4-o’rindagi elementlar taqqoslanadi va h.k. Noto’g’ri

tartibli elementlar jufti almashtiriladi.

Birinchi o’tishda eng katta element topilsa,

Birinchi o’tishda eng katta element topilsa,

shu element ro’yxat oxiriga qadar barcha keyingi elementlar bilan

taqqoslanadi va o’rni almashtiriladi. Shuning uchun ikkinchi o’tishda

ro’yxatning so’ngi elementi bilan taqqoslash shart bo’lmaydi. 2-o’tishda

kattaligi bo’yicha 2-element ro’yxatning oxiridan 2-o’ringa tushadi. Agar biror o’tishda

bitta ham elementlar juftining o’rni almashtirilishi bajarilmasa, u holda algoritm ishini

tugallash mumkin.

E’tiboringiz uchun rahmat!!!