“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Almashtirish orqali saralash (Pufaksimon)
Algoritm g’oyasi
n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo‘lsa, u holda ular o‘rni almashtiriladi.
Misol:
Harakat tamoyili oddiy: biz massivni boshidan oxirigacha ko’rib chiqamiz, bir vaqtning o'zida saralanmagan qo'shni elementlarni almashtiramiz. Birinchi o'tish natijasida maksimal element oxirgi o'ringa “suzib chiqadi". Endi biz yana massivning saralanmagan qismini (birinchi elementdan oxirgi elementgacha) ko’rib chiqamiz va yo'lda saralanmagan qo'shnilarni o'zgartiramiz. Ikkinchi eng katta element oxirgidan oldingi joyda joylashadi. Xuddi shu ruhda davom etib, biz massivning doimiy ravishda kamayib borayotgan saralanmagan qismini ko’rib o'tamiz, topilgan maksimal elementlarni oxiriga surib boramiz.
Element suvdagi pufakcha kabi kerakli holatga “suzib chiqadi" - shuning uchun algoritm nomi pufaksimon saralash deyiladi.
Almashtirish orqali saralash algoritmi tahlili
Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
Taqqoslashlar soni:
O‘rinlashtirishlar soni:
Saralashga ketgan vaqt:
Ushbu algoritmning o'ziga xos xususiyati quyidagidan iborat: ichki tsikl birinchi marta tugallangandan so'ng, massivning maksimal elementi doimo N-pog'onada bo'ladi. Ikkinchi o'tishda keyingi eng katta element N-1 o'rinda. Va hokazo. Shunday qilib, har bir keyingi o'tishda qayta ishlanadigan elementlar soni 1 ga kamayadi va har safar butun massivni boshidan oxirigacha “qarab chiqish" shart bo’lmaydi.

4

5

2

1

3

4

5

2

1

3

4

5