|
Almashtirish orqali saralash (Pufaksimon)
|
| bet | 6/7 | | Sana | 19.11.2023 | | Hajmi | 20,41 Kb. | | #101203 |
Bog'liq Ma\'lumotlarni saralash algoritmlari. Saralash tushunchasi va uni-kompy.info HamdamovAyyubxon, ma\'lumotlar tuzulmasi va algaridimlar amaliy ish - 1, Ma\'lumotlar bazasi mustaqil ish -3, Mashinali o\'qitishga kirish 21-ma\'ruza Nosirov Kh, sun-iy-neyron-tarmoqlarni-umumiy-tasnifi, Mashinali o\'qitishga kirish 1-ma\'ruza Nosirov Kh (1), Asosnoma Quraqov S.A., Haydarqulov Shohzod, OR-5.51.02.02-Elektr atansiyalari tarmoqlari va tizimlari, lab5power point, Kompyuter tarmoqlari va adminstratorlash fanidan test savollari , 8-sinf mavzulashtirilgan testlar, menejment texAlmashtirish 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.
1
|
| |
