Saralash algoritmlari: pufakchali saralash

Saralash — elementlarni biror qoida bo‘yicha, masalan, o‘sish yoki kamayish tartibida joylashtirish. Tartiblangan ma’lumotlarda kerakli elementni topish ancha tez bo‘ladi, ro‘yxatlarni o‘qish ham qulaylashadi. Saralashning ko‘p usullari bor; eng sodda va tushunarlisi — pufakchali saralash. Python’da massiv vazifasini ro‘yxat (list) bajaradi.

Pufakchali saralash g‘oyasi shunday: qo‘shni ikki elementni solishtiring va ular noto‘g‘ri tartibda bo‘lsa, o‘rnini almashtiring. Massiv bo‘ylab boshidan oxirigacha bir marta shunday o‘tganda eng katta element oxiriga “suzib chiqadi” — xuddi suvdagi pufakcha kabi. Keyingi o‘tishda oxirgi element endi tekshirilmaydi, chunki u o‘z joyida turibdi; shu tarzda har safar tekshiriladigan qism bittaga qisqaradi.

Massiv 5 2 4 1 bo‘lsin. 1-o‘tishdan keyin u 2 4 1 5 ga, 2-o‘tishdan keyin 2 1 4 5 ga, 3-o‘tishdan keyin 1 2 4 5 ga aylanadi. Python’da qo‘shnilarni solishtirish if a[j] > a[j + 1] bilan, almashtirish esa a[j], a[j + 1] = a[j + 1], a[j] bilan yoziladi; bu amallar ichma-ich ikkita for sikli ichida takrorlanadi. Agar biror o‘tishda birorta ham almashtirish bo‘lmasa, massiv allaqachon tartiblangan va jarayonni to‘xtatish mumkin.

n ta elementni saralash uchun taxminan n(n − 1)/2 ta solishtirish kerak, ya’ni vaqt n² ga mutanosib o‘sadi. 1000 ta element uchun bu qariyb 500 ming, 10 000 ta uchun esa qariyb 50 million solishtirish. Shuning uchun pufakchali saralash o‘rganish uchun yaxshi, katta ma’lumotlar uchun esa samarasiz. Amalda Python’ning tayyor sorted() va list.sort() funksiyalaridan foydalaniladi: ular ancha tez algoritm (Timsort) asosida ishlaydi.

Asosiy xulosalar

• Saralash elementlarni o‘sish yoki kamayish tartibida joylashtiradi.
• Pufakchali saralash qo‘shni elementlarni solishtirib, noto‘g‘ri tartibdagilarini almashtiradi.
• Har bir o‘tishda eng katta element o‘z joyiga — oxirgisiga — chiqadi.
• Almashtirish bo‘lmagan o‘tish massiv tartiblanganini bildiradi va jarayonni to‘xtatish mumkin.
• Taxminan n(n − 1)/2 solishtirish kerak, shuning uchun usul katta massivlarda sekin.