Ordenación rápida: quicksort

Este algoritmo está baseado na técnica de divide e vencerás. É unha das técnicas de ordenación máis eficientes e a que arroxa o mellor resultado na maioría dos casos (cando falamos de ordenación o mellor resultado é aquel conseguido no menor tempo e co mínimo código). O algoritmo funciona do seguinte xeito:

  • Escollo un número da lista ao chou que será o pivote.

  • Recoloco todos os demais elementos da lista a un lado ou a outro segundo sexan menores ou maiores co pivote.

  • Agora o elemento pivote está xa colocado na súa posición definitiva e teño a lista separada en dúas sublistas.

  • En cada sublista aplicarei outra vez a ordenación rápida ata dividila en outras dúas sublistas.

  • E así sucesivamente ata rematar de dividir.

Podes ver o algoritmo en acción no seguinte vídeo, extraído da páxina Algorithmique / Programmation de Pascal LOEWENGUTH  con licenza cc-by.

Ordenación dunha baralla de cartas Ordenación burbulla Ordenación batedora

Ordenación gnomo Ordenación rápida: quicksort