rendezdés

A rendezdés (rendezés) olyan adatok vagy elemek sorrendbe rendezésének folyamata, amelyet egy összehasonlító kulcs szerint határoznak meg. A kulcs lehet numerikus érték, szöveg vagy bármely rendezhető tulajdonság. A cél általában a gyorsabb keresés, a rendezett megjelenítés vagy a feldolgozás hatékonyságának növelése.

Környezetei közé tartozik a számítástechnika és az adatkezelés: rendezéseket végeznek tömbökön, listákon vagy adatbázisok sorozatain. Az adatok rendezésére gyakran kerül sor például egy adott oszlop értékei szerint, vagy több kulcs szerint komplex sorrendet definiálva. Adatbázisokban kifejezetten használják az ORDER BY utasítást a lekérdezések eredményének rendezésére.

Algoritmusok és tulajdonságaik tekintetében két fő kategória létezik: összehasonlító rendezések és nem összehasonlító rendezések. Az előbbiekben a kulcsok közti összehasonlításokra épülő módszerek találhatók, például a quicksort, a mergesort és a heapsort. Ezek általában O(n log n) átlagos időkomplexitást érnek el, de van amelyik memóriaigény vagy stabilitás tekintetében különbözik. A nem összehasonlító rendezések – például a radix- vagy a counting-sort – akkor lehetnek gyorsabbak, amikor a kulcsok értékei korlátozott skálán mozognak és speciális feltételek teljesülnek.

Fontos fogalmak a stabilitás és az in-place végrehajtás. Stabil rendezésnél az azonos kulcsú elemek megőrzik korábbi sorrendjüket; in-place rendezésnél a rendezés minimális extra memóriát használ. Külső rendezés szükséges nagyméretű adatok esetén, ahol az összefésüléses módszerekhez külső tároló is kell.