rendezési algoritmus összehasonlítás

a rendezési algoritmusok az adatok kezelésének fontos részét képezik. AtCprogramming.com, oktatóanyagokat kínálunk a legfontosabb ésközösségi technikák. Minden algoritmus különleges erősségekkel ésgyengeségek és sok esetben a legjobb dolog, ha csak a beépített qsort funkciót használjuk. Azokban az időkben, amikor ez nem lehetséges, vagy csak szüksége vanegy gyors és piszkos rendezési algoritmusra, sokféle lehetőség van.

A legtöbb rendezési algoritmus a rendezendő adatok összehasonlításával működik. Bizonyos esetekben kívánatos lehet egy nagy adatdarabot (például egy nevet és címet tartalmazó astruct) az adatok csak egy része alapján rendezni.A rendezett sorrend meghatározásához ténylegesen használt adatot kulcsnak nevezzük.
a rendezési algoritmusokat általában hatékonyságuk alapján ítélik meg. Ebben az esetben a hatékonyság az algoritmikus hatékonyságra utal, mivel a bemenet mérete növekszik, és általában a rendezendő elemek számán alapul. A legtöbbalgoritmus a használt algoritmikus hatékonysága O(n^2) orO(n*log(n)). Néhány speciális eset algoritmus(egy példát említünk a programozási gyöngyökben) bizonyos adatkészleteket gyorsabban rendezhet, mint O(n*log (n)). Ezek az algorithm-ek nem a rendezendő elemek összehasonlításán alapulnak, hanem a trickekre támaszkodnak. Kimutatták, hogy egyetlen kulcs-összehasonlító algoritmus sem képes jobban teljesíteni, mint O(n*log(n)).
sok algoritmus, amely ugyanolyan hatékonysággal rendelkezik, nem azonos sebességgel rendelkezikugyanaz a bemenet. Először is, az algoritmusokat az átlagos esetük,a legjobb esetük és a legrosszabb esetük hatékonysága alapján kell megítélni. Egyes algoritmusok,mint például a gyors rendezés, kivételesen jól teljesítenek egyes bemeneteknél, de mások számára rettenetesen. Egyébalgoritmusok, mint például az egyesítés rendezés, a bemeneti adatok sorrendje nem befolyásolja.Még egy módosított változata buborék sort lehet befejezni O (n) a leginkábbkedvező bemenetek.
a második tényező az “állandó kifejezés”. Mivel a big-O jelölés kivonja a folyamat sok részletét, nagyon hasznos a bigpicture megtekintéséhez. De egy dolog, ami kimarad, az a kifejezés előtti állandó: például O(c*n) csak O(n). A Való Világban, theconstant, c, különböző algoritmusok között változik. A jól megvalósított quicksortnak sokkal kisebb állandó szorzóval kell rendelkeznie, mint a heap sort.
Az algoritmusok megítélésének második kritériuma a helyigényük-megkarcolják a helyet, vagy a tömb rendezhető a helyén (néhány változón túl további memória nélkül)? Egyes algoritmusok soha nem igényelnek extra helyet, míg egyesek a legkönnyebben megérthetők, ha extra térrel valósítják meg (például a halom rendezése helyben is elvégezhető, de fogalmilag sokkal könnyebb egy külön kupacra gondolni). A helyigény az alkalmazott adatstruktúrától is függhet (például a tömbök egyesítése vagy az összekapcsolt listák egyesítése).
a harmadik kritérium a stabilitás-megőrzi-e a rendezés a kulcsok sorrendjét egyenlő értékekkel? A legtöbb egyszerű fajta csak ezt teszi, de néhány fajta, mint példáulheap rendezés, nem.
a következő táblázat összehasonlítja a rendezési algoritmusokat a különböző kritériumokbana fenti; a magasabb állandó kifejezésekkel rendelkező algoritmusok jelennek meg először, bár ez egyértelműen implementációtól függő fogalom, ezért csak durva útmutatóként kell figyelembe venni, ha azonos big-O hatékonyságot választunk.

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	állandó	stabil	még egy tökéletesen rendezett bemenet is megköveteli a teljes tömb beolvasását
beillesztési Rendezés	O(n^2)	O(n)	O(n^2)	O (n)	O(n ^ 2)	O(n ^ 2)	állandó	stabil	a legjobb esetben(már rendezve), minden betét állandó időt igényel
halom rendezés	o(n*log(n))	o(n*log (n))	o (n*log (n))	állandó	instable	az input tömb használatával a kupac tárolójaként állandó helyet lehet elérni
egyesítési rendezés	O(n*log(n))	O(n*log(n))	O(n*log(n))	függ	stabil	tömbökön az egyesítés rendezése O(n) helyet igényel; összekapcsolt listákon az egyesítés rendezése állandó helyet igényel
Quicksort	o(n*log(n))	o(n*log(n))	o(n^2)	állandó	stabil	segíthet elkerülni a legrosszabb forgatókönyveket, például egy tökéletesen rendezett tömböt.