Ordenamiento rápido

El ordenamiento rápido (tambien llamado ordonamiento de Hoare o quicksort en inglés) es un algoritmo creado por el científico británico en computación Tony Hoare y basado en la técnica de divide y vencerás. Esta es la técnica quizás la más eficiente y en ella que en la mayoría de los casos da mejores resultados

El algoritmo fundamental es el siguiente:

  1. Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
  2. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
  3. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
  4. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

Representación animada del ordenación rápido :

Representación animada del ordenación rápido

  1. PROCEDIMIENTO quick_sort (vector [1:n], izquierda, derecho )
  2. COMIENZO
  3.   (* separación entre los elementos más pequeños y más grandes como pivote *)
  4.   pared ← izquierda;
  5.   (* el elemento de pivote es la más a la derecha *)
  6.   pivote ← vector[derecho];  
  7.   mover a la izquierda de pared, todos los elementos más pequeños
  8.   mover a la derecha de pared, todos los elementos más grandes
  9.   (* colocando el pivote *)
  10.   colocar el pivote en el lugar de pared
  11.   (* Se continúa con la recursividad *)
  12.   SI (izquierda<pared-1) ENTONCES quick_sort(vector,izquierda,pared-1);
  13.   SI (pared+1<derecho) ENTONCES quick_sort(vector,pared,derecho);
  14. FIN;
  1. let rec quick_sort = function
  2.   | [] -> []
  3.   | pivote::cola -> (* el elemento de pivote es al principio de la lista *)
  4.       let menor, mas_grande = List.partition ((>) pivote) cola in
  5.       (quick_sort menor) @ (pivote :: (quick_sort  mas_grande));;
  1. PROCEDURE quick_sort (var vector : tab;  izquierda, derecho : integer );
  2. Var
  3.   pared,actual : integer;
  4.   tmp, pivote : integer;    
  5. BEGIN
  6.   (* separación entre los elementos más pequeños y más grandes como pivote *)
  7.   pared := izquierda;
  8.   actual := izquierda;
  9.   (* el elemento pivote es el más a la derecha *)
  10.   pivote := vector[derecho];
  11.   REPEAT
  12.     IF (vector[actual] <= pivote) then
  13.     BEGIN
  14.         IF pared <> actual THEN
  15.         BEGIN
  16.             tmp:=vector[actual];
  17.             vector[actual]:=vector[pared];
  18.             vector[pared]:=tmp;
  19.         END;
  20.         pared := pared + 1;
  21.     END;
  22.     actual := actual + 1;
  23.   UNTIL actual>derecho;
  24.   (* Se continúa con la recursividad *)
  25.   IF (izquierda<pared-1) THEN quick_sort(vector,izquierda,pared-1);
  26.   IF (pared+1<derecho) THEN quick_sort(vector,pared,derecho);
  27. END;
  1. def quick_sort(vector):
  2.     if not vector:
  3.         return []
  4.     else:
  5.         pivote = vector[-1]
  6.         menor = [x for x in vector     if x <  pivote]
  7.         mas_grande = [x for x in vector[:-1] if x >= pivote]
  8.         return quick_sort(menor) + [pivote] + quick_sort(mas_grande)
  1. void quick_sort (int *vector, int tamano) {
  2.     int pared, actual, pivote, tmp;
  3.     if (tamano < 2) return;
  4.     // el elemento de pivote es la más a la derecha
  5.     pivote = vector[tamano - 1];
  6.     pared  = actual = 0;
  7.     while (actual<tamano) {
  8.         if (vector[actual] <= pivote) {
  9.             if (pared != actual) {
  10.                 tmp=vector[actual];
  11.                 vector[actual]=vector[pared];
  12.                 vector[pared]=tmp;              
  13.             }
  14.             pared ++;
  15.         }
  16.         actual ++;
  17.     }
  18.     quick_sort(vector, pared - 1);
  19.     quick_sort(vector + pared - 1, tamano - pared + 1);
  20. }

Lo más importante del algoritmo es elegir bien el pivote. En la animación de arriba, se elige el pivote que se encuentra al final de la lista. Sin embargo, otras estrategias son posibles.

Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 


La eficiencia del algoritmo depende de la posición en la que termine el pivote elegido. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente. En el caso promedio, el orden es O(n•log n). Y no es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

La aplicación a continuación calcula el rendimiento dependiendo de la elección del pivote.

Rendimiento del algoritmo
Pivote :
Número de términosPasoComparacionesIntercambiosSuma
000
Número de términosPasoComparacionesIntercambiosSuma
000
Número de términosPasoComparacionesIntercambiosSuma
000
Número de términosPasoComparacionesIntercambiosSuma
000
Número de términosPasoComparacionesIntercambiosSuma
000