Quicksort

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ă $\theta(n \log{n})$ comparații pentru a sorta n elemente. În cazul cel mai rău, efectuează $O(n^2)$ comparații. De obicei, în practică, quicksort este mai rapid decât ceilalți algoritmi de sortare de complexitate $\theta(n \log{n})$ 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^2)$

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.

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ă.