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:
1. **Böl (Divide):** Dizinin içinden referans olarak bir eleman seçilir. Bu elemana **Pivot** adı verilir. Dizi, pivottan küçük olanlar sol tarafa, pivottan büyük olanlar sağ tarafa gelecek şekilde ikiye bölünür (Bölümleme - Partitioning).
2. **Yönet (Conquer):** Pivotun solundaki ve sağındaki iki alt dizi, aynı mantıkla özyinelemeli (recursive) olarak sıralanır.
3. **Birleştir (Combine):** Elemanlar zaten yerinde (in-place) takas edildiği için ekstra bir birleştirme maliyetine gerek kalmaz; dizi kendiliğinden sıralanmış olur!
---
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!