Rendezés közvetlen kiválasztással
A módszer lényege: A rendezendő számok legyenek az A vektor elemei. Az első menetben kiválasztjuk a vektor legkisebb elemét úgy, hogy az A(1)-et összehasonlítjuk A(2)... A(N) mindegyikével. Ha A(1)-nél kisebb elemet találunk, felcseréljük őket, vagyis ezt a kisebbet tesszük A(1)-be. Így a menet végére A(1) biztosan a vektor legkisebb elemét tartalmazza majd. Az eljárást A(2)-vel folytatjuk, ezt hasonlítjuk össze az A(3), ..., A(N) elemekkel. És így tovább. N-1 lépésben a vektor rendezett lesz.
Algoritmus:
Eljárás
Ciklus I=1-től N-1-ig
Ciklus J=I+1-től N-ig
Ha A(J)<A(I) akkor A:=A(J) ; A(J):=A(I) ; A(I):=A
Ciklus vége
Ciklus vége
Eljárás vége.
Rendezés minimum kiválasztással
A módszer lényege: A felesleges cserék kiküszöbölése érdekében két segédváltozót vezetünk be. Az ÉRTÉK tartalmazza az adott menetben legkisebb számot, az INDEX pedig annak lelőhelyét a vektorban.
Algoritmus:
Eljárás
Ciklus I=1-től N-1-ig
INDEX:=I ; ÉRTÉK:=A(I)
Ciklus J=I+1-től N-ig
Ha ÉRTÉK>A(J) akkor ÉRTÉK:=A(J) ; INDEX:=J
Ciklus vége
A(INDEX):=A(I) ; A(I):=ÉRTÉK
Ciklus vége
Eljárás vége.
Buborékos rendezés
A buborékos rendezés alapgondolata a szomszédos elemek cseréje. Az első menetben a rendező A vektor végéről indulva minden elemet összehasonlítunk az előtte lévővel. Amennyiben rossz sorrendben vannak, felcseréljük őket. Az első menet végére a legkisebb elem biztosan a helyére kerül. Minden további menetben ismét a vektor végéről indulunk, de egyre kevesebb hasonlításra van szükségünk, mert a vektor eleje fokozatosan rendezetté válik.
Algoritmus:
Eljárás
Ciklus I=2-től N-ig
Ciklus J=N-től I-ig (-1-esével)
Ha A(J-1)>A(J) akkor A:=A(J-1)
A(J-1):=A(J)
A(J):=A
Elágazás vége
Ciklus vége
Ciklus vége
Eljárás vége.
Egyszerű beillesztéses rendezés
A rendezést úgy végezzük, mintha kártyáznánk, és kezünkbe egyesével vennénk fel az asztalról a kiosztott lapokat. Az éppen felvett lapnak megkeressük a kezünkben lévő, már rendezett sorozatban a helyét úgy, hogy közben a nála nagyobbakat egy hellyel elcsúsztatjuk, végül beillesztjük a felvett lapot a neki megfelelő helyre. N elem esetén a végső sorrend kialakításához N-1 menetre van szükség.
Eredeti: 64 56 8 42 5 12 16 40 3 31 47 22 24 33 7 46
1. menet után: 56 64 8 42 5 12 16 40 3 31 47 22 24 33 7 46
2. menet után: 8 56 64 42 5 12 16 40 3 31 47 22 24 33 7 46
3. menet után: 8 42 56 64 5 12 16 40 3 31 47 22 24 33 7 46
4. menet után: 5 8 42 56 64 12 16 40 3 31 47 22 24 33 7 46
5. menet után: 5 8 12 42 56 64 16 40 3 31 47 22 24 33 7 46
...........
15. menet után: 3 5 7 8 12 16 22 24 31 33 40 42 46 47 56 64
Algoritmus:
Eljárás
Ciklus J=2-től N-ig
I:=J-1 ; A:=A(J)
Ciklus amíg I>0 és A<A(I)
A(I+1):=A(I) ; I:=I-1
Ciklus vége
A(I+1):=A
Ciklus vége
Eljárás vége.
Quicksort
Igen gyors és hatékony rendezésről van szó, amelynek alapja az, hogy egymástól távol lévő elemeket hasonlítunk össze egymással, és szükség esetén felcseréljük azokat.
Válasszuk ki az A vektor első elemét, és vegyük ki a vektorból. A helye üres marad.
A vektor végéről indulva keresünk egy ennél kisebb elemet. Ha találunk, azt betesszük a felszabadult helyre. Most a lyuk ott keletkezik, ahonnan ezt az elemet kivettük. Ide a vektor elejéről keresünk egy, a kiválasztott elemnél nagyobb elemet. Ha találunk, beillesztjük, ha nem, akkor oda éppen a kiválasztott elem illik.
64 56 8 42 5 12 16 40 3 31 47 22 24 33 7 46
64 __ 56 8 42 5 12 16 40 3 31 47 22 24 33 7 46
64 46 56 8 42 5 12 16 40 3 31 47 22 24 33 7 __
46 56 8 42 5 12 16 40 3 31 47 22 24 33 7 64
A konkrét példában nem sikerült a vektort nem sikerült két részre vágni, mert a 64 éppen a legnagyobb elem. A következő lépésben a 46-ot emeljük ki a vektor elejéről, és hátulról haladva keressünk nála kisebb elemet, és így tovább.
46 __ 56 8 42 5 12 16 40 3 31 47 22 24 33 7 64
46 7 56 8 42 5 12 16 40 3 31 47 22 24 33 __ 64
46 7 __ 8 42 5 12 16 40 3 31 47 22 24 33 56 64
46 7 33 8 42 5 12 16 40 3 31 47 22 24 __ 56 64
46 7 33 8 42 5 12 16 40 3 31 __ 22 24 47 56 64
46 7 33 8 42 5 12 16 40 3 31 24 22 __ 47 56 64
7 33 8 42 5 12 16 40 3 31 24 22 46 47 56 64
A 46 most a végleges helyére került. Tőle balra a nála kisebb, jobbra a nála nagyobb elemek helyezkednek el. Az eljárást az így kettévágott vektor egyik részének elemeivel a fent leírt módon folytatjuk tovább.
Algoritmus:
Eljárás Quick(AH, FH)
Szétválogat(AH, FH, E)
Ha AH<E-1 akkor Quick(AH, E-1)
Ha E+1<FH akkor Quck(E+1, FH)
Eljárás vége
A szétválogató eljárás a vektor elemeit úgy rendezi át, hogy az E-edik elem elé kerülnek a nála kisebbek, mögé pedig a nagyobbak.
Teljes algoritmus:
Eljárás gyorsrendezés (n, A) {n – elemszám, A - tömb}
Eljárás rendez(also, felso)
I:=also; J:=felso; {az intervallumok szélei}
X:=A[(also+felso) div 2]; {a középső elem, div – egész osztás}
Ciklus
Ciklus amíg A[I]<x I:=I+1 ciklus vége {elölről}
Ciklus amíg A[J]>x J:=J-1 ciklus vége {hátulról}
Ha I<=J akkor csere(A[I];A[J]); I:=I+1; J:=J-1;
Amíg I>J
Ha also<J akkor rendez(also,J); {addig áll fenn, amíg a különbségük}
Ha I<felso akkor rendez(I, felso); {legalább 1. 1-hosszúra már nem hívjuk meg}
Eljárás vége
Begin
Rendez(1,N); {a főprogram}
End;
Megjegyzések:
· A középső elem mindig más, amíg a két határ össze nem ér.
· Az algoritmus sebessége függ az elemek rendezettségétől
· Akkor a leglassabb, ha a középső elem a legkisebb vagy a legnagyobb
· Akkor igazán gyors, ha nagy méretű tömbbel dolgozik
· Nem ismeri fel, ha a tömb rendezett, de ekkor is gyors. A rekurzív újrahívás megtörténik.
· A kis méretű tömbökre azért nem jó, mert a rekurzió lassít
Hibrid megoldás: Ha a tömbméret lecsökken mondjuk 100 elemre, akkor egy hagyományos rendező algoritmust használunk.
Tipp: a quicksort algoritmus lefutása előtt egyszerűen ellenőrizhetjük, hogy a tömb nem rendezett-e már.
