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