🔄 Sıralama Algoritmaları
📋 İçindekiler
🫧 Bubble Sort
Çalışma Mantığı
Yan yana elemanları karşılaştırarak büyük elemanları sona doğru “yüzdürür”. Her turda en büyük eleman yerine yerleşir.
Adımlar
- Dizinin başından itibaren yan yana elemanları karşılaştır
- Soldaki sağdakinden büyükse yer değiştir
- Dizinin sonuna kadar devam et
- Her turda bir eleman daha yerine oturur
- Tüm dizi sıralanana kadar tekrarla
Görsel Gösterim
[5, 3, 8, 4, 2] → İlk durum
[3, 5, 4, 2, 8] → 1. tur (8 yerine oturdu)
[3, 4, 2, 5, 8] → 2. tur (5 yerine oturdu)
[3, 2, 4, 5, 8] → 3. tur
[2, 3, 4, 5, 8] → Sıralı ✓
Komplekslik
- Zaman: O(n²) - En kötü ve ortalama
- Zaman: O(n) - En iyi durum (zaten sıralıysa)
- Alan: O(1) - Yerinde sıralama
Kullanım Alanları
- Küçük veri setleri
- Eğitim amaçlı
- Neredeyse sıralı diziler için
🎯 Selection Sort
Çalışma Mantığı
Her adımda dizinin geri kalanından en küçük elemanı bulup başa yerleştirir.
Adımlar
- Sıralanmamış kısımdan en küçük elemanı bul
- Bu elemanı sıralanmamış kısmın başıyla değiştir
- Sıralı kısmı bir eleman genişlet
- Tüm dizi sıralanana kadar tekrarla
Görsel Gösterim
[64, 25, 12, 22, 11]
↓ En küçük: 11
[11 | 25, 12, 22, 64]
↓ En küçük: 12
[11, 12 | 25, 22, 64]
↓ En küçük: 22
[11, 12, 22 | 25, 64]
↓ En küçük: 25
[11, 12, 22, 25, 64] ✓
Komplekslik
- Zaman: O(n²) - Her durumda
- Alan: O(1) - Yerinde sıralama
- Değiş tokuş sayısı: O(n) - Az swap
Özellikler
- ✅ Az sayıda değiş tokuş yapar
- ✅ Basit implementasyon
- ❌ Büyük veri setlerinde yavaş
📥 Insertion Sort
Çalışma Mantığı
Kart sıralarken yaptığımız gibi, her elemanı sıralı kısımdaki doğru yerine yerleştirir.
Adımlar
- İkinci elemandan başla
- Elemanı al ve sıralı kısımla karşılaştır
- Doğru konumu bulana kadar sola kaydır
- Elemanı doğru konuma yerleştir
- Sonraki eleman için tekrarla
Görsel Gösterim
[5 | 2, 4, 6, 1, 3] → 5 sıralı
[2, 5 | 4, 6, 1, 3] → 2'yi yerleştir
[2, 4, 5 | 6, 1, 3] → 4'ü yerleştir
[2, 4, 5, 6 | 1, 3] → 6 zaten yerinde
[1, 2, 4, 5, 6 | 3] → 1'i başa yerleştir
[1, 2, 3, 4, 5, 6] → 3'ü yerleştir ✓
Komplekslik
- Zaman: O(n²) - En kötü durum
- Zaman: O(n) - En iyi durum (sıralıysa)
- Alan: O(1) - Yerinde sıralama
Avantajları
- ✅ Neredeyse sıralı dizilerde çok hızlı
- ✅ Kararlı (stable) algoritma
- ✅ Online - Veri gelirken sıralayabilir
- ✅ Küçük dizilerde etkili
🔀 Merge Sort
Çalışma Mantığı
Böl ve Fethet stratejisi kullanır. Diziyi ikiye böler, her parçayı sıralar, sonra birleştirir.
Adımlar
- Diziyi ortadan ikiye böl
- Her iki yarıyı rekürsif olarak sırala
- İki sıralı yarıyı birleştir (merge)
Görsel Gösterim
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43, 3] [9, 82, 10]
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
/ \ / \ / \ |
[38] [27] [43] [3] [9] [82] [10]
\ / \ / \ / |
[27, 38] [3, 43] [9, 82] [10]
\ / \ /
[3, 27, 38, 43] [9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82] ✓
Komplekslik
- Zaman: O(n log n) - Her durumda
- Alan: O(n) - Ek dizi gerekir
Özellikler
- ✅ Garantili O(n log n) performans
- ✅ Kararlı (stable) sıralama
- ✅ Büyük veri setleri için uygun
- ❌ Ekstra bellek kullanır
- ✅ Paralel işlemeye uygun
⚡ Quick Sort
Çalışma Mantığı
Bir pivot eleman seçer, pivot’tan küçükleri sol, büyükleri sağ tarafa yerleştirir. Her iki tarafı rekürsif sıralar.
Adımlar
- Pivot eleman seç (genelde son eleman)
- Pivot’tan küçükleri sol, büyükleri sağa taşı
- Pivot doğru konumuna yerleşir
- Sol ve sağ kısımları rekürsif sırala
Görsel Gösterim
[10, 80, 30, 90, 40, 50, 70] → Pivot: 70
↓ Partition
[10, 30, 40, 50 | 70 | 80, 90]
↓ ↓
Sol kısım sırala Sağ kısım sırala
[10, 30, 40, 50] → Pivot: 50
↓
[10, 30, 40 | 50]
[10, 30, 40] → Pivot: 40
↓
[10, 30 | 40]
Sonuç: [10, 30, 40, 50, 70, 80, 90] ✓
Komplekslik
- Zaman: O(n log n) - Ortalama ve en iyi
- Zaman: O(n²) - En kötü (pivot hep en küçük/büyük)
- Alan: O(log n) - Rekürsyon stack’i
Pivot Seçim Stratejileri
- Son eleman: Basit ama riskli
- Ortanca (median-of-three): Daha güvenli
- Rastgele: En kötü durumu önler
Avantajları
- ✅ Pratikte çok hızlı (cache-friendly)
- ✅ Yerinde sıralama (az bellek)
- ✅ En popüler sıralama algoritması
- ❌ Kararsız (unstable)
- ❌ En kötü durum O(n²)
📊 Hızlı Karşılaştırma
| Algoritma | Zaman (Ortalama) | Zaman (En Kötü) | Alan | Kararlılık |
|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(1) | ✅ Kararlı |
| Selection | O(n²) | O(n²) | O(1) | ❌ Kararsız |
| Insertion | O(n²) | O(n²) | O(1) | ✅ Kararlı |
| Merge | O(n log n) | O(n log n) | O(n) | ✅ Kararlı |
| Quick | O(n log n) | O(n²) | O(log n) | ❌ Kararsız |
💡 Hangi Algoritmayı Kullanmalı?
Küçük Veri Setleri (n < 50)
→ Insertion Sort (basit ve hızlı)
Neredeyse Sıralı Veri
→ Insertion Sort (O(n)’e yakın)
Kararlılık Gerekli
→ Merge Sort (garantili kararlı)
Genel Amaçlı / Büyük Veri
→ Quick Sort (pratikte en hızlı)
Bellek Kısıtlı
→ Quick Sort veya Heap Sort
Garantili Performans
→ Merge Sort (her zaman O(n log n))