Sürətli nizamlama (Quicksort)

Sürətli nizamlama () 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(n2) əməliyyat yerinə yetirir.

 İşləmə mexanizmi 
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(n2) əməliyyat yerinə yetirir. Psevdokod:Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford: Introduction to Algorithms

 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."Quicksort Partitioning: Hoare vs. Lomuto". cs.stackexchange.com. Retrieved 2015-08-03. Artıq eleməntləri sıralanmış massivlərdə Lomuto bölmə sxemi kimi Hoare də O(n2) ə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]

 İstinadlar 

 Xarici keçidlər 
 Open Data Structures – Section 11.1.2 – Quicksort
 Interactive illustration of Quicksort, with code walkthrough

Kateqoriya:Nizamlama alqoritmləri