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:
🟢 Sıralı Kısım | 🔴 Yerleştirilecek Kart | ⬜ Sıralanmamış Kısım
| 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ı |