Quicksort

De la Wikipedia, enciclopedia liberă

Quicksort în acţiune pe o listă de numere. Liniile orizontale sunt valorile pivot.

Quicksort este un celebru algoritm de sortare, dezvoltat de C. A. R. Hoare şi care, în medie, efectuează θ(nlogn) comparaţii pentru a sorta n elemente. În cazul cel mai rău, efectuează O(n²) comparaţii. De obicei, în practică, quicksort este mai rapid decât ceilalţi algoritmi de sortare de complexitate θ(nlogn) deoarece bucla sa interioară are implementări eficiente pe majoritatea arhitecturilor şi, în plus, în majoritatea implementărilor practice se pot lua, la proiectare, decizii ce ajută la evitarea cazului când complexitatea algoritmului este de O(n²)

[modifică] Istoric

Algoritmul a fost dezvoltat de C. A. R. Hoare în 1960, pe când lucra la mica firmă britanică producătoare de calculatoare Elliot Brothers.

[modifică] Algoritmul

Quicksort efectuează sortarea bazându-se pe o strategie divide et impera. Astfel, el împarte lista de sortat în două subliste mai uşor de sortat. Paşii algoritmului sunt:

1. Se alege un element al listei, denumit pivot
2. Se reordonează lista astfel încât toate elementele mai mici decât pivotul să fie plasate înaintea pivotului şi toate elementele mai mari să fie după pivot. După această partiţionare, pivotul se află în poziţia sa finală.
3. Se sortează recursiv sublista de elemente mai mici decât pivotul şi sublista de elemente mai mari decât pivotul.

O listă de dimensiune 0 sau 1 este considerată sortată.

Acest articol din domeniul informaticii este deocamdată un ciot. Puteţi ajuta Wikipedia prin dezvoltarea lui.