DSA Selection Sort (tanlab saralash)

Selection Sort

Selection Sort algoritmi massivdagi eng kichik qiymatni topadi va uni massiv boshiga o‘tkazadi.

Algoritm massivni qayta-qayta ko‘rib chiqib, navbatdagi eng kichik qiymatlarni oldinga o‘tkazadi va bu massiv saralanguncha davom etadi.

Selection Sort algoritmini va uni o‘zingiz qanday amalga oshirishni to‘liq tushunish uchun o‘qishda davom eting.

Qo‘lda bajarib ko‘rish

Selection Sort algoritmini dasturlash tilida amalga oshirishdan oldin, g‘oyani tushunib olish uchun qisqa massiv bo‘ylab faqat bir marta qo‘lda o‘tib chiqaylik.

1-qadam: Saralanmagan massivdan boshlaymiz.

2-qadam: Massivni bittadan qiymat bo‘yicha ko‘rib chiqamiz. Qaysi qiymat eng kichik? 3, to‘g‘rimi?

3-qadam: Eng kichik qiymat — 3 ni massiv boshiga o‘tkazamiz.

4-qadam: 7 dan boshlab qolgan qiymatlarni ko‘rib chiqamiz. 7 eng kichik qiymat va u allaqachon massiv boshida turibdi, shuning uchun uni ko‘chirishimiz shart emas.

5-qadam: Massivning qolgan qismini ko‘rib chiqamiz: 12, 9 va 11. Eng kichik qiymat — 9.

6-qadam: 9 ni oldinga o‘tkazamiz.

7-qadam: 12 va 11 ni ko‘rib chiqamiz, ulardan eng kichigi — 11.

8-qadam: Uni oldinga o‘tkazamiz.

Nihoyat, massiv saralandi.

Yuqoridagi qadamlarni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Algoritmni to‘liq tushunishimiz va uni dasturlash tilida amalga oshira olishimiz uchun yuqorida nima sodir bo‘lganini tushunib olishimiz kerak.

Eng kichik qiymat — 3 ga nima bo‘lganini ko‘ryapsizmi? 3-qadamda u massiv boshiga, ya’ni o‘z joyiga o‘tkazildi, ammo o‘sha qadamda massivning qolgan qismi saralanmaganicha qoldi.

Shunday qilib, Selection Sort algoritmi massiv bo‘ylab qayta-qayta o‘tishi kerak va har safar navbatdagi eng kichik qiymat massivning saralanmagan qismi oldiga, ya’ni o‘zining to‘g‘ri o‘rniga o‘tkaziladi. Saralash eng katta qiymat — 12 massiv oxirida qolguncha davom etadi. Demak, 5 ta qiymatli massivni saralash uchun massiv bo‘ylab 4 marta o‘tishimiz kerak.

Algoritm massiv bo‘ylab har safar o‘tganda massivning qolgan saralanmagan qismi qisqarib boradi.

Endi o‘rganganlarimizdan foydalanib, Selection Sort algoritmini dasturlash tilida amalga oshiramiz.

Selection Sort’ni amalga oshirish

Selection Sort algoritmini dasturlash tilida amalga oshirish uchun bizga quyidagilar kerak:

1. Saralanadigan qiymatlarga ega massiv.
2. Massiv bo‘ylab o‘tadigan, eng kichik qiymatni topadigan va uni massiv boshiga o‘tkazadigan ichki sikl. Bu sikl har safar bajarilganda bitta kamroq qiymat bo‘ylab o‘tishi kerak.
3. Ichki sikl necha marta bajarilishi kerakligini boshqaradigan tashqi sikl. \(n\) ta qiymatli massiv uchun bu tashqi sikl \(n-1\) marta bajarilishi kerak.

Natijaviy kod quyidagicha ko‘rinadi:

my_array = [64, 34, 25, 5, 22, 11, 90, 12]

n = len(my_array)
for i in range(n-1):
    min_index = i
    for j in range(i+1, n):
        if my_array[j] < my_array[min_index]:
            min_index = j
    min_value = my_array.pop(min_index)
    my_array.insert(i, min_value)

print("Sorted array:", my_array)

Selection Sort’dagi siljitish muammosi

Selection Sort algoritmini yana biroz takomillashtirish mumkin.

Yuqoridagi kodda eng kichik qiymatli element o‘chiriladi, so‘ngra massiv boshiga qo‘yiladi.

Har safar navbatdagi eng kichik qiymatli massiv elementi o‘chirilganda, o‘chirilgan element o‘rnini to‘ldirish uchun undan keyingi barcha elementlar bir pozitsiya pastga siljitilishi kerak.

Bu siljitish amallari ko‘p vaqt oladi, bu hali hammasi ham emas! Eng kichik qiymat (5) topilib o‘chirilgandan so‘ng, u massiv boshiga qo‘yiladi, bu esa quyidagi rasmda ko‘rsatilganidek, yangi qiymatga joy bo‘shatish uchun keyingi barcha qiymatlarning bir pozitsiya yuqoriga siljishiga sabab bo‘ladi.

Yechim: qiymatlarni almashtiring!

Barcha siljitishlar o‘rniga, quyida ko‘rsatilganidek, eng kichik qiymatni (5) birinchi qiymat (64) bilan almashtiring.

Qiymatlarni yuqoridagi rasmda ko‘rsatilganidek almashtirishimiz mumkin, chunki eng kichik qiymat to‘g‘ri pozitsiyaga tushadi, u bilan almashtirilayotgan boshqa qiymatni qayerga qo‘yishimizning esa ahamiyati yo‘q, chunki u hali saralanmagan.

Quyida almashtirishdan foydalanadigan ushbu takomillashtirilgan Selection Sort qanday ishlashini ko‘rsatuvchi simulyatsiya keltirilgan:

Quyida almashtirishdan foydalanadigan takomillashtirilgan Selection Sort’ning amalga oshirilishi keltirilgan:

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(n):
    min_index = i
    for j in range(i+1, n):
        if my_array[j] < my_array[min_index]:
            min_index = j   
    my_array[i], my_array[min_index] = my_array[min_index], my_array[i]

print("Sorted array:", my_array)

Selection Sort’ning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Selection Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Selection Sort \(n\) ta qiymatli massivni saralaydi.

O‘rtacha har bir siklda eng kichik qiymatni topish uchun taxminan \(\frac{n}{2}\) ta element taqqoslanadi.

Selection Sort esa eng kichik qiymatni topish siklini taxminan \(n\) marta bajarishi kerak.

Quyidagi vaqt murakkabligini olamiz:

\[ O( \frac{n}{2} \cdot n) = \underline{\underline{O(n^2)}} \]

Selection Sort algoritmining vaqt murakkabligini grafikda quyidagicha tasvirlash mumkin:

Ko‘rib turganingizdek, bajarilish vaqti Bubble Sort’dagi bilan bir xil: massiv hajmi oshirilganda bajarilish vaqti juda tez ortadi.

Quyidagi simulyatsiyani turli o‘lchamdagi massivlar uchun ishga tushiring.

Qizil punktir chiziq nazariy vaqt murakkabligi \(O(n^2)\) ni ifodalaydi.

Simulyatsiyani ishga tushirganingizda ko‘k xochlar paydo bo‘ladi. Ko‘k xochlar ma’lum o‘lchamdagi massivni saralash uchun qancha amal kerakligini ko‘rsatadi.

Ushbu simulyatsiyada ko‘rishimiz mumkin bo‘lgan Bubble Sort’dan eng muhim farq shundaki, Selection Sort uchun eng yaxshi va eng yomon holatlar amalda deyarli bir xil (\(O(n^2)\)), Bubble Sort uchun esa eng yaxshi holatdagi bajarilish vaqti atigi \(O(n)\).

Selection Sort uchun eng yaxshi va eng yomon holatlar o‘rtasidagi farq asosan almashtirishlar sonida. Eng yaxshi holatda Selection Sort hech bir qiymatni almashtirishi shart emas, chunki massiv allaqachon saralangan. Eng yomon holatda esa massiv allaqachon saralangan, lekin teskari tartibda bo‘ladi, shuning uchun Selection Sort massivda qancha qiymat bo‘lsa, shuncha almashtirish bajarishi kerak.