Método de Ordenamiento Rápido (Quick Sort)

Método  Quicksort 

Creación

Desde que existe la ciencia de la computación, uno de los mayores problemas con los que los ingenieros se encontraban en su día a día, era el de ordenar listas de elementos. Por su causa, diversos algoritmos de ordenación fueron desarrollados a lo largo de los años y siempre existió un intenso debate entre los desarrolladores sobre cual de todos los algoritmos de ordenación era el más rápido.

El debate finalizó abruptamente en 1960 cuando Sir Charles Antony Richard Hoare desarrolló el algoritmo de ordenación Quicksort, este es el algoritmo de ordenación más rápido. 

¿En que se basa el quicksort?

Se basa en la técnica divide y vencerás, que consiste en ir subdividiendo el array en arrays más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del array como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el array.

Características del Algoritmo QuickSort

En la práctica, es el algoritmo de ordenación más rápido conocido, su tiempo de ejecución promedio es O(n log (n)), siendo en el peor de los casos O(n2), caso altamente improbable. El hecho de que sea más rápido que otros algoritmos de ordenación con tiempo promedio de O(n log (n)) ( como SmoothSort o HeapSort ) viene dado por que QuickSort realiza menos operaciones ya que el método utilizado es el de partición.

Los pasos que realiza este algoritmo son:

1. Selecciona un valor del arreglo como pivote es decir un numero por el cual todos los elementos van a ser comparados.

2. Se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.

3. Luego se organizan los subarreglos que quedaron a mano derecha y izquierda.

Eligiendo el Pivote

La elección del pivote determina las particiones de la lista de datos, por lo tanto es importante intentar que al seleccionar el pivote v las particiones L1 y L3 tengan un tamaño idéntico dentro de lo posible.

De forma gráfica el proceso sería el siguiente:

En código así: 

Clase!
package programa.quicksort.pkg1;


public class Clase {
    
    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)
{
//Pivote Centro de pila
int pivote;
int aux;
pivote = izq;
while(izq!=der)
{//imprimirArreglo(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;

}

private void imprimirArreglo(int arreglo[] )
{
String imp="";
for (int i=0; i<arreglo.length;i++)
{
if(i!=arreglo.length-1)
imp=imp+arreglo[i]+"\n";
else
imp=imp+arreglo[i]+"";
}
System.out.println(imp);

}
}


main!
public static void main(String[] args) {
          long inicio, fin,tiempo;
        inicio= System.currentTimeMillis();
        Clase a = new Clase();
       int array[] = new int[1000];
     for (int x = 0; x<1000; x++){
     array[x]= (int)(Math.random()*100) ;
         System.out.println(x+".- "+array[x]);
     }
        System.out.println("Ahora te lo voy a ordenar, sale???");
     
     a.quicksort(array,0,999);
     for (int x = 0; x<1000; x++){
         System.out.println(x+".- "+array[x]);
     }
     fin=System.currentTimeMillis();
     tiempo=fin-inicio;
        System.out.println("Finalizado en: "+tiempo);
    }
}