DSA Insertion Sort (qo‘yib saralash)

Insertion Sort

Insertion Sort algoritmi massivning bir qismidan saralangan qiymatlarni, boshqa qismidan esa hali saralanmagan qiymatlarni saqlash uchun foydalanadi.

Algoritm massivning saralanmagan qismidan bittadan qiymat olib, uni massivning saralangan qismidagi to‘g‘ri joyga qo‘yadi va bu massiv saralanguncha davom etadi.

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

Qo‘lda bajarib ko‘rish

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

1-qadam: Saralanmagan massivdan boshlaymiz.

2-qadam: Birinchi qiymatni massivning boshlang‘ich saralangan qismi deb hisoblashimiz mumkin. Agar u bitta qiymatdan iborat bo‘lsa, demak, u saralangan bo‘lishi kerak, to‘g‘rimi?

3-qadam: Endi navbatdagi qiymat — 12 massivning saralangan qismidagi to‘g‘ri pozitsiyaga o‘tkazilishi kerak. Ammo 12 soni 7 dan katta, shuning uchun u allaqachon to‘g‘ri pozitsiyada turibdi.

4-qadam: Navbatdagi qiymat — 9 ni ko‘rib chiqamiz.

5-qadam: Endi 9 qiymati massivning saralangan qismidagi to‘g‘ri pozitsiyaga o‘tkazilishi kerak, shuning uchun 9 ni 7 va 12 ning orasiga o‘tkazamiz.

6-qadam: Navbatdagi qiymat — 11.

7-qadam: Uni massivning saralangan qismida 9 va 12 ning orasiga o‘tkazamiz.

8-qadam: To‘g‘ri pozitsiyaga qo‘yilishi kerak bo‘lgan oxirgi qiymat — 3.

9-qadam: 3 ni boshqa barcha qiymatlarning oldiga qo‘yamiz, chunki u eng kichik qiymat.

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.

Birinchi qiymat massivning boshlang‘ich saralangan qismi deb hisoblanadi.

Birinchi qiymatdan keyingi har bir qiymat to‘g‘ri pozitsiyaga qo‘yilishi uchun massivning saralangan qismidagi qiymatlar bilan taqqoslanishi kerak.

Insertion Sort algoritmi 5 ta qiymatli massivni saralash uchun massiv bo‘ylab 4 marta o‘tishi kerak, chunki birinchi qiymatni saralashimiz shart emas.

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

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

Insertion Sort’ni amalga oshirish

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

1. Saralanadigan qiymatlarga ega massiv.
2. Saralanadigan qiymatni tanlaydigan tashqi sikl. \(n\) ta qiymatli massiv uchun bu tashqi sikl birinchi qiymatni o‘tkazib yuboradi va \(n-1\) marta bajarilishi kerak.
3. Qiymatni qayerga qo‘yish kerakligini topish uchun massivning saralangan qismi bo‘ylab o‘tadigan ichki sikl. Agar saralanadigan qiymat \(i\) indeksida bo‘lsa, massivning saralangan qismi \(0\) indeksidan boshlanib, \(i-1\) indeksida tugaydi.

Natijaviy kod quyidagicha ko‘rinadi:

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

n = len(my_array)
for i in range(1,n):
    insert_index = i
    current_value = my_array.pop(i)
    for j in range(i-1, -1, -1):
        if my_array[j] > current_value:
            insert_index = j
    my_array.insert(insert_index, current_value)

print("Sorted array:", my_array)

Insertion Sort’ni takomillashtirish

Insertion Sort’ni yana biroz takomillashtirish mumkin.

Yuqoridagi kodda avval qiymatni o‘chirib, so‘ngra uni boshqa joyga qo‘yish usuli intuitiv jihatdan tushunarli. Masalan, qo‘lingizdagi kartalar bilan Insertion Sort’ni jismonan xuddi shunday bajargan bo‘lardingiz. Agar kichik qiymatli kartalar chap tomonga saralanayotgan bo‘lsa, siz yangi saralanmagan kartani olasiz va uni allaqachon saralangan boshqa kartalar orasidagi to‘g‘ri joyga qo‘yasiz.

Buni shu tarzda dasturlashning muammosi shundaki, massivdan qiymat o‘chirilganda undan yuqoridagi barcha elementlar bir indeks pastga siljitilishi kerak:

O‘chirilgan qiymatni massivga qayta qo‘yishda ham ko‘plab siljitish amallarini bajarish kerak bo‘ladi: qo‘yilayotgan qiymatga joy bo‘shatish uchun keyingi barcha elementlar bir pozitsiya yuqoriga siljishi kerak:

Bu siljitish amallari, ayniqsa ko‘p elementli massivlarda, ko‘p vaqt olishi mumkin.

Massivlar xotirada qanday saqlanishi haqida bu yerda batafsil o‘qishingiz mumkin.

Takomillashtirilgan yechim

Faqat zarur qiymatlarni siljitish orqali bu siljitish amallarining ko‘pchiligidan qochishimiz mumkin:

Yuqoridagi rasmda avval 7 qiymati nusxalanadi, so‘ngra 11 va 12 qiymatlari massivda bir pozitsiya yuqoriga siljitiladi va nihoyat 7 qiymati oldin 11 qiymati turgan joyga qo‘yiladi.

Bu holda siljitish amallari soni 12 tadan 2 taga kamayadi.

Bu takomillashtirish quyidagi misolda amalga oshirilgan:

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

n = len(my_array)
for i in range(1,n):
    insert_index = i
    current_value = my_array[i]
    for j in range(i-1, -1, -1):
        if my_array[j] > current_value:
            my_array[j+1] = my_array[j]
            insert_index = j
        else:
            break
    my_array[insert_index] = current_value

print("Sorted array:", my_array)

Yuqoridagi kodda, shuningdek, ichki sikldan chiqib ketiladi (break). Buning sababi, joriy qiymat uchun to‘g‘ri joyni topib bo‘lganimizdan keyin qiymatlarni taqqoslashda davom etishga hojat yo‘q.

Insertion Sort’ning vaqt murakkabligi

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

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

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

O‘rtacha har bir qiymat uni qo‘yish uchun to‘g‘ri joyni topish maqsadida taxminan \(\frac{n}{2}\) ta boshqa qiymat bilan taqqoslanishi kerak.

Insertion Sort qiymatni to‘g‘ri joyiga qo‘yish siklini taxminan \(n\) marta bajarishi kerak.

Insertion Sort uchun quyidagi vaqt murakkabligini olamiz:

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

Insertion Sort’ning vaqt murakkabligini quyidagicha tasvirlash mumkin:

Nazariy vaqt murakkabligi \(O(n^2)\) (qizil chiziq) haqiqiy Insertion Sort bajarilishlaridagi amallar soni bilan qanday solishtirilishini ko‘rish uchun quyidagi simulyatsiyadan foydalaning.

Insertion Sort uchun eng yaxshi, o‘rtacha va eng yomon holatlar o‘rtasida katta farq bor. Buni yuqoridagi turli simulyatsiyalarni ishga tushirib ko‘rishingiz mumkin.

Navbatda Quicksort. Nihoyat, tezroq saralash algoritmini ko‘ramiz!