szuchi.hu

Szuchi Dániel Blogja

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

comments

Powered by Facebook Comments