Quicksort

L'ordenament ràpid, quicksort en anglès, és un algorisme basat en la tècnica de divideix i venceràs, que permet, de mitjana, ordenar n elements en un temps proporcional a n log n. Aquesta és probablement la tècnica d'ordenament més ràpida que es coneix. Fou desenvolupada per C. Antony R. Hoare el 1960. L'algorisme original és recursiu, però s'utilitzen versions iteratives per a millorar-ne el rendiment (els algorismes recursius són en general més lents que els iteratius i consumeixen més recursos).

Animació que exemplifica l'algorisme. Les línies horitzontals indiquen el pivot.

Descripció de l'algorisme

L'algorisme fonamental és el següent:

• Triar un element de la llista d'elements a ordenar, al que anomenarem pivot.
• Ressituar els elements restants de la llista a cada costat del pivot, de manera que a un costat queden els més petits i a l'altre els més grans que el pivot. En aquest moment, el pivot ocupa exactament el lloc que li correspondrà en la llista ordenada.
• La llista queda separada en dues subllistes, una formada pels elements a l'esquerra del pivot i una altra amb elements de la seva dreta.
• Repetim aquest procés de forma recursiva mentre aquestes subllistes continguin més d'un element. Una vegada acabat aquest procés tots els elements estaran ordenats.

Tal com es pot suposar, l'eficiència de l'algorisme depèn de la posició en què acabi el pivot triat.

• En el millor cas, el pivot acaba en el centre de la llista, dividint-la en dues de la mateixa mida. En aquest cas, l'ordre de complexitat de l'algorisme és O (n·log n).
• En el pitjor cas, el pivot acaba en un extrem de la llista. L'ordre de complexitat de l'algorisme és de 0(n²). El pitjor cas dependrà de la implementació de l'algorisme, tot i que normalment es dona en llistes ordenades o quasi.
• En el cas mitjà, l'ordre és O(n·log n).

No és estrany, doncs, que la majoria d'optimitzacions que s'apliquen a l'algorisme se centrin en l'elecció del pivot.

Optimització de l'algorisme

Tècniques d'elecció de pivot

L'algorisme bàsic Quicksort permet agafar qualsevol element de la llista com a pivot, tot i que ja hem vist l'eficiència de l'algorisme dependrà del pivot escollit.

• Agafar un element qualsevol com a pivot té l'avantatge de no requerir cap càlcul addicional, la qual cosa el fa bastant ràpid. Tot i així, aquesta tria aleatòria sempre provoca que l'algorisme tingui un ordre de O(n²) per a certes permutacions dels elements de la llista.
• Un altre recurs pot ser recórrer tota la llista per saber prèviament quin element ocuparà la posició central de la llista i així triar-lo com a pivot. Això es pot fer en O(n) i assegura que fins i tot en el pitjor dels casos l'algorisme sigui O(n·log n). No obstant això, el càlcul addicional rebaixa bastant l'eficiència de l'algorisme en el cas mitjà.
• L'opció a cavall de les dues és prendre tres elements de la llista - per exemple, el primer, el tercer i l'últim - i comparar-los, escollint el valor mitjà com a pivot

Tècniques de reposicionament

Una idea preliminar per a ubicar el pivot en la seva posició final seria comptar la quantitat d'elements menors que si i ubicar-lo una posició més amunt, movent a continuació tots aquests elements menors cap a la seva esquerra, per poder aplicar la recursivitat.

Tot i això, hi ha un procediment molt més efectiu. S'utilitzen dos index: E, al que anomenarem índex esquerre i D que serà l'index dret. L'algorisme és el següent:

• Recórrer la llista de forma simultània amb E i D: per l'esquerra amb E (des del primer element) i per la dreta amb D(des de l'últim element).
• Quan llista[E] sigui major que el pivot i llista[D] menor, s'intercanvien els elements en aquestes posicions.
• Repetir-ho fins que els índexs es creuin.
• El punt en què es creuen els índexs és la posició on va el pivot, perquè sabem que a un costat els elements són tots menors i a l'altre són tots majors.

Transició a un altre algorisme

Tal com ja s'ha comentat, l'algorisme quicksort ofereix un ordre d'execució O(n²) per a certes permutacions "crítiques" dels elements de la llista, que sempre sorgeixen quan s'escull el pivot de forma aleatòria. La permutació concreta depèn del pivot triat, però sol correspondre a seqüències ordenades. La probabilitat de trobar-se amb una d'aquestes seqüències és inversament proporcional a la seva mida.

• Les últimes passades de quicksort són nombroses i ordenen quantitats de petits elements. Un percentatge mitjanament alt d'aquests estaran disposats d'una forma semblant al pitjor cas de l'algorisme, fent-lo ineficient. Una solució al problema consisteix a ordenar les seqüències petites emprant un altre algorisme. Habitualment s'utilitza l'algorisme d'inserció per a seqüències de menys de 8-15 elements.
• Tot i que en les seqüències llargues d'elements la probabilitat de trobar-se una configuració d'elements "crítica" és molt baixa, això no evita que segueixin apareixent. L'algorisme introsort és una extensió del quicksort que resolt aquest problema utilitzant heapsort en comptes de quicksort quan el nombre de excedeix l'esperat.

Vegeu també

• Bubble-sort

Enllaços externs

• Dictionary of Algorithms and Data Structures del NIST (anglès)
• Comparativa de diferents algorismes d'ordenació Arxivat 2016-01-13 a Wayback Machine. (anglès)