Daxiletmə ilə çeşidləmə

6.1 Insertion Sort-un tərifi

Insertion Sort — bu, bir-bir element əlavə etməklə sıraya salınan massiv (və ya siyahı) yaradan sıralama alqoritmidir. Alqoritm, sıralanmamış hissədən hər bir elementi götürür və onu sıralanmış hissədə düzgün yerə yerləşdirir.

Necə işləyir:

1. Massivin ikinci elementindən başlayırıq (birinci element artıq sıralanmış hesab olunur).
2. Cari elementi əvvəlki elementlərlə müqayisə edirik və düzgün yerini tapana qədər onu sola hərəkət etdiririk.
3. Bütün massiv elementləri üçün bu prosesi təkrarlayırıq, hər yeni elementi artıq sıralanmış hissədə uyğun yerə əlavə edirik.

Insertion Sort-un vaxt və yaddaş mürəkkəbliyi

Vaxt mürəkkəbliyi:

• Ən pis halda: O(n^2) — bu halda elementlər əvvəlcədən əks sıralanıb.
• Orta halda: O(n^2) — elementlər təsadüfi qaydada yerləşəndə baş verir.
• Ən yaxşı halda: O(n) — elementlər artıq sıralanıbsa baş verir.

Yaddaş mürəkkəbliyi:

O(1) — çünki alqoritm əlavə yaddaş üçün sabit sayda dəyişən istifadə edir (yalnız bir neçə müvəqqəti dəyişən).

6.2 Alqoritmin iş prinsipi

Alqoritmin növbəti addımında belə bir vəziyyət var:

• Hazırda i indeksli elementimiz var.
• Onun solundakı bütün elementlər artıq artan sıralamada yerləşdirilib.
• Cari elementi daxil etməyə çalışırıq ki, sıralanmış hissənin sırası pozulmasın.

Sıralanmış hissəyə elementin daxil edilməsi prosesi belə görünür:

1. Dövr daxilində j dəyişəni i - 1 dən 0 a qədər dəyər alır.
2. Əgər cari (i) element j elementindən kiçikdirsə, onda j elementinin dəyərini sağa doğru sürüşdürürük.

Məsələn: cari vəziyyət:

• Yaşıl rənglə artıq sıralanmış elementlər qeyd edilib.
• Çəhrayı rənglə isə hələ sıralanmayan elementlər.
• Cari 5 indeksi olan element - qəhvəyi rəngdə qeyd edilib.

Cari elementi sıralanmış hissəyə düzgün şəkildə yerləşdirməyə çalışırıq.

Addım 1 — Cari elementin dəyərini key dəyişəni ilə yadda saxlayırıq.

Addım 2 — No4 elementi key dəyərindən böyükdür? (10 böyükdür 5?) Onda No4 elementini sağa sürüşdürürük:

Addım 3 — No3 elementi key dəyərindən böyükdür? (8 böyükdür 5?) Onda No3 elementini sağa sürüşdürürük:

Addım 4 — No2 elementi key dəyərindən böyükdür? (6 böyükdür 5?) Onda No2 elementini sağa sürüşdürürük:

Addım 5 — No1 elementi key dəyərindən böyükdür? (4 böyükdür 5?) Xeyr. Onda No2 elementi olan yerə key dəyərini yerləşdiririk.

No5 elementini doğru yerə yerləşdirdikdən sonra, No6 elementinə keçirik və onu sıralanmış hissədəki yerinə yerləşdirməyə çalışırıq:

Sonra yeddinci elementi götürürük:

Sonra 8-ci:

6.3 Qoşma çeşidləmə alqoritminin realizasiyası

Bu alqoritm Python-da belə görünür:

def insertion_sort(arr):
    # Massivin bütün elementlərini, ikinci elementdən başlayaraq keçirik
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1 # arr[0..i - 1] elementlərini, hansılar ki key-dən böyükdür, bir mövqe sağa sürüşdürürük while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1
        arr[j + 1] = key # Key-i düzgün yerə yerləşdiririk
    return arr  # Çeşidlənmiş massivi qaytarırıq
        
# İstifadə nümunəsi:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Çeşidlənmiş massiv:", sorted_arr)
# Çıxış: Çeşidlənmiş massiv: [5, 6, 11, 12, 13]

İzah:

• Hazırkı elementi key-də saxlayırıq
• Massivin çeşidlənmiş hissəsinin bütün elementlərini sağa sürüşdürürük
• Elementimizi uyğun yerə yerləşdiririk

Alqoritmin iş nümunəsi

Massiv nümunəsi götürək: [12, 11, 13, 5, 6]

1. Birinci keçid (i = 1):

• 11 ilə 12-ni müqayisə edirik, 12-ni sağa sürüşdürürük.
• Massiv: [11, 12, 13, 5, 6]

2. İkinci keçid (i = 2):

• 13 artıq yerindədir.
• Massiv: [11, 12, 13, 5, 6]

3. Üçüncü keçid (i = 3):

• 5 ilə 13, 12 və 11-i müqayisə edirik, hamısını sağa sürüşdürürük.
• Massiv: [5, 11, 12, 13, 6]

4. Dördüncü keçid (i = 4):

• 6 ilə 13, 12 və 11-i müqayisə edirik, hamısını sağa sürüşdürürük.
• Massiv: [5, 6, 11, 12, 13]

Alqoritm bitir, çünki bütün elementlər çeşidlənmiş olur.