Miért a Quicksort a legjobb rendezési módszer?

Nem a quicksort a legjobb, már csak azért sem, mert attól is függy hogy mit és milyen elemszémot kell rendezni.

A quicksort csak általánosságban jó, a lusta programozók gyakran ezt választják.

Nos a téma kissé összetett. Sokféle paraméterrel rendelkezik egy rendezési algoritmus:

- Minimálisan hány összehasonlítás szükséges. (Ha az adatsor eleve rendezett volt.)

- Maximálisan hány összehasonlítás szükséges. (Ha pont a legrosszabb az elrendezés az adott algoritmus szempontjából.)

- Átlagosan hány összehasonlítás szükséges.

- Mekkora a memóriaigénye a rendezésnek.

- Milyen hosszú a kód maga.

- Stabil-e a rendezés. (Azaz mondjuk egy 100 elemű adatsor esetén ha mondjuk 5 olyan szomszédos szám van, ahol egy nagyobb elem előz meg egy kisebb elemet, és a rendezést menet közben megszakítod, akkor nő-e a rendezetlen számpárok száma. Ha a rendezetlen számpárok száma a rendezés során nem tud növekedni, akkor stabil rendezésről van szó.)

- Régen mondjuk ha sok adatot kellett rendezni, ami szalagos egységen foglalt helyet, az sem volt lényegtelen szempont, hogy mennyit kell tekerni a szalagot.

Minden rendezési algoritmusnak vannak előnyei és hátrányai. Pl. a quicksort általában jó választás. De nem a legrövidebb kód – az egyik legkisebb kódú algoritmus a Gnome sort –, ami beépített rendszer esetén lehet lényeges kérdés. A memóriafogyasztása átlagosan log(n), ami nem rossz, de pl. a buborékrendezésnek 1 egységnyi a memóriaigénye. Óriási adatsor esetén ez sem elhanyagolható kérdés. A legrosszabb esetben n² összehasonlítás kell, míg pl. a merge sort esetén csak n*log(n). Az legjobb esetben is n*log(n) összehasonlítás kell, míg mondjuk a beszúrásos, vagy buborékrendezésnél csak n. Ráadásul a quicksort nem stabil rendezés, azaz a rendezés megszakítása után lehet, hogy rendezetlenebb állapot áll fenn, mint a rendezés előtt.

Tehát hogy melyik a legjobb algoritmus? Az attól függ, milyen elvárásokat tartunk fontosnak, és mit tartunk lényegtelennek.

Lásd még: [link]