Ordenacion Quicksort

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) i++; while(vector[j]>pivote) j--;
 If (i<=j){ auxiliar=vector[j];
 vector[j]=vector[i];
 vector[i]=auxiliar; i++; j--;
 }
 }
 while (i<=j);
 if(primero<j) ordenarQuicksort(vector,primero, j);
 if(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
GRACIAS

Ordenacion Quicksort

Cargado por

Copyright:

Formatos disponibles

Ordenacion Quicksort

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Ordenacion Quicksort

Cargado por

Copyright:

Formatos disponibles

Quicksort

 Este método es una mejora sustancial del método de intercambio directo y

 es un algoritmo basado en la técnica de divide y vencerás, que permite, en

 El algoritmo original es recursivo, pero se utilizan versiones iterativas para

 La idea central de este algoritmo consiste en los siguiente:

 Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que

Por lo tanto: C = (n-1) + 2(n -1)/2 + 4(n - 1)/4 + ....... + (n - 1)(n

Lo cual es lo mismo que: C= (n - 1) + (n- 1) + ....... + (n - 1)

También podría gustarte