Insertion Sort: Detaylı Anlatım ve Örnekler

Insertion Sort: Detaylı Anlatım ve Örnekler

Merhaba! Fatih Soysal olarak, bugün size oldukça yaygın ve anlaşılır bir sıralama algoritması olan Insertion Sort’u detaylı bir şekilde anlatacağım. Bu algoritma, özellikle küçük veri kümeleri için oldukça etkilidir ve öğrenmesi kolaydır. Öncelikle algoritmanın mantığını kavrayalım, ardından kod örnekleri ve performans analizine geçeceğiz.

Insertion Sort Mantığı

Insertion Sort, bir kart destesi sıralarken kullandığımız yönteme benzer şekilde çalışır. Elimizde sıralanmamış bir dizi elemanımız olduğunu düşünelim. Algoritma, her bir elemanı alır ve bu elemanın doğru sıralanmış konumunu bulmak için önündeki sıralı kısımda yerini arar. Bunu yaparken, daha büyük elemanları birer birer bir adım sağa kaydırarak yer açar ve ardından elemanı doğru yerine yerleştirir.

Örneğin, [5, 2, 4, 6, 1, 3] dizisini ele alalım. Algoritma şu şekilde ilerler:

1. [5] – İlk eleman zaten sıralı.
2. [2, 5] – 2, 5’ten küçük olduğu için 5 bir adım sağa kaydırılır ve 2 başa yerleştirilir. Sıralı dizi: [2, 5]
3. [2, 4, 5] – 4, 5’ten küçük, ancak 2’den büyük. Dolayısıyla 5 sağa kaydırılır ve 4, 2’nin yanına yerleştirilir. Sıralı dizi: [2, 4, 5]
4. [2, 4, 5, 6] – 6 zaten en büyük, dolayısıyla sıraya eklenir. Sıralı dizi: [2, 4, 5, 6]
5. [1, 2, 4, 5, 6] – 1, hepsinden küçük olduğu için başa yerleştirilir. Sıralı dizi: [1, 2, 4, 5, 6]
6. [1, 2, 3, 4, 5, 6] – 3, 4’ten küçük, 2’den büyük olduğu için 4 sağa kaydırılır ve 3 doğru yerine yerleştirilir. Sıralı dizi: [1, 2, 3, 4, 5, 6]

Sonuç olarak, dizi tamamen sıralanmış olur.

Kod Örneği (Python)

def insertion_sort(dizi):
  for i in range(1, len(dizi)):
    anahtar = dizi[i]
    j = i-1
    while j >= 0 and anahtar < dizi[j]:
      dizi[j+1] = dizi[j]
      j -= 1
    dizi[j+1] = anahtar
  return dizi

dizi = [5, 2, 4, 6, 1, 3]
sirali_dizi = insertion_sort(dizi)
print(f"Sıralanmış dizi: {sirali_dizi}")

Performans Analizi

Insertion Sort'un zaman karmaşıklığı, en kötü ve ortalama durumlarda O(n²) iken, en iyi durumda (zaten sıralı bir dizi) O(n)'dir. Bu nedenle, büyük veri kümeleri için pek uygun değildir. Ancak, küçük veri kümeleri veya neredeyse sıralı diziler için oldukça etkilidir. Ayrıca, yerinde sıralama (in-place sorting) algoritması olduğundan, ekstra bellek kullanımı gerektirmez.

Daha fazla algoritma ve yazılım geliştirme konularında bilgi edinmek için web sitemi ziyaret edebilirsiniz.

Bu konuda faydalı bulabileceğiniz başka bir kaynak: GeeksforGeeks Insertion Sort

Umarım bu makale size Insertion Sort algoritmasını daha iyi anlamanıza yardımcı olmuştur. Herhangi bir sorunuz varsa lütfen bana ulaşmaktan çekinmeyin.

#Etiketler: Insertion Sort, Sıralama Algoritmaları, Python, Zaman Karmaşıklığı, Algoritma Analizi, Veri Yapıları, Programlama