Bəzən yalnız k-cı ən kiçik element lazım olur (indekslər 0-dan başlayır): minimum, median, 90-cı persentil. Bütün massivi O(n log n) vaxtda çeşidləmək artıqdır. Quickselect sürətli çeşidləmədəki eyni partition-ı işlədir, lakin hər bölgüdən sonra yalnız bir tərəflə davam edir və cavabı orta hesabla O(n) vaxtda tapır. Bu, "böl və hökm sür" ideyasıdır, bax: böl və hökm sür.

Pivot ətrafında bölgü və bir tərəfin seçilməsi
Pivot ətrafında bölgü və bir tərəfin seçilməsi

Lomuto bölgüsü

Pivot sonuncu elementdir. Dövr pivotdan kiçik elementləri əvvələ daşıyır, i bu zonanın sərhədidir. Sonda pivot a[i] ilə yer dəyişir: bu, onun çeşidlənmiş massivdəki son yeridir.

python
def partition(a, lo, hi):
    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

a = [7, 2, 9, 4, 3, 8, 5]
p = partition(a, 0, len(a) - 1)
print(a)
print("pivot index:", p)
text
[2, 4, 3, 5, 9, 8, 7]
pivot index: 3

Quickselect