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: 
Legrosszabb eset: 
Tárigénye:

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: 
Legrosszabb eset: 
Tárigénye:

Beszúró rendezés 

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

Stabil rendezés.

Átlagos eset: 
Legrosszabb eset: 
Tárigénye:

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: 
Legrosszabb eset: 
Tárigénye:

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: 
Legrosszabb eset: 
Tárigénye:

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

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: 
Legrosszabb eset: 
Tárigénye:

Források

További információk 
  Programozni egyszerű! Programozás alapjai kezdőknek 
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

Rendezési algoritmusok