Algoritmalar

Hızlı Sıralama

Sıralama O(n log n) O(log n)

Diziyi bir eksen etrafında bölen, sonra her iki yanı özyinelemeli sıralayan böl-ve-yönet sıralaması.

en fazla 16 sayı (0–999)
Boşta
23
7
41
15
3
34
9
28

8 eleman üzerinde Quick Sort başlıyor.

Değişmezi'nin solundaki her şey < pivot; i ile j arasındaki her şey ≥ pivot. Pivot ikisinin arasına oturur.

1/31
karşılaştırma0takas0lo0hi0pivot0i0j0
quick-sort.c
int partition(int arr[], int lo, int hi) {
int pivot = arr[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (arr[j] < pivot) {
i++;
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
int tmp = arr[i + 1]; arr[i + 1] = arr[hi]; arr[hi] = tmp;
return i + 1;
}
void quickSort(int arr[], int lo, int hi) {
if (lo < hi) {
int p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1);
quickSort(arr, p + 1, hi);
}
}

Hızlı Sıralama nasıl çalışır?

Bir eksen (pivot) seç ve böl: küçükler sola, büyükler sağa — pivot son yerine oturur. İki tarafta özyinele. Her şey yerinde olur.

En iyi durum

Dengeli bölmeler (iyi pivotlar): çok küçük sabitli O(n log n).

En kötü durum

Kötü pivot kuralıyla sıralı girdi — tek taraflı bölmeler: O(n²).

Ne zaman kullanılır?

Kararlılık gerekmiyorsa bellek içi genel amaçlı sıralamanın varsayılanı.