„Kupacrendezés” változatai közötti eltérés
[nem ellenőrzött változat] | [nem ellenőrzött változat] |
a „Wikihumor” kategória hozzáadva (a HotCattel) |
aNincs szerkesztési összefoglaló |
||
1. sor: | 1. sor: | ||
A '''kupacrendezés''' |
A '''kupacrendezés''' összehasonlító rendezési [[algoritmus]], és a kiválasztó rendezések családjába tartozik. Helyben rendező, nem stabil rendezés. |
||
== Áttekintés == |
== Áttekintés == |
||
7. sor: | 7. sor: | ||
== Összehasonlítás más rendezésekkel == |
== Összehasonlítás más rendezésekkel == |
||
A kupacrendezés a |
A kupacrendezés a [[gyorsrendezés]]hez hasonló hatékonysággal rendelkezik. A gyorsrendezés általában valamivel gyorsabb, viszont legrosszabb esetben futásideje elérheti a Θ(''n''<sup>2</sup>) nagyságrendet. Bizonyos adatmennyiség felett a négyzetes futásidő elfogadhatatlan, a gyorsrendezés implementációjának ismeretében pedig könnyen elérhető, ezzel csökkentve az algoritmus biztonságát. Mivel a kupacrendezés nagyságrendje Θ(''n'' log ''n'') marad, jellemzően ezt az algoritmust választják a gyorsrendezéssel szemben azokban a rendszerekben, ahol a biztonság meghatározó tényező. |
||
A kupacrendezés szembeállítható az összefésülő |
A kupacrendezés szembeállítható az [[összefésülő rendezés]]sel is. Időigényük hasonló, memóriaigényben az összefésülő rendezés rosszabbul állhat. Az összefésülő rendezés rendelkezik néhány előnnyel a kupacrendezéshez képest: |
||
* Az összefésülő rendezés stabil rendezés. |
* Az összefésülő rendezés stabil rendezés. |
||
* Az összefésülő rendezés könnyebben és hatékonyabban párhuzamosítható. |
* Az összefésülő rendezés könnyebben és hatékonyabban párhuzamosítható. |
||
[[Kategória: |
[[Kategória:Rendezési algoritmusok]] |
||
[[en:Heapsort]] |
A lap 2010. február 13., 08:00-kori változata
A kupacrendezés összehasonlító rendezési algoritmus, és a kiválasztó rendezések családjába tartozik. Helyben rendező, nem stabil rendezés.
Áttekintés
A kupacrendezés nevének megfelelően egy kupac felépítésével kezdődik. Az adatok felhasználásával létrehozunk egy kupacot, majd eltávolítjuk a legnagyobb elemet. A gyökérelem törlésével elromlott a kupac tulajdonság, ezt helyre kell állítanunk. Az elem törlése lehetséges úgy is, hogy a kupac legalsó szintjének jobb szélső elemével cserélünk, és az új jobb szélső elemet nem tekintjük a kupac részének. A helyreállítás úgy lehetséges, hogy az eredeti jobb szélső elemet a gyökérbe helyezzük, majd süllyesztjük. Az utóbbi változatban ez megegyezik a gyökérelem süllyesztésével. A süllyesztés a szülő elemet mindig a nagyobbik, illetve a jobb oldali gyerekkel cseréli, ha van ilyen, és nagyobb a szülőnél. Az algoritmus ezután mindig eltávolítja a következő legnagyobb, azaz a gyökérben található elemet, és helyreállítja a kupac tulajdonságot. Ha a kupacrendezés helyesen, tömbbel kerül implementálásra, és a jobb szélső elemmel való törlést választjuk, a tömb rendezett lesz, és nincs szükség az eredeti tömbnél több memóriára.
A kupac tulajdonság feltételezi, hogy minden szülő elem nagyobb, vagy azonos értékű, mint gyerekei. Ennek megfordításával minimális gyökerű kupacot kapunk, és csökkenően rendezett tömböt készíthetünk a fenti algoritmussal.
Összehasonlítás más rendezésekkel
A kupacrendezés a gyorsrendezéshez hasonló hatékonysággal rendelkezik. A gyorsrendezés általában valamivel gyorsabb, viszont legrosszabb esetben futásideje elérheti a Θ(n2) nagyságrendet. Bizonyos adatmennyiség felett a négyzetes futásidő elfogadhatatlan, a gyorsrendezés implementációjának ismeretében pedig könnyen elérhető, ezzel csökkentve az algoritmus biztonságát. Mivel a kupacrendezés nagyságrendje Θ(n log n) marad, jellemzően ezt az algoritmust választják a gyorsrendezéssel szemben azokban a rendszerekben, ahol a biztonság meghatározó tényező.
A kupacrendezés szembeállítható az összefésülő rendezéssel is. Időigényük hasonló, memóriaigényben az összefésülő rendezés rosszabbul állhat. Az összefésülő rendezés rendelkezik néhány előnnyel a kupacrendezéshez képest:
- Az összefésülő rendezés stabil rendezés.
- Az összefésülő rendezés könnyebben és hatékonyabban párhuzamosítható.