Sürətli nizamlama (Quicksort)

Sürətli nizamlama (ing. Quicksort) alqoritmi Tony Hoare tərəfindən 1959 -cu ildə hazırlanmış və 1961 -ci ildə nəşr olunmuş, nizamlama alqoritmidir. Sürətli nizamlama alqoritmi rekursiv alqoritmdir, parçala və idarə etmə alqoritminə əsaslanır. 

Sürətli nizamlama alqoritminin riyazi analizləri göstərir ki, alqoritm n elementi nizamlamaq üçün ortalama O(n log n) müqayisə əməliyyatı yerinə yetirir. Ən pis halda isə O(n²) əməliyyat yerinə yetirir.

İşləmə mexanizmi

İşarələnmiş elementlər pivot olaraq seçilən elemetlerdir. Hər massivdən sonuncu element pivot olaraq seçilmişdir. Ancaq, artıq sıralanmış və ya bütün elementləri eyni olan massivlərdən hər dəfə sonuncu elementi pivot olaraq seçmək (O(n²)) əməliyyat aparmaq deməkdir.

Sürətli nizamlama alqoritmi parçala və idarə etmə alqoritmidir. Sürətli nizamlama əvvəlcə massivi iki kiçik massivə bölür: kiçik elementlər massivi və böyük elementlər massivi. Sonra rekursiv olaraq bu massivləri sıralayır. Massiv boş olduqda və bir elementdən ibarət olduqda onu nizamlamağa ehtiyac olmur. Bu iki hal sürətli nizamlama alqoritmində əsas hal (base case) adlandırılır. Əgər massivin elementlərinin sayı ikiyə bərabər və ya ikidən böyük olarsa onda sürətli nizamlama alqoritmi ilk olaraq massivdən təsadüfi bir elementi seçir. Bu element pivot adlandırılır. Sonra seçilən pivotdan kiçik və böyük olan elementlər tapılır. Bu qayda bölmə (partitioning) adlandırılır. Nəticədə:

• Pivotdan kiçik olan elementlər massivi (sol massiv)
• Pivot 
• Pivotdan böyük olan elementlər massivi (sağ massiv)

alınır. Alınan hər iki massiv sıralanmamış olur. Bu massivlər üzərində alqoritm rekursiv olaraq əsas hal alınana qədər yenidən çağrılır.  Yekun nəticə:

                   sol massiv  + pivot + sağ massiv

Pivotun seçilməsi və massivin bölünməsi bir neçə fərqli sxemlərlə edilə bilər. Seçilən sxem alqoritmin sürətinə böyük təsir göstərir. 

Lomuto bölmə sxemi

Bu sxemdə pivot bir qayda olaraq massivin sonuncu elementi olaraq seçilir.  Bu sxem artıq sıralanmış və ya bütün elementləri eyni olan massivlərdə O(n²) əməliyyat yerinə yetirir. Psevdokod:

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] ≤ pivot then
            i := i + 1
            swap A[i] with A[j]
   swap A[i + 1] with A[hi]
   return i + 1

Hoare bölmə sxemi

Bu alqoritmin müxtəlif variantları var, məsələn, pivotu  A[lo] əvəzinə A[hi]seçmək. Hoare sxemi Lomuto bölmə sxemindən daha səmərəlidir. Çünki Hoare orta hesabla 3 dəfə daha az yerdəyişmə əməliyyatı edir. Artıq eleməntləri sıralanmış massivlərdə Lomuto bölmə sxemi kimi Hoare də O(n²) əməliyyat yerinə yetirir. Psevdokod:

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

Xarici keçidlər

• Open Data Structures – Section 11.1.2 – Quicksort
• Interactive illustration of Quicksort, with code walkthrough