Tartalom
A tételek készletének megrendelése egy listában gyakori feladat a programozásban. Gyakran az ember képes intuitív módon elvégezni ezt a feladatot. A számítógépes programnak azonban az utasítások pontos sorrendjét kell követnie a befejezéséhez, és ezt a sorrendet algoritmusnak nevezzük. A rendezési algoritmus egy módszer, amelyet a rendezetlen elemek listájának elhelyezésére használnak egy adott sorrendben. A sorrendet egy kulcs határozza meg. Számos rendezési algoritmus létezik, amelyek különböznek a hatékonyság és a teljesítmény szempontjából. Néhány ilyen típusú ismert és fontos: buborék rendezés, kiválasztási rendezés, beszúrási rendezés és gyors rendezés.
Buborékfajta
A buborék-rendezés többször cseréli a szomszédos elemeket, amelyek nincsenek rendben, amíg a teljes elemlista sorrendben van. Ily módon az elemek értékeik szerint lebegnek a listában, a legnagyobb (növekvő rendezés esetén) az egyes iterációk végén a végéig tart.
Ennek az algoritmusnak a legfőbb előnye, hogy egyszerű és ismert a megvalósítása. Ezenkívül a buborék-rendezésben az elemeket helyettesítik ideiglenes tárolás nélkül, ami minimálisra teszi a helyigényt. A fő hátrány az a tény, hogy nem mutat jó eredményeket, ha a lista sok elemet tartalmaz. Ez a fajta rendezés ugyanis n² feldolgozási lépést igényel minden rendezni kívánt elem n számához. Ezért a buborékfajta alkalmas egyetemi oktatásra, de nem való életben történő alkalmazásra.
Válogatás rendezése
A kiválasztási sorrend ismételten keresi az elemek listáját, egy-egy elemet kiválasztva, és a sorrendben a megfelelő helyre helyezve.
A kiválasztási rendezés fő előnye, hogy rövid listán jól működik. Ezenkívül, mivel helyrendelési algoritmus, nincs szüksége ideiglenes tárolásra azon túl, ami az eredeti lista tárolásához szükséges. A fő hátrány az alacsony hatékonyság nagy listákon. A buborék-rendezéshez hasonlóan n² lépésszámot igényel minden n elemhez. Ezenkívül teljesítményét könnyen befolyásolja az elemek rendezési folyamat előtti kezdeti sorrendje. Emiatt ez a kiválasztási típus csak olyan listára alkalmas, ahol kevés elem van véletlenszerű sorrendben.
Beszúrás rendezése
A beillesztés rendezése többször is beolvassa a listát, és minden alkalommal egy elemet illeszt a rendezetlen sorrendből a megfelelő pozícióba.
A beszúrással történő válogatás fő előnye az egyszerűsége, amellett, hogy kis listákban is jó teljesítményt mutat. Ez egy helyrendezési algoritmus, ezért a helyigény minimális. Hátránya, hogy nem olyan jól teljesít, mint más rendezési algoritmusok. A működéshez szükséges n² lépéssel a beillesztés rendezése szintén nem működik nagy listáknál. Különösen hasznos néhány tétel felsorolásával.
Gyors rendezés
A gyors rendezés a megosztás és a hódítás elvén működik. Először az elemlistát két allistára osztja egy pivot elem alapján. Az első allista összes eleme úgy van elrendezve, hogy kisebbek legyenek, mint a forgás, míg a második allista összes eleme nagyobb legyen, mint az elfordulás. Ugyanazt a particionálási és szervezési folyamatot hajtják végre az eredményül kapott allistákon, amíg a teljes lista el nem rendeződik.
A gyors rendezés egyesek szerint a legjobb rendezési algoritmus, mivel jelentős hatékonysági előnye van, mivel nagy tétellistával jól működik. A helyszínen történő megrendeléssel nincs szükség további tárhelyre sem. Enyhe hátránya, hogy a legrosszabb teljesítménye hasonló a többi fent leírt algoritmus átlagos teljesítményéhez. Fontos azonban megjegyezni, hogy ez a legrosszabb eset nagyon ritka. Általánosságban elmondható, hogy a gyors rendezés a leghatékonyabb és legszélesebb körben alkalmazott módszert kínálja bármilyen méretű lista összeállításához.
