Quicksort

Quicksort el ordenamiento rápido
El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna.

Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
Fue desarrollada por C. Antony R. Hoare en 1960.

Descripción del algoritmo

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

La idea central de este algoritmo consiste en los siguiente: Se toma un elemento x de una posición cualquiera del arreglo. Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x. Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

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.

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

Algoritmo en Java:
void ordenarQuicksort(int[] vector, int primero, int ultimo){
int i=primero, j=ultimo;
int pivote=vector[(primero+ultimo)/2];
int auxiliar;
do{
while(vector[i]pivote) j--;
If (i<=j){ auxiliar=vector[j];
vector[j]=vector[i];
vector[i]=auxiliar; i++; j--;
}
}
while (i<=j);
if(primeroif(ultimo>i) ordenarQuicksort(vector,i, ultimo);
}
Analisis del algoritmo:
Estabilidad: No es estable.
Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila.

Ventajas:
Muy rápido.
No requiere memoria adicional.
Desventajas:
Implementación un poco más complicada.
Recursividad (utiliza muchos recursos).
Mucha diferencia entre el peor y el mejor caso.

Analisis del algoritmo:

Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada el elemento que ocupa la posición central del conjunto de datos a analizar, el número de pasadas necesarias para ordenar es del orden de Log n. Respecto al número de comparaciones, si el tamaño del arreglo es una potencia de 2, en la primera pasada realizará (n-1) comparaciones, en la 2ª pasada realizará (n-1)/2 comparaciones, pero en 2 conjuntos diferentes, en la tercera pasada realizará (n-1)/4 comparaciones pero en 4 conjuntos diferentes y así sucesivamente. Por lo tanto: C = (n-1) + 2(n -1)/2 + 4(n - 1)/4 + ....... + (n - 1)(n - 1)/(n - 1) Lo cual es lo mismo que: C= (n - 1) + (n- 1) + ....... + (n - 1)

EJEMPLO

El elemento divisor será el 6:
5 - 3 - 7 - 6 - 2 - 1 - 4
p
Comparamos con el 5 por la izquierda y el 4 por la derecha con el pivote.
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
5 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
 
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
3 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
 
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
7 NO es menor que 6 y 4 NO es mayor que 6.
 
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
Como i=2 y j=6, i es menor que j, así que intercambiamos los valores de a[i] y de a[j].
5 - 3 - 4 - 6 - 2 - 1 - 7
Como i sigue siendo menor que j, se vuelve a aplicar el mismo algoritmo hasta que se crucen los índices i y j, siendo este momento cuando se vuelve a llamar al método quicksort con la parte del array que es menor que el pivote y, por otro lado, con la parte que es mayor. (Sólo se muestra a continuación una parte, ya que es igual su ejecución en ambas):
1 - 3 - 2
1 es menor que 3: avanzamos por la izquierda. 2 NO es mayor: no avanzamos por la derecha. Como i no es menor que el pivote, se para, y como i es menor que j, se intercambian a[i] y a[j], resultando ya ordenador este subarray:
1 - 2 - 3
El mismo procedimiento se aplicará al otro subarray. Al finalizar y unir todos los subarrays queda el array inicial ordenado en forma ascendente.
1 - 2 - 3 - 4 - 5 - 6 - 7

2 comentarios:

  1. vil copia de ConClase ¬¬' http://c.conclase.net/orden/quicksort.html

    al menos pon los creditos ... xD

    ResponderEliminar
  2. pèro bueno.. derre tienen por ahi un quicksort usando pilas :| nos e no s eme ocurre nada xD

    alaoz' colegas

    visitenme en http://mikaminogeek.blogspot.com/

    ResponderEliminar