Insertion Sort (Eklemeli Sıralama) algoritması, liste üzerinde yerinde sıralama yapmak için kullanılan basit bir algoritmadır. Yavaş çalışmasına rağmen, küçük veri kümeleri üzerinde oldukça etkilidir. İşte algoritmanın ayrıntılı açıklaması:

İlk Bakış

Insertion Sort, ellerinizle oyun kartlarını sıralarken yaptığınıza benzer bir şekilde çalışır. Sıralı bir listeye eleman eklemek istediğinizi düşünün. Yeni eklenen elemanı doğru yere koymak için mevcut sıralı listeyi tararsınız.

Algoritmanın Adımları

İlk Elemanı Sıralı Olarak Kabul Et: İlk eleman, tek başına sıralı olarak kabul edilir, çünkü tek başına bir liste her zaman sıralıdır.

Sonraki Elemanı İncele: İlk elemandan sonra gelen elemanı alın ve bu elemanı, zaten sıralı olan önceki elemanlar arasında uygun yere koymak üzere "ana" listenin geri kalanıyla karşılaştırın.

Elemanı Doğru Yere Yerleştir: Şu anki elemanı, uygun yere yerleştirin. Bu, şu anki elemanın daha küçük olduğu ilk elemanın soluna yerleştirilmesi anlamına gelir.

Tüm Listeyi İnceleyin: Listenin sonuna kadar bu işlemi tekrar edin.

Sonuç: Liste sıralanmış olur.

Python'da Örnek Kod

def insertion_sort(arr):
    # 1. elemandan başlayarak listenin sonuna kadar gidilir
    for i in range(1, len(arr)):
        # i. elemanı anahtar olarak al (şu anda sıralanacak olan eleman)
        key = arr[i]
        # Anahtarın solundaki elemana göre pozisyonu kontrol et
        j = i - 1
        # j pozitif olduğu ve anahtar, j'nin solundaki elemandan küçük olduğu sürece
        while j >= 0 and key < arr[j]:
            # j'nin solundaki elemanı bir sağa kaydır
            arr[j + 1] = arr[j]
            # j'yi azaltarak sol elemana geç
            j -= 1
        # Anahtarı doğru konuma yerleştir (j'nin bir sağında)
        arr[j + 1] = key
    # Sıralanmış diziyi döndür
    return arr

Örnek olarak, [4, 3, 2, 1] dizisi düşünün:

• İlk adımda, 4 zaten sıralı.
• İkinci adımda, 3 alınır ve 4'ün soluna eklenir, böylece [3, 4, 2, 1] olur.
• Üçüncü adımda, 2 alınır ve 3'ün soluna eklenir, böylece [2, 3, 4, 1] olur.
• Dördüncü adımda, 1 alınır ve 2'nin soluna eklenir, böylece [1, 2, 3, 4] olur.

Her adımda, yeni elemanın doğru yere eklenmesi, listenin o elemana kadar olan kısmının sıralı olmasını sağlar. Bu nedenle, bu algoritmaya "Insertion Sort" veya Türkçe'de "Eklemeli Sıralama" denir.

Zaman Karmaşıklığı

En İyi Durum: Eğer liste zaten sıralıysa, her elemanın sadece bir kez kontrol edilmesi gerekir, bu da O(n) zaman karmaşıklığına sahip olmasını sağlar.

Ortalama ve En Kötü Durum: Ortalama ve en kötü durumlar için zaman karmaşıklığı O(n²)'dir.

Uygulama Alanları

Insertion Sort, küçük veri kümeleri üzerinde veya neredeyse sıralı veri kümelerinde etkilidir. Daha büyük veri kümelerinde ise genellikle çok yavaş çalışır, bu nedenle daha etkili sıralama algoritmaları kullanılması tercih edilir.