szuchi.hu

Szuchi Dániel Blogja

8. Rendezések I

A rendezésről általában:

A rendezési algoritmusok alapfeladata, hogy egy N elemű sorozatot nagyság szerint sorba rendez. Ehhez mindenképpen szükséges a < (relációs) művelet. A rendezéseket általában az eredeti sorozatban hajtjuk végre, így az eredeti rendezetlen sorozat elveszik.

|5|3|9|1|7| -> |1|3|5|7|9|

A rendezési algoritmusok bemenete minden esetben egy N elemű X tömb és kimenete is ugyan ez.

Egyszerű cserés rendezés:

Alapötlet: A sorozat első elemét hasonlítsuk össze az őt követőkkel, ha egy elem kisebb mint az első, akkor cseréljük meg őket. Így a sorozat elejére a legkisebb elem kerül. Ezt kell megismételni az összes többi elemmel is egymás után.

Pszeudokód(X: Rendezendő tömb, N: tömb elemszáma):

Eljárás Rendezés(X, N)

Ciklus i<-1-től N-ig

Ciklus j<-i+1-től N-ig

Ha X[i]>X[j] akkor

Csere(X[i], X[j])

Elágazás vége

Ciklus vége

Ciklus vége

Eljárás vége

A csere megvalósítása:  A sorbeli két elem megcseréléséhez szükséges egy plusz elem aminek a típusa megegyezik a sor elemeinek típusával.

Pszeudokód:

Eljárás Csere(X[i], X[j])

TEMP<-X[i]

X[i]<-X[j]

X[j]<-TEMP

Eljárás vége

Rendezés hatékonysága:

  • Helyfoglalás: N+1
  • Hasonlítások száma: N(N-1)/2
  • Mozgatások száma: Legalább:0 Legfeljebb: 3*N(N-1)/2

 

Minimumkiválasztásos rendezés:

Alapötlet: Mivel az egyszerű cserés rendezés nagyon sokszor cserél elemeket, ezért a minimumkiválasztásos rendezés az aktuális elemet a mögötte állók minimumával cseréli fel.

Pszeudokód(X: rendezendő tömb, N: tömb elemszáma):

Eljárás Rendezés(X, N)

Ciklus i<-1-től N-ig

MIN<-i

Ciklus j<-i+1-től N-ig

Ha X[MIN]>X[j] akkor

Min<-j

Elágazás vége

Ciklus vége

Csere(X[i], X[MIN])

Ciklus vége

Elágazás vége

Hatékonyság:

  • Helyfoglalás: N+1
  • Hasonlítások száma: N(N-1)/2
  • Mozgatások száma: 3*(N-1)

 

Megjegyzés: A mozgatások száma akár több is lehet, mint az egyszerű cserés rendezésnél, ennek oka, hogy a külső ciklusban mindenképpen cserélünk, annak érdekében, hogy ne keljen mindig összehasonlítást elvégezni.

 

Buborékos rendezés:

Alapötlet: Összehasonlítjuk az egymással szomszédos elemeket, és ha a sorrendjük nem jó akkor cseréljük őket. Ennek hatására először a legnagyobb elem kerül a helyére majd a második legnagyobb, és így tovább.

Pszeudokód(X:rendezendő tömb, N: tömb elemszáma):

Eljárás Rendezés(X, N)

Ciklus i<-N-től 2-ig -1-esével

Ciklus j<-1-től i-1-ig

Ha X[j]>X[j+1] akkor

Csere(X[j],X[j+1])

Elágazás vége

Ciklus vége

Ciklus vége

Eljárás vége

Hatékonyság:

  • Helyfoglalás: N+1
  • Hasonlítások száma: N(N-1)/2
  • Mozgatások száma: Legalább 0, Legfeljebb: 3*N(N-1)/2

 

Javított buborékos rendezés:

Alapötlet: Ha a buborékrendezés belső ciklusában már nincsen csere, akkor az algoritmust kár folytatni. Ha volt csere, de az utolsó csere a sorozat közepén volt, akkor az utolsó csere helyétől a sorozat már rendezett, felesleges azzal a résszel foglalkozni.

Pszeudokód(X: rendezendő tömb, N: tömb elemszáma):

Eljárás Rendezés(X, N)

i<-N

Ciklus amíg i>=2

CS<-0

Ciklus j<-1-től i-1-ig

Ha X[j]>X[j+1] akkor

Csere(X[j], X[j+1])

CS<-j

Elágazás vége

Ciklus vége

i<-CS

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
  • A buborék rendezéshez képest szignifikáns javulás az átlagos végrehajtási időben van

 

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

 

Kommentek

comments

Powered by Facebook Comments