Quicksort

Archiu:Sorting quicksort anim.gif

Quicksort en acció sobre una llista de números aleatoris. Les llínees horisontals són valores pivot.

El ordenament ràpit (quicksort en anglés) és un algoritme de ordenacion creat pel científic britànic en computació C. A. R. Hoare.

Descripció de l'algoritme

L'algoritme treballa de la següent forma:

• Elegir un element del conjunt d'elements a ordenar, al que cridarem pivot.
• Resituar els demés elements de la llista a cada costat del pivot, de manera que a un costat queden tots els menors que ell, i a l'atre els majors. Els elements iguals al pivot poden ser colocats tant a la seua dreta com a la seua esquerra, depenent de l'implementació desijada. En este moment, el pivot ocupa exactament el lloc que li correspondrà en la llista ordenada.
• La llista queda separada en dos sublistas, una formada pels elements a l'esquerra del pivot, i una atra pels elements a la seua dreta.
• Repetir este procés de forma recursiva per a cada sublista mentres estes continguen més d'un element. Una volta terminat este procés tots els elements estaran ordenats.

Com es pot supondre, l'eficiència de l'algoritme depén de la posició en la que termine el pivot elegit.

• En el millor cas, el pivot termina en el centre de la llista, dividint-la en dos sublistas d'igual tamany. En este cas, l'orde de complexitat de l'algoritme és O(n·log n).
• En el pijor cas, el pivot termina en un extrem de la llista. L'orde de complexitat de l'algoritme és llavors de O(n²). El pijor cas dependrà de l'implementació de l'algoritme, encara que habitualment ocorre en llistes que es troben ordenades, o casi ordenades. Pero principalment depén del pivot, si per eixemple l'algoritme implementat pren com a pivot sempre el primer element del array, i el array que li passem està ordenat, sempre va a generar a la seua esquerra un array buit, lo que és ineficiente.

• En el cas promig, l'orde és O(n·log n).

No és estrany, puix, que la majoria d'optimisacions que s'apliquen a l'algoritme se centren en l'elecció del pivot.

Demostració d'un cas particular

Supongam que el número d'elements a ordenar és una potència de dos, és dir, $n=2^k$ per a algun natural $k$. Immediatament $k=lo{g}_2(n)$, a on k és el número de divisions que realisarà l'algoritme.

En la primera fase de l'algoritme hi haurà n comparacions. En la segona fase l'algoritme instanciará dos sublistas de tamany aproximadament n/2. El número total de comparacions d'estes dos sublistas és: 2(n/2) = n. En la tercera fase l'algoritme processarà 4 sublistas més, per tant el número total de comparacions en esta fase és 4(n/4) = n.

En conclusió, el número total de comparacions que fa l'algoritme és:

$n+n+n+\mathrm{.....}+n=kn$, a on $k=lo{g}_2(n)$, per tant l'Orde de Complexitat de l'algoritme en el millor dels casos és $O(n.lo{g}_{2}n)$.

Vore també

• Algoritme d'ordenament