Eklemeli Sıralama

#Nasıl çalışır?

Eklemeli sıralama (insertion sort), elindeki iskambil kâğıtlarını sıraya dizmeye benzer: her yeni kartı, zaten sıralı olan kartların arasında doğru yere sokarsın.

Dizinin sol kısmı her zaman kendi içinde sıralıdır. Sıradaki eleman (key) alınır; solundaki kendisinden büyük elemanlar birer sağa kaydırılır ve key açılan boşluğa yerleştirilir.

Dizi neredeyse sıralıysa çok az kaydırma gerekir. Bu yüzden insertion sort pratikte küçük ve neredeyse sıralı dizilerde çok hızlıdır.

#Canlı animasyon

for i = 1 to n - 1
  key = a[i]; j = i - 1
  while j >= 0 and a[j] > key
    a[j + 1] = a[j]; j = j - 1
  a[j + 1] = key

#Adım adım

1. 01İkinci elemandan başla; ilk eleman tek başına sıralı bir kısımdır.
2. 02Sıradaki elemanı (key) al.
3. 03Solundaki sıralı kısımda key'den büyük olan elemanları birer sağa kaydır.
4. 04Kendisinden küçük ya da eşit bir elemana veya dizinin başına gelince key'i boşluğa yerleştir.
5. 05Bir sonraki elemanla devam et; son eleman da yerleşince dizi sıralanmıştır.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def insertion_sort(a: list[int]) -> None:
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # Shift larger elements of the sorted part one place right.
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key


numbers = [5, 1, 4, 2, 8, 3]
insertion_sort(numbers)
print(*numbers)

#Karmaşıklık

Dizi zaten sıralıysa her eleman tek karşılaştırmayla yerinde kalır: toplam n-1 karşılaştırma, yani O(n). Ters sıralı dizide her eleman en başa kadar kaydırılır ve yaklaşık n²/2 işlem gerekir. Eşit elemanları birbirinin önüne geçirmediği için kararlıdır.

#Ne zaman kullanılır?

Küçük dizilerde (birkaç düzine elemana kadar) ve neredeyse sıralı verilerde en iyi seçeneklerden biridir. Bu yüzden Timsort gibi gerçek dünyadaki hibrit algoritmalar küçük parçaları insertion sort ile sıralar. Veri parça parça geldiğinde (online) de kullanışlıdır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Birleştirmeli Sıralama
• Shell Sort