Rendezés (programozás)

A Wikipédiából, a szabad enciklopédiából

Rendezésnek nevezünk egy algoritmust, ha az valamilyen szempont alapján sorba állítja elemek egy listáját. A rendezési algoritmusok a programozás kezdete óta jelen vannak és érdeklődés középpontjában állnak, mivel egy rendezett adathalmazzal több és hatékonyabb műveletek végezhetők, mint egy rendezetlennel.

Rendezési algoritmusok[szerkesztés | forrásszöveg szerkesztése]

A rendezési algoritmusoknak két fő típusa van: az összehasonlító (melyek az elemek összehasonlítása alapján állítják elő a rendezett kimenetet) és a nem összehasonlító (melyek az elemek összehasonlítása nélkül képesek erre) rendezések. Egy másik szempont a rendezés stabilitása, azaz hogy az azonosnak ítélt elemek közötti sorrendet megőrzi-e.

A rendezések hatékonyságát, összehasonlítását általában a szükséges összehasonlítások, cserék átlagos és maximális száma és az extra tárigény alapján végezzük.

Összehasonlító rendezések[szerkesztés | forrásszöveg szerkesztése]

Buborékrendezés[szerkesztés | forrásszöveg szerkesztése]

A buborékrendezés egy egyszerű algoritmus, amelyet főleg az oktatásban használunk, mivel nem igazán hatékony. Elve, hogy egy „buborékkal” haladva a tömbben több menetben elölről hátra a buborékban szereplő két elemet felcseréljük, ha azok rossz sorrendben vannak.

Stabil rendezés.

Átlagos eset:  \mathcal{O} \left( n^2 \right)
Legrosszabb eset:  \mathcal{O} \left( n^2 \right)
Tárigénye:  \mathcal{O} \left( 1 \right)

Gyorsrendezés[szerkesztés | forrásszöveg szerkesztése]

Az egyik legnépszerűbb rendezési algoritmus, amely átlagos esetben gyorsabb, mint a többi algoritmus, viszont hátránya hogy a legrosszabb esetben lassú, és nem stabil rendezés.

Rekurzív algoritmus, kettéosztja a rendezendő listát egy kiemelt elemnél kisebb és nagyobb elemekre, majd a részekre külön-külön alkalmazza a gyorsrendezést.

Átlagos eset: \mathcal{O}\left( {n \log n} \right)
Legrosszabb eset:  \mathcal{O}\left( n^2 \right)
Tárigénye: \mathcal{O}\left( {\log n} \right)

Beszúró rendezés[szerkesztés | forrásszöveg szerkesztése]

Az emberi gondolkodáshoz közel álló algoritmus, amely egyszerre egy elemet visz a helyére.

Stabil rendezés.

Átlagos eset:  \mathcal{O} \left( n^2 \right)
Legrosszabb eset:  \mathcal{O} \left( n^2 \right)
Tárigénye:  \mathcal{O} \left( 1 \right)

Kupacrendezés[szerkesztés | forrásszöveg szerkesztése]

A kupacrendezés a használt adatszerkezetről kapta a nevét, a kupacról. Működése során felépíti a kupacot, majd egyesével kiemeli a gyökérelemet, ami a kupac definíciója miatt a legnagyobb/legkisebb elem lesz.

Nem stabil rendezés.

Átlagos eset: \mathcal{O}\left( {n \log n} \right)
Legrosszabb eset: \mathcal{O}\left( {n \log n} \right)
Tárigénye:  \mathcal{O} \left( 1 \right)

Nem összehasonlító rendezések[szerkesztés | forrásszöveg szerkesztése]

Ezek az algoritmusok nem használják az elemek között fennálló rendezési műveletet (ha egyáltalán van ilyen) az elemek összehasonlítására, ezért általában valamely más, speciálisabb követelményt támasztanak, ezért általános esetben nem használjuk őket.

Jelölések: n az elemek száma, k a kulcsérték mérete. Az algoritmusok feltételezik hogy a kulcsok egyediek és hogy n << 2k (n lényegesen kisebb, mint 2k).

Edényrendezés[szerkesztés | forrásszöveg szerkesztése]

Az algoritmus során edényekbe, kategóriákba helyezzük az elemeket a kulcsértékük alapján, ott helyben rendezzük őket valamelyik rendezési algoritmussal, majd újra összefűzzük a most már rendezett rész-listákat. Közel áll az emberi gondolkodáshoz abban, hogy hatékonyan lebontja a feladatot egyszerűbben megoldhatóakra, és aztán alulról felfelé építi fel az eredményt.

Átlagos eset: \mathcal{O}\left( {n \cdot k} \right)
Legrosszabb eset: \mathcal{O}\left( {n^2 \cdot k} \right)
Tárigénye: \mathcal{O}\left( {n \cdot k} \right)

Források[szerkesztés | forrásszöveg szerkesztése]

Knuth, Donald E.. A számítógép-programozás művészete Harmadik kötet: Keresés és rendezés, második (magyar nyelven), Budapest: Műszaki Könyvkiadó (1994) 

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]