Büyük veri çağında milyonlarca hatta milyarlarca satırdan oluşan veritabanlarını sıralamak, modern bilişim sistemlerinin en kritik işlem yüklerinden biridir. Bubble Sort gibi basit algoritmalar küçük dizilerde harika birer eğitim aracı olsa da, $n=1.000.000$ olduğunda $O(n^2)$ karmaşıklığı nedeniyle bilgisayarı kilitler. 1959 yılında İngiliz bilgisayar bilimci Sir Tony Hoare tarafından icat edilen Quick Sort (Hızlı Sıralama), pratik uygulamalarda dünyanın en çok kullanılan, C/C++ standart kütüphanesindeki `qsort` fonksiyonuna ve Python'un sıralama motorlarına ilham kaynağı olmuş mühendislik harikası bir sıralama algoritmasıdır.
1. Böl ve Yönet (Divide and Conquer) Prensibi Nedir?
Quick Sort, algoritma tasarımının en güçlü stratejilerinden biri olan "Böl ve Yönet" (Divide and Conquer) prensibiyle çalışır:
2. Pivot Seçimi ve Bölümleme (Partitioning) Stratejileri
Quick Sort'un performansını belirleyen en kritik faktör pivot seçimidir:
Lomuto Bölümleme Mantığı:
Bir `i` göstericisi dizinin solunda tutulur. Bir `j` göstericisi diziyi baştan sona tarar:
3. Zaman ve Alan Karmaşıklığı Analizi
| Senaryo | Zaman Karmaşıklığı | Neden Oluşur? |
|---|---|---|
| En İyi Durum (Best Case) | $O(n \log n)$ | Pivot her seferinde diziyi tam ortadan iki eşit parçaya böldüğünde. |
| Ortalama Durum (Average Case) | $O(n \log n)$ | Rastgele dağılmış verilerde neredeyse her zaman bu performansı verir. |
| En Kötü Durum (Worst Case) | $O(n^2)$ | Dizi zaten sıralıysa ve her zaman en küçük/en büyük eleman pivot seçilirse. |
| Alan Karmaşıklığı (Space) | $O(\log n)$ | Ekstra dizi oluşturmaz, sadece özyineleme yığını (call stack) için bellek harcar. |
Neden Merge Sort'tan daha çok tercih edilir?
Çünkü Quick Sort Yerinde (In-Place) çalışır; yani $O(n)$ ekstra yedek dizi kopyalaması yapmaz ve işlemcinin önbellek (Cache Locality) mimarisiyle olağanüstü uyumludur.
4. Tam ve Çalışan Python ve C++ Kodları
Python ile Quick Sort Uygulaması (Lomuto Partitioning):
def partition(arr, low, high): pivot = arr[high] # Son elemanı pivot seç i = low - 1 # Küçük elemanların sınır göstericisi for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] # Pivotu ait olduğu orta noktaya yerleştir arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 def quick_sort(arr, low, high): if low < high: # Bölümleme indeksini bul pi = partition(arr, low, high) # Sol ve sağ yarıları özyinelemeli sırala quick_sort(arr, low, pi - 1) quick_sort(arr, pi + 1, high) # Test Verisi
sayilar = [10, 80, 30, 90, 40, 50, 70]
print("Sıralama Öncesi :", sayilar)
quick_sort(sayilar, 0, len(sayilar) - 1)
print("Sıralama Sonrası:", sayilar)C++ ile Quick Sort Uygulaması:
#include <iostream>
#include <vector> int partition(std::vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; ++j) { if (arr[j] <= pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1;
} void quickSort(std::vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }
} int main() { std::vector<int> data = {10, 80, 30, 90, 40, 50, 70}; quickSort(data, 0, data.size() - 1); std::cout << "Sirali Dizi: "; for (int val : data) std::cout << val << " "; std::cout << std::endl; return 0;
}5. Kendini Geliştirme Görevi: Quickselect ile K. En Küçük Eleman
Görev: Bir diziyi tamamen sıralamadan, dizideki en küçük 3. sayıyı $O(n)$ ortalama sürede bulabilir misiniz? Quick Sort'un bölümleme mantığını kullanarak sadece aranan indeksin bulunduğu yarıya inen Quickselect algoritmasını kodlamayı deneyin!
6. Üç Yollu Bölümleme (3-Way Partitioning - Hollanda Bayrağı Problemi)
Eğer sıralanacak dizide birbirinin kopyası olan çok sayıda tekrar eden eleman varsa (örneğin `[2, 2, 2, 2, 2, 2]`), standart Quick Sort gereksiz yere $O(n^2)$ süresine düşebilir. Bu zafiyeti çözmek için Edsger Dijkstra tarafından önerilen 3-Way Partitioning (Hollanda Ulusal Bayrağı) algoritması kullanılır:
Sonuç
Quick Sort, doğru pivot seçimiyle birleştiğinde dünyanın en hızlı sıralama motorudur. Böl ve yönet tekniğini kavramak, yazılım mülakatlarında ve algoritmik sistem tasarımlarında size büyük bir avantaj sağlayacaktır. Diğer derslerimiz için [Robotik Kodlama Dersleri](/dersler) sayfamıza göz atabilirsiniz!