17. Rekurzív rendezések II

Quicksort:

• Válogassuk szét úgy a rendezendő x tömb elemeit, hogy az első elemnél kisebb méretű elemek az első elem elé, a nagyobbak pedig mögé kerüljenek
• Végezzük el ezt a szétválogatást az első elemnél kisibbekre és nagyobbakra külön külön.
• Ez az eljárás az oszd meg és uralkodj elvet használja

Pszeudokód:

Eljárás Szétválogatás(X,E,U,K)

K<-E; L<-U; A<-X[K];

Ciklus amíg K<L

Ciklus amíg (K<L) és (X[L]>=A)

L<-L-1

Ciklus vége

Ha K<L akkor

X[K]<-X[L]; K<-K+1;

Ciklus amíg (K<L) és (X[K]<=A)

K<-K-1

Ciklus vége

Ha K<L akkor

X[L]<-X[K]; L<-L-1;

Elágazás vége

Elágazás vége

Ciklus vége

X[K]<-A

Eljárás vége

Rekurzív hívás:

Pszeudokód:

Eljárás Quick(X,E,U)

Szétválogat(X,E,U,K)

Ha K-E > 1 akkor

Quick(X,E,K-1)

Elágazás vége

Ha U-K>1 akkor

Quick(X,K+1,U)

Elágazás vége

Eljárás vége

Megjegyzések:

• A Quicksort-nál alkalmazott szétválogat metódus mindíg a résztömb első eleméhez képest válogatja szét a résztömböt
• Emiatt egy eleve rendezett tömbnél az algoritmus futási ideje O(N^2) -es míg átlagos esetben csak O(N*logN)-es
• Javíthatunk az algoritmuson, ha véletlenszerűen jelöljük ki azt az elemet, amelyhez képest viszonyítva szétválogatjuk a résztömböt.

Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 10. előadás diasor

Kommentek

comments

Powered by Facebook Comments