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.
Descripcion del algortimo:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
La idea central de este algoritmo consiste en lo 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.
Análisis 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.
public class Ordenador {
public int[] quicksort(int numeros[])
{
return quicksort(numeros,0,numeros.length-1);
}
public int[] quicksort(int numeros[],int izq,int der)
{
if(izq>=der)
return numeros;
int i=izq,d=der;
if(izq!=der)
{
int pivote;
int aux;
pivote = izq;
while(izq!=der)
{imprimeArreglo(numeros);
while(numeros[der]>=numeros[pivote] && izq<der)
der--;
while(numeros[izq]<numeros[pivote] && izq<der)
izq++;
if(der!=izq)
{
aux = numeros[der];
numeros[der]= numeros[izq];
numeros[izq]=aux;}
}
if(izq==der){
quicksort(numeros,i,izq-1);
quicksort(numeros,izq+1,d);
}
}
else
return numeros;
return numeros;
}
public void imprimeArreglo(int arreglo[])
{
String imp="";
for(int i=0;i<arreglo.length;i++)
{
if(i!=arreglo.length-1)
imp=imp+arreglo[i]+",";
else
imp=imp+arreglo[i]+"";
}
System.out.println(imp);
}
public static void main(String[] args) {
int array[] ={4,2,5,7,6,1,3};
Ordenador a = new Ordenador();
a.quicksort(array);
}
}
