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(n2) ə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(n2) əməliyyat yerinə yetirir. Psevdokod:
algorithm quicksort(A, lo, hi) isif 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 doif 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(n2) əməliyyat yerinə yetirir. Psevdokod:
algorithm quicksort(A, lo, hi) isif 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 foreverdo i := i + 1 while A[i] < pivot do j := j - 1 while A[j] > pivot if i >= j thenreturn j swap A[i] with A[j]
İstinadlar
. Computer History Museum. 3 April 2015 tarixində orijinalından arxivləşdirilib. İstifadə tarixi: 22 April 2015.
Hoare, C. A. R. "Algorithm 64: Quicksort". Comm. ACM. 4 (7). 1961: 321. doi:10.1145/366622.366644.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford: Introduction to Algorithms
"Quicksort Partitioning: Hoare vs. Lomuto". cs.stackexchange.com. Retrieved 2015-08-03.
Xarici keçidlər
Open Data Structures – Section 11.1.2 – Quicksort
Interactive illustration of Quicksort[ölü keçid], with code walkthrough
Mart 11, 2022
sürətli, nizamlama, quicksort, sürətli, nizamlama, quicksort, alqoritmi, tony, hoare, tərəfindən, 1959, ildə, hazırlanmış, 1961, ildə, nəşr, olunmuş, nizamlama, alqoritmidir, sürətli, nizamlama, alqoritmi, rekursiv, alqoritmdir, parçala, idarə, etmə, alqoritmi. Suretli nizamlama ing Quicksort alqoritmi Tony Hoare terefinden 1959 1 cu ilde hazirlanmis ve 1961 2 ci ilde nesr olunmus nizamlama alqoritmidir Suretli nizamlama alqoritmi rekursiv alqoritmdir parcala ve idare etme alqoritmine esaslanir Suretli nizamlama alqoritminin riyazi analizleri gosterir ki alqoritm n elementi nizamlamaq ucun ortalama O n log n muqayise emeliyyati yerine yetirir En pis halda ise O n2 emeliyyat yerine yetirir Mundericat 1 Isleme mexanizmi 1 1 Lomuto bolme sxemi 1 2 Hoare bolme sxemi 2 Istinadlar 3 Xarici kecidlerIsleme mexanizmi Redakte Isarelenmis elementler pivot olaraq secilen elemetlerdir Her massivden sonuncu element pivot olaraq secilmisdir Ancaq artiq siralanmis ve ya butun elementleri eyni olan massivlerden her defe sonuncu elementi pivot olaraq secmek O n emeliyyat aparmaq demekdir Suretli nizamlama alqoritmi parcala ve idare etme alqoritmidir Suretli nizamlama evvelce massivi iki kicik massive bolur kicik elementler massivi ve boyuk elementler massivi Sonra rekursiv olaraq bu massivleri siralayir Massiv bos olduqda ve bir elementden ibaret olduqda onu nizamlamaga ehtiyac olmur Bu iki hal suretli nizamlama alqoritminde esas hal base case adlandirilir Eger massivin elementlerinin sayi ikiye beraber ve ya ikiden boyuk olarsa onda suretli nizamlama alqoritmi ilk olaraq massivden tesadufi bir elementi secir Bu element pivot adlandirilir Sonra secilen pivotdan kicik ve boyuk olan elementler tapilir Bu qayda bolme partitioning adlandirilir Neticede Pivotdan kicik olan elementler massivi sol massiv Pivot Pivotdan boyuk olan elementler massivi sag massiv alinir Alinan her iki massiv siralanmamis olur Bu massivler uzerinde alqoritm rekursiv olaraq esas hal alinana qeder yeniden cagrilir Yekun netice sol massiv pivot sag massiv Pivotun secilmesi ve massivin bolunmesi bir nece ferqli sxemlerle edile biler Secilen sxem alqoritmin suretine boyuk tesir gosterir Lomuto bolme sxemi Redakte Bu sxemde pivot bir qayda olaraq massivin sonuncu elementi olaraq secilir Bu sxem artiq siralanmis ve ya butun elementleri eyni olan massivlerde O n2 emeliyyat yerine yetirir Psevdokod 3 algorithm quicksort A lo hi is if lo lt 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 bolme sxemi Redakte Bu alqoritmin muxtelif variantlari var meselen pivotu A lo evezine A hi secmek Hoare sxemi Lomuto bolme sxeminden daha semerelidir Cunki Hoare orta hesabla 3 defe daha az yerdeyisme emeliyyati edir 4 Artiq elementleri siralanmis massivlerde Lomuto bolme sxemi kimi Hoare de O n2 emeliyyat yerine yetirir Psevdokod algorithm quicksort A lo hi is if lo lt 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 lt pivot do j j 1 while A j gt pivot if i gt j then return j swap A i with A j Istinadlar Redakte Sir Antony Hoare Computer History Museum 3 April 2015 tarixinde orijinalindan arxivlesdirilib Istifade tarixi 22 April 2015 Hoare C A R Algorithm 64 Quicksort Comm ACM 4 7 1961 321 doi 10 1145 366622 366644 Cormen Thomas H Leiserson Charles E Rivest Ronald L Stein Clifford Introduction to Algorithms Quicksort Partitioning Hoare vs Lomuto cs stackexchange com Retrieved 2015 08 03 Xarici kecidler RedakteOpen Data Structures Section 11 1 2 Quicksort Interactive illustration of Quicksort olu kecid with code walkthrough Menbe https az wikipedia org w index php title Suretli nizamlama Quicksort amp oldid 5743300, wikipedia, oxu, kitab, kitabxana, axtar, tap, hersey,
ne axtarsan burda
, en yaxsi meqale sayti, meqaleler, kitablar, oyrenmek, wiki, bilgi, tarix, seks, porno, indir, yukle, sex, azeri sex, azeri, seks yukle, sex yukle, izle, seks izle, porno izle, mobil seks, telefon ucun, chat, azeri chat, tanisliq, tanishliq, azeri tanishliq, sayt, medeni, medeni saytlar, chatlar, mekan, tanisliq mekani, mekanlari, yüklə, pulsuz, pulsuz yüklə, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, şəkil, muisiqi, mahnı, kino, film, kitab, oyun, oyunlar.
