9. Rendezések II
Beillesztéses rendezés:
Alapötlet: Egy elem önmagában rendezett. A második elemet tegyük a helyére. A harmadikat és az összes soron következőt tegyük a helyére.
Pszeudokód(X: rendezendő tömb, N: tömb elemszáma):
Eljárás Rendezés(X, N)
Ciklus i<-2-től N-ig
j<-i-1
Ciklus amíg j>0 és X[j]>X[j+1]
Csere(X[j], X[j+1])
j<-j-1
Ciklus vége
Ciklus vége
Eljárás vége
Hatékonyság:
- Helyfoglalás: N+1
- Hasonlítások száma: Legalább: N-1 Legfeljebb: N(N-1)/2
- Mozgatások száma: Legalább: 0, Legfeljebb: 3*N(N-1)/2
Javított beillesztéses rendezés:
Alapötlet: A beillesztéses rendezésben túl sok cserét hajtunk végre annak érdekében, hogy egy elem a helyére kerüljön. Ésszerűbb lenne, ha a szükséges elemeket hátrább tolnánk egyel.
Pszeudokód(X: rendezendő tömb, N: tömb elemszáma):
Eljárás Rendezés(X,N)
Ciklus i<-2-től N-ig
j<-i-1
Y<-X[i]
Ciklus amíg j>0 és X[j]>Y
X[j+1]<-X[j]
j<-j-1
Ciklus vége
X[j+1]<-Y
Ciklus vége
Eljárás vége
Hatékonyság:
- Helyfoglalás: N+1
- Hasonlítások száma: Legalább: N-1, Legfeljebb: N(N-1)/2
- Mozgatások száma: Legalább: 2*(N-1) Legfeljebb: 2*(N-1)+N(N-1)/2
Shell rendezés:
Alapötlet: Hasonlítsuk össze először az egymástól Távol lévő elemeket és ha kell, cseréljük meg őket. Így az egyes elemek gyorsan közelében lesznek a végleges helyüknek.
Videó a megértéshez:
Magyarázat: Ami először szemet szúrhat, hogy mi az az L<-L0. Az L0 elvileg szabadon választható, de általában N/2 szokott lenni. Értelem szerűen az L<-Következő(L) egy külső függvény által meghatározott értél az L alapján(2^k-1 vagy a Fibonacci). Ha ezeket letisztáztuk, nem bonyolultabb a kódja a Shell rendezésnek mint az eddigieknek, nem szorul további magyarázatra.
Pszeudokód(X: rendezendő tömb, N: tömb elemszáma, L0: legyen N/2):
Eljárás Rendezés(X, N)
L<-L0
Ciklus amíg L>=1
Ciklus K<-L+1-től 2L-ig
Ciklus i<-K-tól N-ig L-esével
j<-i-L
Y<-X[i]
Ciklus amíg j>0 és X[j]>Y
X[j+L]<-X[j]
j<-j-L
Ciklus vége
X[j+L]<-Y
Ciklus vége
Ciklus vége
L<-Következő(L)
Ciklus vége
Eljárás vége
Felhasznált Irodalom: Sergyán Szabolcs – Programozás I – 8. előadás diasor
Kommentek
Powered by Facebook Comments