Hızlı Sıralama

#Nasıl çalışır?

Hızlı sıralama (quick sort) da "böl ve yönet" kullanır, ama işin çoğunu bölme sırasında yapar. Diziden bir pivot seçilir.

Bölümleme (partition) adımında pivottan küçük elemanlar sola, büyük ya da eşit olanlar sağa toplanır. Sonunda pivot ikisinin arasına, yani kesin yerine yerleşir.

Ardından pivotun solundaki ve sağındaki kısımlar aynı yöntemle ayrı ayrı sıralanır. Bu animasyonda Lomuto bölümlemesi kullanılıyor ve pivot her zaman aralığın son elemanı.

#Canlı animasyon

quickSort(a, lo, hi):
  if lo >= hi: return
  pivot = a[hi]; i = lo
  for j = lo to hi - 1
    if a[j] < pivot: swap(a[i], a[j]); i = i + 1
  swap(a[i], a[hi])
  quickSort(a, lo, i - 1); quickSort(a, i + 1, hi)

#Adım adım

1. 01Aralıkta bir ya da hiç eleman yoksa zaten sıralıdır; geri dön.
2. 02Pivot seç (burada aralığın son elemanı).
3. 03Aralığı baştan tara: pivottan küçük her elemanı sol taraftaki sınırın içine al.
4. 04Tarama bitince pivotu küçüklerin hemen sağına yerleştir; pivot artık kesin yerinde.
5. 05Pivotun solundaki ve sağındaki kısımları aynı şekilde sırala.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def partition(a: list[int], lo: int, hi: int) -> int:
    """Lomuto partition: the last element is the pivot. Returns its final index."""
    pivot = a[hi]
    i = lo  # a[lo:i] holds the elements smaller than the pivot
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i


def quick_sort(a: list[int], lo: int, hi: int) -> None:
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)
    quick_sort(a, p + 1, hi)


numbers = [5, 1, 4, 2, 8, 3]
quick_sort(numbers, 0, len(numbers) - 1)
print(*numbers)

#Karmaşıklık

Pivot diziyi yaklaşık iki eşit parçaya böldüğünde n log n işlem yapılır. Pivot hep en küçük ya da en büyük eleman olursa (örneğin sıralı bir dizide son elemanı pivot seçmek) parçalar dengesiz olur ve süre O(n²)'ye çıkar. Rastgele pivot ya da "üçün ortancası" seçimi bu riski pratikte ortadan kaldırır. Özyineleme yığını ortalama O(log n) bellek kullanır.

#Ne zaman kullanılır?

Pratikte genellikle en hızlı karşılaştırmalı sıralamadır: yerinde çalışır ve önbelleği verimli kullanır. C'nin qsort'u ve birçok dilin sayı dizisi sıralaması quick sort tabanlıdır (çoğu zaman introsort gibi hibritlerle). Kararlılık ya da en kötü durum garantisi gerekiyorsa merge sort tercih edilir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.