Rendezési algoritmusok

Tartalom

Minimum-kiválasztásos rendezés

Az elemi rendezések

Dummy text.

Az alábbi rendezések futási ideje: N\(^2\)

Egyszerű cserés rendezés

Egyesével összehasonlítjuk a legelső elemet az összes tőle jobbra álló elemmel. Amennyiben egy adott összehasonlított elem kisebb/nagyobb, akkor kicseréljük. Ezt ismételjük a második, harmadik, stb. elemekre mindaddig, még a tömb végére nem érünk.

Az azonos értékű elemek nem cserélődnek fel, sorrendiségük megmarad.

Animáció: link

Algoritmus


            Egyszerű_cserés_rendezés:
                Változó
                    i, j: Egész
                    cs: TH
                Ciklus i=1-től elemszám-ig
                    Ciklus j=i+1-től elemszámig
                        Ha elemek[i] > elemek[j] akkor
                            cs := elemek[i]
                            elemek[i] := elemek[j]
                            elemek[j] := cs
                        Elágazás vége
                    Ciklus vége
                Ciklus vége
            Eljárás vége.

Minimum-kiválasztásos rendezés

Algoritmus


            Minimum-kiválasztásos_rendezés:
                Változó
                    minI, i, j: Egész
                    cs: TH
                Ciklus i=1-től elemszám-1-ig
                    minI := i
                    Ciklus j=i+1-től elemszámig
                        Ha elemek[minI] > elemek[j] akkor minI := j
                    Ciklus vége
                    cs := elemek[minI]
                    elemek[minI] := elemek[i]
                    elemek[i] := cs
                Ciklus vége
            Eljárás vége.

Buborékrendezés

Algoritmus


            Buborékrendezés:
                Változó
                    i, j: Egész
                    cs: TH
                Ciklus i=elemszám-tól 2-ig -1-esével
                    Ciklus j=1-től i-1-ig
                        Ha elemek[j] > elemek[j+1] akkor
                            cs := elemek[j]
                            elemek[j] := elemek[j+1]
                            elemek[j+1] := cs
                        Elágazás vége
                    Ciklus vége
                Ciklus vége
            Eljárás vége.

Algoritmus (javított)


            Javított_buborékrendezés:
                Változó
                    ucs, i, j: Egész
                    cs: TH
                i := elemszám
                Ciklus amíg i >= 2
                    ucs := 0
                    Ciklus j=1-től i-1-ig
                        Ha elemek[j] > elemek[j+1] akkor
                            cs := elemek[j]
                            elemek[j] := elemek[j+1]
                            elemek[j+1] := cs
                            ucs := j
                        Elágazás vége
                    Ciklus vége
                    i := ucs
                Ciklus vége
            Eljárás vége.

Beillesztéses rendezés

Algoritmus


            Beillesztéses_rendezés:
                Változó
                    i, j: Egész
                    cs: TH
                Ciklus i=2-től elemszám-ig
                    j := i-1
                    Ciklus amíg j>0 és elemek[j] > elemek[j+1]
                        cs := elemek[j]
                        elemek[j] := elemek[j+1]
                        elemek[j+1] := cs
                        j := j-1
                    Ciklus vége
                Ciklus vége
            Eljárás vége.

Algoritmus (javított)


            Javított_beillesztéses_rendezés:
                Változó
                    i, j: Egész
                    cs: TH
                Ciklus i=2-től elemszám-ig
                    cs := elemek[i]
                    j := i-1
                    Ciklus amíg j>0 és elemek[j] > cs
                        elemek[j+1] := elemek[j]
                        j := j-1
                    Ciklus vége
                    elemek[j+1] := cs
                Ciklus vége
            Eljárás vége.

További linkek

ELTE specifikáció szerkesztője

Források

Horváth Győző, Horváth Gyula, Szlávi Péter, Törley Gábor: Programozási alapismeretek 9. előadás (ppt) (előadó: Törley Gábor)