"Ordenamiento quicksort"

El ordenamiento rápido (quicksort en inglés) 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 vector desordenado es enviado a la función "quicksort()"
Al llegarle el vector a la función, se toma el primer elemento del vector (o cualquiera; Nota: en nuestro caso tomamos el primero) y se considera ese elemento como "pivote" o "comodín".
Después se recorre todo el vector; durante el recorrido, se va buscando los numeros menores que el pivote, sí el elemento del vector en una vuelta es menor que el pivote, entonces se manda a la izquierda del pivote, de lo contrario no se hace nada. Esto provocará que después de recorrer todo el vector, todos los elementos menores que el pivote quedarán a la izquierda de este y los mayores al pivote a la derecha.
Se envía recursivamente la mitad izquierda del vector (números menores que el pivote sin tomar en cuenta el mismo pivote) a la función quicksort
Se envía recursivamente la mitad derecha del vector (números mayores que el pivote sin tomar en cuenta el mismo pivote) a la función quicksort






Enseguida presentamos un ejemplo con su respectivo codigo y una imagen de como de muestra corriendo


public class quicksort {

public static void qsort(Comparable [] c, int inicio, int fin) {

if(fin<=inicio) return;
Comparable comp=c[inicio];
int i=inicio, j=fin+1;
for(;;){
do i++; while(i do j--;while(j>inicio && c[j].compareTo(comp)>0 );
if (j<=i) break;
Comparable tmp=c[i];
c[i]=c[j];
c[j]=tmp;

}
c[inicio]=c[j];
c[j]=comp;
qsort(c, inicio, j-1);
qsort(c, j+1, fin);
}

public static void qsort(Comparable[] c){
qsort(c, 0, c.length-1);
}
public static void main(String[] args){
int i;
Double[] arr=new Double [1000];
System.out.println("Elementos aleatorios:");
for(i=0; i arr[i]=new Double((int)(Math.random()*99));
System.out.print(arr[i]+"");
}


System.out.println("\nelementos ordenados:");
for(i=0; i System.out.print(arr[i]+"");

}
}




Ahora el mismo ejemplo solo que con los valores flotantes:


public class quicksort {

public static void qsort(Comparable [] c, int inicio, int fin) {

if(fin<=inicio) return;
Comparable comp=c[inicio];
int i=inicio, j=fin+1;
for(;;){
do i++; while(i
do j--;while(j>inicio && c[j].compareTo(comp)>0 );
if (j<=i) break;
Comparable tmp=c[i];
c[i]=c[j];
c[j]=tmp;

}
c[inicio]=c[j];
c[j]=comp;
qsort(c, inicio, j-1);
qsort(c, j+1, fin);
}

public static void qsort(Comparable[] c){
qsort(c, 0, c.length-1);
}
public static void main(String[] args){
int i;
Double[] arr=new Double [1000];
System.out.println("Elementos aleatorios:");
for(i=0; i
arr[i]=new Double((int)(Math.random()*99));
System.out.print(arr[i]+"");
}


System.out.println("\nelementos ordenados:");
for(i=0; i
System.out.print(arr[i]+"");

}
}