Sürətli çeşidləmə pivot seçir, massivi pivotdan kiçik və kiçik olmayan elementlərə bölür və hər iki hissəni rekursiv çeşidləyir. Birləşdirmə lazım deyil: partition-dan sonra pivot artıq son yerindədir. Orta vaxt O(n log n), pis hal O(n²), yaddaş isə stek üçün O(log n)-dir. partition addımı quickselect-dəki ilə eynidir, indi isə hər iki tərəfə düşürük.

Bölgü invariantları
Bölgü invariantları

Median-of-three pivotlu Lomuto bölgüsü

Pivot birinci, orta və son elementlərin medianıdır və sona köçürülür. i "pivotdan kiçik" zonasının sərhədidir. Rekursiya kiçik hissəyə gedir, böyük hissə üzrə dövr davam edir (aşağıdakı dərinlik bölməsinə bax).

python
def median_of_three(a, lo, hi):
    mid = (lo + hi) // 2
    x, y, z = a[lo], a[mid], a[hi]
    if x < y:
        if y < z:
            return mid
        return hi if x < z else lo
    if x < z:
        return lo
    return hi if y < z else mid

def partition(a, lo, hi):
    m = median_of_three(a, lo, hi)
    a[m], a[hi] = a[hi], a[m]
    pivot = a[hi]
    i = lo
    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):
    a = list(a)

    def sort(lo, hi):
        while lo < hi:
            p = partition(a, lo, hi)
            if p - lo < hi - p:
                sort(lo, p - 1)
                lo = p + 1
            else:
                sort(p + 1, hi)
                hi = p - 1

    sort(0, len(a) - 1)
    return a

print(quick_sort([5, 2, 9, 1, 5, 6, 3]))
print(quick_sort([]))
print(quick_sort([4, 4, 4]))
text
[1, 2, 3, 5, 5, 6, 9]
[]
[4, 4, 4]

Hoare bölgüsü