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
Powered by Facebook Comments