Rendezés (programozás)

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

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

Buborékrendezés

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

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

A beszúrásos rendezés

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)$

Beszúró rendezés bináris kereséssel

Az emberi gondolkodáshoz közel álló algoritmus, amely egyszerre egy elemet visz a bináris kereséssel megállapított helyére. Rendezetten tartott közvetlen elérésű adatbázisokba új elemet így érdemes beszúrni.

Stabil rendezés, az eredeti sorrend nem változik.

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

Kupacrendezés

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

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 << 2^k (n lényegesen kisebb, mint 2^k).

Edényrendezés

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

• 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) 

További információk

• Programozni egyszerű! Programozás alapjai kezdőknek Archiválva 2011. szeptember 24-i dátummal a Wayback Machine-ben
• Beszúrásos rendezés bináris kereséssel

Kapcsolódó szócikkek

• Koktélrendezés
• Fésűs rendezés
• Gyorsrendezés
• Beszúrásos rendezés
• Kupacrendezés