Kart Oyununda El Düzenleme Mantığı
Insertion Sort, her elemanı sıralı bölümde doğru yerine "sokan" bir algoritmadır. Kart oyunlarında elimizdeki kartları düzenleme mantığına benzer.
İskambil oynarken:
Insertion Sort, tıpkı elinize gelen iskambil kartlarını sıraya dizme gibi çalışır. Kırmızı renkli kart şu anda yerleştirilmeye çalışılan karttır. Bu kart, yeşil (sıralı) kısımda doğru yerine konulana kadar, kendinden büyük kartlar sağa kaydırılır.
Kırmızı çizgi sıralı kısmı (sol) ve henüz sıralanmamış kısmı (sağ) ayırır. Her adımda sıralı kısım büyür, sıralanmamış kısım küçülür.
| Durum | Zaman | Açıklama |
|---|---|---|
| En İyi | O(n) | Dizi zaten sıralı - sadece n-1 karşılaştırma |
| Ortalama | O(n²) | Rastgele sıralı dizi |
| En Kötü | O(n²) | Ters sıralı dizi - her eleman en başa gider |
Neredeyse sıralı verilerde çok hızlıdır! Verinin büyük kısmı sıralıysa O(n)'e yakın çalışır. Bu nedenle küçük dizilerde veya hibrit algoritmalarda (Timsort) kullanılır.
def insertion_sort(arr):
"""
Insertion Sort Algoritması
Her elemanı sıralı bölümde doğru yerine "sokar".
"""
n = len(arr)
comparisons = 0
shifts = 0
for i in range(1, n):
key = arr[i] # Yerleştirilecek eleman
j = i - 1
print(f"\n--- Adım {i} ---")
print(f"Yerleştirilecek: {key}")
print(f"Sıralı bölüm: {arr[:i]}")
# key'den büyük elemanları sağa kaydır
while j >= 0 and arr[j] > key:
comparisons += 1
print(f" {arr[j]} > {key} → Sağa kaydır")
arr[j + 1] = arr[j]
shifts += 1
j -= 1
if j >= 0:
comparisons += 1
print(f" {arr[j]} ≤ {key} → Dur")
arr[j + 1] = key
print(f"Sonuç: {arr}")
return comparisons, shifts
# Test
dizi = [64, 34, 25, 12, 22, 11]
print(f"Başlangıç: {dizi}\n")
comp, shift = insertion_sort(dizi)
print(f"\n{'='*40}")
print(f"Sonuç: {dizi}")
print(f"Karşılaştırma: {comp}")
print(f"Kaydırma: {shift}")Python'un sort() fonksiyonu (Timsort), küçük parçaları Insertion Sort ile sıralar. Çünkü küçük dizilerde overhead'sız ve cache-friendly!
| Özellik | Bubble | Selection | Insertion |
|---|---|---|---|
| En İyi Durum | O(n) | O(n²) | O(n) |
| Takas Sayısı | O(n²) | O(n) | O(n²) |
| Stabil | ✅ | ❌ | ✅ |
| Online | ❌ | ❌ | ✅ |
| Önerilen Kullanım | Sadece öğretim | Takas maliyetli | Küçük/neredeyse sıralı |