Quicksort, quickselect ve pivot seçimi

Partition, pivot'a göre öğeleri bölümlere ayırır; pivot seçimi ile partition kuralı ayrı kararlardır. Rastgele pivot adversarial sıralılığa bağımlılığı azaltır ama worst-case garantisini ortadan kaldırmaz. Üç yönlü partition küçük/eşit/büyük grupları ayırarak çok tekrar içeren veride gereksiz recursion'ı önler.

Quicksort her iki tarafı sıralar. Quickselect yalnız k'ın bulunduğu tarafa gider; beklenen doğrusal seçim sağlar. k'ın sıfırdan mı birden mi sayıldığını tanımla. Median-of-medians uygun uygulanırsa worst-case O(n) seçim elde eder, fakat sabit maliyeti yüksektir.

Introsort derinlik sınırına ulaştığında heapsort'a dönerek worst-case O(n log n) sağlar. Timsort başka bir hibrit olup mevcut run'ları kullanır; Python'un sort fonksiyonunu burada yazdığımız quicksort sanma. Aşağıdaki okunaklı üç-listeli örnek in-place değildir; benchmark'ta allocation maliyetini saklama.

from random import choice

def quicksort(a):
    if len(a) < 2: return list(a)
    p = choice(a)
    return (quicksort([x for x in a if x < p]) +
            [x for x in a if x == p] +
            quicksort([x for x in a if x > p]))
assert quicksort([3,1,3,2]) == [1,2,3,3]