Quicksort
De Viquipèdia
L'ordenament ràpid (quicksort en anglès) és un algorisme basat en la tècnica de divideix i venceràs, que permet, en promig, 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 desarrollada 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).
Taula de continguts |
[edita] 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.
- Resituar 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 lista ordenada.
- La llista queda separada en dos subllistes, una formada pels elements a l'esquerra del pivot i una altre 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 normalemnt es dona en llistes ordenades o casi.
- En el cas promig, 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.
[edita] Optimització de l'algorisme
[edita] 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 escullit.
- Agagar un element qualsevol com a pivot té l'avantatge de no requerir de cap càlcul adicional, 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 por 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 adicional rebaixa bastant l'eficiència de l'algorisme en el cas promig.
- La opció a caball 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
[edita] 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 continució 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 esquerra 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).
- Quant llista[E] sigui major que el pivot i llista[D] menor, s'intercanvien els elements en aquestes posicions.
- Repetir-ho fins que els índex es creuin.
- El punt en què es creuen els índex és la posició on va el pivot, perquè sabem que a un costat els elements són tots menors i a l'altre son tots majors.
[edita] 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 surgeixen quan s'escull el pivot de forma aleatòria. La permutació concrta depén del pivot triat, però sol correspondre a seqüències ordenades. La provabilitat de trobar-se amb una d'aquestes seqüències és inversament proporcional a la seva mida.
- Les últimes passades de quicksort són numeroses i ordenades 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 provabilitat de trobar-se una configuració d'elements "crítica" és molt baixa, això no evita que segeixin apareixent. L'algorisme introsort és una extensió del quicksort que resolt aquest problema utilitzant heapsort en comptes de quicksort quan el nombre de exedeix l'esperat.
