Pratikte En Hızlı Genel Amaçlı Sıralama
Quick Sort, bir "pivot" eleman seçip diziyi pivot etrafında bölümlere ayıran, sonra bu bölümleri recursive olarak sıralayan algoritma. Pratikte en hızlı sıralama algoritmasıdır.
Örnek: [8, 3, 7, 4, 2, 6, 5] - Pivot: 5 (son eleman)
Pivot (5) artık doğru yerinde! Solunda hepsi küçük, sağında hepsi büyük.
| Durum | Zaman | Açıklama |
|---|---|---|
| En İyi | O(n log n) | Pivot her zaman medyan |
| Ortalama | O(n log n) | Rastgele pivot iyi çalışır |
| En Kötü | O(n²) | Pivot her zaman en küçük/büyük |
| Alan | O(log n) | Call stack (in-place) |
Ne zaman olur?
Çözüm: Rastgele pivot seçimi veya "median-of-three" kullanmak!
def quick_sort(arr, low=0, high=None, depth=0):
"""
Quick Sort - Lomuto Partition Scheme
"""
if high is None:
high = len(arr) - 1
indent = " " * depth
if low < high:
print(f"{indent}quick_sort(arr[{low}:{high+1}] = {arr[low:high+1]})")
# Partition ve pivot indeksini al
pivot_idx = partition(arr, low, high)
print(f"{indent} Pivot {arr[pivot_idx]} indeks {pivot_idx}'e yerleşti")
print(f"{indent} Dizi: {arr}")
# Sol ve sağ parçaları recursive sırala
quick_sort(arr, low, pivot_idx - 1, depth + 1)
quick_sort(arr, pivot_idx + 1, high, depth + 1)
return arr
def partition(arr, low, high):
"""
Lomuto Partition:
Son elemanı pivot seç, küçükleri sola topla
"""
pivot = arr[high] # Son eleman pivot
i = low - 1 # Küçük elemanların sınırı
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# Pivotu doğru yerine koy
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1 # Pivot'un yeni indeksi
# Test
dizi = [8, 3, 7, 4, 2, 6, 5]
print(f"Başlangıç: {dizi}\n")
sonuc = quick_sort(dizi.copy())
print(f"\n{'='*40}")
print(f"Sonuç: {sonuc}")def quick_sort_simple(arr):
"""
Basit Quick Sort (List Comprehension ile)
NOT: Bu versiyon O(n) ek alan kullanır!
Anlaması kolay ama bellek açısından verimsiz.
"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # Ortadaki eleman pivot
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort_simple(left) + middle + quick_sort_simple(right)
# Test
dizi = [8, 3, 7, 4, 2, 6, 5, 1, 9]
print(f"Başlangıç: {dizi}")
sonuc = quick_sort_simple(dizi)
print(f"Sonuç: {sonuc}")
# Karşılaştırma
print("\n--- Bu versiyonun artıları/eksileri ---")
print("✅ Çok okunabilir ve anlaşılır")
print("✅ Stabil (eşit elemanlar middle'da)")
print("❌ O(n) ek bellek kullanır")
print("❌ Gerçek Quick Sort in-place çalışır")| Strateji | Açıklama | Risk |
|---|---|---|
| İlk/Son Eleman | En basit yöntem | Sıralı dizide O(n²) |
| Rastgele | Rastgele eleman seç | Ortalamada iyi |
| Median-of-Three | İlk, orta, son'un medyanı | En güvenli |
| Özellik | Quick Sort | Merge Sort |
|---|---|---|
| Ortalama | O(n log n) | O(n log n) |
| En Kötü | O(n²) | O(n log n) |
| Alan | O(log n) | O(n) |
| Stabil | ❌ Hayır | ✅ Evet |
| Cache | ✅ Friendly | ❌ Unfriendly |
| Pratikte | Genellikle daha hızlı! | Garantili performans |