Insertion Sort — kartalar o'yinidagi kabi: har yangi kartani allaqachon tartiblangan qismga to'g'ri joyiga qo'yadi.
G'oya:
Keling, algoritmni vizual ko'raylik:
Misol: [12, 11, 13, 5, 6]
Tasavvur qiling: chap tomon — tartiblangan qism, o'ng tomon — tartiblanmagan qism. Har qadamda o'ng tomondan bitta elementni olib, chap tomondagi to'g'ri joyga qo'yamiz.
1-qadam: 12 allaqachon tartiblangan. Navbatdagi element 11. 11 < 12, shuning uchun 12 ni o'ngga suramiz va 11 ni boshiga qo'yamiz → [11, 12, | 13, 5, 6]
2-qadam: Navbatdagi 13. 13 > 12 — allaqachon to'g'ri joyda, hech narsa o'zgarmaydi → [11, 12, 13, | 5, 6]
3-qadam: Navbatdagi 5. 5 < 13, 5 < 12, 5 < 11 — hammani o'ngga suramiz, 5 eng boshiga o'tadi → [5, 11, 12, 13, | 6]
4-qadam: Navbatdagi 6. 6 < 13, 6 < 12, 6 < 11 — ularni o'ngga suramiz, 6 ni 5 dan keyin qo'yamiz → [5, 6, 11, 12, 13]
Python kodi:
sonlar = [12, 11, 13, 5, 6]
for i in range(1, len(sonlar)):
kalit = sonlar[i] # hozirgi element
j = i - 1
# Kalitdan katta elementlarni bir o'ringa o'ngga siljit
while j >= 0 and sonlar[j] > kalit:
sonlar[j + 1] = sonlar[j]
j -= 1
# Kalitni to'g'ri joyiga qo'y
sonlar[j + 1] = kalit
print(sonlar) # [5, 6, 11, 12, 13]Keling, kodning qanday ishlashini qadam-baqadam ko'rib chiqamiz:
Insertion Sort deyarli tartiblangan listlarda O(n) ga yaqin ishlaydi — boshqa ikkita algoritmdan ancha tez!
Keyingi darsda biz uchala algoritmni batafsil solishtiramiz va qaysi birini qachon tanlash kerakligini ko'rib chiqamiz.
Insertion Sort ni amalga oshirish
Dastur yozing:
12 11 13 5 6)