Melyik a leghatékonyabb rendezési algoritmus?

Olyan algoritmust nehezen, mert ugye, ha ideálistól távol álló sorozatot nézünk, akkor mindet meg kell vizsgálni és pakolni.

Ergó, ha kapsz egy random 10000db-os tömböt, akkor legalább 9999x meg kell vizsgálnod, és ugye még csak 1x mentél végig.

csak már itt bukott, mert a gyök(10000) = 100. Nos, már csak az 1x végig menni is 9999 > 100.

#2 Ez egy elég hülye elgondolás. Nem indoklod meg semmivel, hogy miért kéne 9999 összehasonlítás.

Összehasonlító rendezések esetén létezik kemény alsó korlát: méghozzá úgy jön elő, hogy megalkotod a tömör döntési fát, és ennek a magassága. (itt egy rendezőfa: [link] N=3-ra)

Ugye a lényeg, hogy N! levele van a fának. K magasságú tömör bináris fa leveleinek a száma 2^K. Megkeresed azt a legkisebb K-t, ahol 2^K >= N!, és megvan a minimális száma a döntéseknek (összehasonlításoknak).

Speciális esetben lehetséges hatékonyabb rendezés, de ehhez tudnunk kell a konkrét célt.

" A rendező algoritmusnak meg kell nézni minden elemet ez már eleve O(n) futási idejű."

Még annyit hozzáteszek hogyha nem néznék meg minden elemet akkor az nem más mint vakon elhinni hogy azok jó helyen vannak.

Nézd meg a radix sort-ot. A legrosszabb esetben O(kN)

[link]

Mire nem jó az Algoritmusok és Adatszerkezetek tárgy :D

Ajánlom, hogy nézd meg az 'Algorimusok I.' és az 'Algoritmusok II.' menüpontot, és az ott lévő pdf-eket alaposan tanulmányozd át.

[link]