Insertion Sort algoritmi

[codex]

Insertion Sort sadə və asan başa düşülən sıralama alqoritmlərindən biridir. Bu alqoritm son sıralanmış massivi bir elementi digərinin ardınca yerbəyer etməklə qurur. Quicksort, Heapsort və Merge Sort kimi daha mürəkkəb alqoritmlərlə müqayisədə böyük listlərdə daha az effektivdir. Lakin bəzi üstünlüklərə malikdir:

1. Sadədir – asan başa düşülür və tətbiq edilir.
2. Kiçik və demək olar ki, sıralanmış listlərdə yaxşı performans göstərir.
3. Yerində sıralama (in-place sort) alqoritmidir, yəni əlavə yaddaş tələb etmir.

Bu alqoritmin zaman mürəkkəbliyi:

• Ən pis və orta hallarda: O(n²)
• Ən yaxşı halda (əgər massiv artıq sıralanıbsa): O(n)

---

İnsertion Sort-un işləmə mexanizmi

1. Xarici dövrü (outer loop) başlat – i = 1-dən başlayaraq massiv sonuna qədər iterasiya et.
2. İki dəyişən müəyyən et:
   • current – cari elementin (arr[i]) dəyərini saxlayır.
   • j – i-1 dəyərinə bərabər olan indeksdir.
3. Daxili while dövrü başlat və aşağıdakı şərtləri yoxla:
   • j >= 0 olduqda və
   • arr[j] current-dən böyük olduqda.
4. Əgər şərt ödənirsə:
   • arr[j+1] = arr[j] – yəni j indeksində olan elementi sağa ötür.
   • j dəyərini bir vahid azaldır.
5. Xarici dövrün sonunda arr[j+1] current dəyərinə bərabər edilir.
6. Sonda sıralanmış massivi qaytarır.

---

Həlli (JavaScript)

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let currentElement = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > currentElement) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = currentElement;
  }

  return arr;
}

Bu funksiya yerində (in-place) sıralama aparır və əlavə yaddaş istifadə etmir. Kiçik massivlər üçün ideal seçimdir.

---

Video izahı (ingiliscə)

---

Vizual izahı

---

Əgər sadə, asan başa düşülən və kiçik massivlər üçün effektiv bir sıralama alqoritmi axtarırsınızsa, Insertion Sort yaxşı seçim ola bilər. Lakin böyük massivlər üçün Quicksort və Merge Sort kimi daha optimallaşdırılmış alqoritmlər tövsiyə olunur.