Programozás‎ > ‎

Rendezések

Bevezető

A rendezés a legalapvetőbb programozási probléma. Van néhány adatunk és ezeket valamilyen szempont szerint nagyság szerinti sorrendbe kell rendeznünk.


Ebben a pontban csak olyan rendezésekkel foglalkozunk  ahol a rendezendő adatok elférnek a központi memóriában. Feltesszük tehát, hogy az adatok egy a[ ] tömbben vannak. Az algoritmusokat lehetőség szerint függetleníteni szeretnénk a programozási nyelvektől, ezért bevezetünk két jelölést: a tömb első elemének indexe E, utolsó elemének indexe pedig U lesz.

A rendezést általában összetett objektumokon hajtjuk végre, ilyenkor a sorrendet valamelyik mező adja meg, amit szokás rendezési kulcsnak hívni. Az algoritmusainkban elrejtjük ezt a részletet és úgy fogalmazzuk meg a módszereket, hogy mindenhol az a[i] < a[j] összehasonlítást használjuk. Egy külön pontban vizsgáljuk azt, hogy hogyan lehet típus- és objektumfüggetlen rendezést írni. (Ez már nyelvfüggő.)

Rendezési algoritmusok


Rendezési algoritmusok összehasonlítása

Animációk

www.sorting-algorithms.com
Rendezések eltáncolva

A hatékonyság mérőszámai

Futási idő a bemenet függvényében


Memóriaigény


Bonyolultság

Objektumok rendezése, "összehasonlítható" adatok


Gyakorlat

Rendezzük különböző módszerekkel a mellékelt adatfájlokat és mérjük meg a rendezések futási idejét!