Java básico #23

Quicksort

Este es el algoritmo de ordenación más rápido.

Se basa en la técnica "divide y vencerás", la cual consiste en ir dividiendo el array en otros arrays más pequeños, y ordenar estos. Para esto, se toma un valor de array pivote y se mueven todos los elementos menores que el pivote a su izquierda y los mayores, a su derecha. Después se aplica lo mismo a cada una de las partes en las que queda dividido el array.
A continuación de elegir el pivote, se realizan dos búsquedas:

• Una de izquierda a derecha, buscando un elemento mayor que el pivote
• Una de derecha a izquierda, buscando un elemento menor que el pivote

Una vez se hayan encontrado, se intercambian y se vuelve a realizar la búsqueda. 

Este método es recursivo.

Ejemplo:

package OrdenamientoArraysQuicksort;
 
public class Main {
 public static void main(String[] args){
  int numeros[] = {4,87,24,65,98,7,1};
  quicksort(numeros,0,numeros.length-1);
  for(int i=0;i<numeros.length;i++) System.out.println(numeros[i]);
 
 }
 
 public static void quicksort(int A[], int izq, int der) {
 
    int pivote=A[izq];
    int i=izq;
    int j=der; 
    int aux;
 
    while(i<j){            
       while(A[i]<=pivote && i<j) i++; 
       while(A[j]>pivote) j--;       
       if (i<j) {                                      
           aux= A[i];                 
           A[i]=A[j];
           A[j]=aux;
       }
     }
     A[izq]=A[j]; 
     A[j]=pivote;
     if(izq<j-1)
        quicksort(A,izq,j-1);
     if(j+1 <der)
        quicksort(A,j+1,der); 
  }
 
}