Veriyi Düzene Sokmak: Temel Kavramlar ve Karşılaştırma
Temel konsept
Karmaşıklık farkları
Neden önemli?
Hangi algoritma?
Sıralama, bir veri kümesindeki elemanları belirli bir düzene (artan veya azalan) göre yeniden organize etme işlemidir.
Sıralanmamış
Sıralanmış (Artan)
Sıralama, bilgisayar biliminin en çok çalışılan problemlerinden biridir. Neden?
Birçok algoritma sıralı veri varsayar:
Endüstriyel araştırmalara göre:
Sıralama algoritmaları temel teknikleri gösterir:
Anlaması kolay, küçük veriler için uygun, büyük verilerde yavaş.
Yan yana elemanları karşılaştırıp takas eder. En büyük eleman "yukarı çıkar".
En iyi: O(n) (zaten sıralıysa)
Her elemanı doğru yerine "sokar". Kart oyununda el düzenleme gibi.
En iyi: O(n) (neredeyse sıralıysa)
En küçüğü bulup başa koyar. Her zaman O(n²).
Avantaj: Minimum takas sayısı
Büyük veriler için optimize edilmiş, pratikte kullanılan algoritmalar.
Böl-birleştir stratejisi. Her zaman O(n log n) garantili.
Dezavantaj: O(n) ek bellek
Pivot etrafında bölme. Pratikte en hızlı.
Dikkat: En kötü O(n²)
Heap veri yapısı kullanır. In-place, garantili performans.
Dezavantaj: Cache-unfriendly
Belirli koşullarda çalışan lineer zamanlı algoritmalar.
Sayma tabanlı. Küçük aralıklı tamsayılar için ideal.
Verileri kovalara dağıtır. Uniform dağılım için ideal.
Basamak basamak sıralar. Sabit uzunluklu sayılar için.
| Algoritma | En İyi | Ortalama | En Kötü | Alan | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Evet |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Evet |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ Hayır |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Evet |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ Hayır |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ Hayır |
Stabil bir sıralama algoritması, eşit değerli elemanların orijinal sırasını korur.
5🔴 hala 5♥'den önce
5'lerin sırası değişmiş olabilir
Veritabanında önce isme göre, sonra tarihe göre sıralama yapıyorsanız, ikinci sıralama ilkini bozmamalı!
Bu bölümde geçen bazı terimler size yabancı gelebilir. İşte açıklamaları:
| Durum | Önerilen Algoritma | Sebep |
|---|---|---|
| Küçük veri (n < 50) | Insertion Sort | Basit, overhead yok (fonksiyon çağrısı, bellek ayırma gibi ek işlemler minimum) |
| Neredeyse sıralı veri | Insertion Sort | Adaptive algoritma - sıralı veride O(n) |
| Genel amaçlı (pratikte) | Quick Sort | Ortalamada en hızlı, cache-friendly (ardışık bellek erişimi) |
| Garantili O(n log n) gerekli | Merge Sort | Her zaman O(n log n), en kötü durumda bile |
| Bellek kısıtlı | Heap Sort | In-place, O(1) ek alan (orijinal dizi üzerinde çalışır) |
| Stabilite gerekli | Merge Sort | Stabil - eşit elemanların sırası korunur |
| Linked List sıralama | Merge Sort | Rastgele erişim gerektirmez - sıralı gezinme yeterli |
| Tamsayılar, küçük aralık | Counting Sort | O(n) - karşılaştırma yapmadan sayma ile sıralar |
# Python'un yerleşik sıralama fonksiyonları
# Timsort algoritması kullanır (Merge + Insertion Sort hibrit)
# 1. sorted() - Yeni liste döndürür
original = [64, 34, 25, 12, 22, 11, 90]
sirali = sorted(original)
print(f"Orijinal: {original}")
print(f"sorted(): {sirali}")
# 2. list.sort() - Listeyi yerinde sıralar
liste = [64, 34, 25, 12, 22, 11, 90]
liste.sort()
print(f"\n.sort(): {liste}")
# 3. Azalan sıra
azalan = sorted(original, reverse=True)
print(f"\nAzalan: {azalan}")
# 4. Özel anahtar ile sıralama
isimler = ["Zeynep", "Ali", "Mehmet", "Ayşe"]
isimler_sirali = sorted(isimler, key=len) # Uzunluğa göre
print(f"\nUzunluğa göre: {isimler_sirali}")
# 5. Lambda ile karmaşık sıralama
# lambda x: x["not"] → Anonim fonksiyon, x alır, x["not"] döner
ogrenciler = [
{"ad": "Ali", "not": 85},
{"ad": "Ayşe", "not": 92},
{"ad": "Mehmet", "not": 78}
]
nota_gore = sorted(ogrenciler, key=lambda x: x["not"], reverse=True)
print(f"\nNota göre:")
for o in nota_gore:
print(f" {o['ad']}: {o['not']}")Python'un sort() ve sorted() fonksiyonları Timsort algoritmasını kullanır:
💡 İpucu: Kendi sıralama algoritmanızı yazmak yerine her zaman sorted() veya .sort() kullanın - çok optimize edilmiş!