Algoritmos de ordenamiento en java.

En este post se mostrarán algunos métodos de ordenamiento; este tipo de algoritmos pone los elementos de un vector -casi siempre- según un orden numérico de manera que sea más fácil la manipulación de estos elementos. También resulta menester que un vector esté ordenado para aplicarle ciertos algoritmos de búsqueda, como el Binary search, que a pesar de ser eficiente debe ir de la mano con alguno de los siguientes algoritmos:

Ordenamiento de burbuja ( Bubble sort ).

Uno de los más sencillos entre los que se veremos. El ordenamiento por burbuja resulta no ser eficiente para vectores con muchos elementos puesto que el orden de complejidad es O(n²)  .Se puede implementar de diversas maneras, mostraremos dos, una usando ciclos for anidados, otra reemplazando uno de estos ciclos for por un while.

El siguiente algoritmo imprime:
[8 10 23 7 6 1 4 2 3 ]
[1 2 3 4 6 7 8 10 23 ]
[4 1 31 8 9 5 10 11 13 ]
[1 4 5 8 9 10 11 13 31 ]

public class BubbleSort {

    public static void manera1(int [] vector){

     for(int i=0; i < vector.length;i++){
      for(int j=1; j < (vector.length - i );j++){
       if(vector[j-1]>vector[j]){
        int aux = vector[j-1];
        vector[j-1] = vector[j];
        vector[j] = aux;
       }
      }
     }
    }

    public static void manera2(int [] vector){
  boolean control;
     while(true){
      control=false;
      for(int i=0;i < (vector.length)-1;i++){
       if(vector[i]>vector[i+1]){
        int aux = vector[i];
        vector[i]=vector[i+1];
        vector[i+1]=aux;
        control = true;
       }
      }
      if(control==false)break;
     }
    }

    public static void printElements(int [] vector){
     System.out.print("[");
     for(int i=0;i < vector.length;i++){
      System.out.print(vector[i] + " ");
     }
     System.out.println("]");
    }


    public static void main (String[]args){
     int [] vector1 = {8,10,23,7,6,1,4,2,3};
     int [] vector2 = {4,1,31,8,9,5,10,11,13};

     printElements(vector1);
     manera1(vector1);
     printElements(vector1);

     printElements(vector2);
     manera2(vector2);
     printElements(vector2);
    }
}

En ambos métodos el proceso para intercambiar de posición dos elementos es el mismo. Se debe crear una variable auxiliar para almacenar el valor de alguno de esos dos elementos llamémoslo A, luego el otro valor (B) pasa a la posición de A, y finalmente en donde teníamos el valor de B, allí se reemplaza este por A, que estaba contenido por la variable auxiliar que mencionamos. Si esta no se creara , el valor de A se perdería al ser reemplazado por el de B.
Analicemos pues los dos métodos que se aplicaron,

manera1: En este método como su puede ver, se usa un for dentro de otro (anidado). En una primera iteración del ciclo externo, lo que hace el for interno es verificar cada par de elementos consecutivos, es decir, elemento 1 vs elemento 2, elemento 2 vs elemento 3 ..... elemento (n-1) vs elemento n, -siendo n el número total de elementos que tiene el vector. De manera que todos los elementos se verifican al menos una vez lo que conduce a que el mayor termine en la última posición.
Continuan las iteraciones del ciclo externo y se verifican los elementos hasta (n-1), -esto debido a que ya conocemos que el mayor está en la posición final y sería en vano que se verificara éste con otro número.- hasta que el segundo mayor termine en la penúltima posición. ...

manera2:  Bastante similar a la anterior con la diferencia de que esta puede realizar menos iteraciones  -siempre que el vector esté relativamente ordenado-. El for funciona de la misma forma en como lo hace en el método anterior. Siempre que haya una modificación de posiciones durante todo el ciclo for, se volverá a realizar el siguiente con el fin de determinar si falta algún cambio. Si esto no ocurre es deducible que del inicio al final del vector, sus elementos están ordenados de manera que nunca se cumplió el if. Acá termina el trabajo del algoritmo.

Ordenamiento por inserción (insertion Sort).

Otro de los sencillos, aunque ineficiente cuando de manejar muchos datos se trata, O(n²).
El ordenamiento por inserción consiste en tomar uno a uno los elementos del vector (excepto el primero), compararlos con los elementos anteriores hasta detenerse si se topa con uno menor al que se está moviendo o bien si llegó al inicio del vector.

Así pues supongamos el vector [ 1, 2, 5, 6, 4, 3]
Primeramente se tomará el 2, se compara con los elementos anteriores. Como 2 > 1 entonces el 2 se quedará allí.
Luego el 5 se compara con el 2, pero como 5 > 2 entonces el 5 también se quedará allí.
Lo mismo pasa con el 6, que al ver que es mayor que su inmediato término anterior se queda allí.
Ahora bien, el 4 se compara con el 6 y debido a que 4 < 6, entonces se cambian de posición. Nuevamente el 4 se intercambia con el 5, hasta que se topa con el 2 y allí no retrocede más.

Así va quedando el vector [ 1, 2, 4, 5, 6, 3]

Ya el algoritmo examinó los valores correspondientes a los índices 0, 1, 2, 3, 4, por lo cual resta examinar el valor que tiene el vector en el índice 5.
Este valor es el 3, que es menor a 6, 5 y 4, llegando a estar en medio del 2 y el 4. Así:

[ 1, 2, 3, 4, 5, 6] 

public class InsertionSort {

    public static int [] organizar(int [] vector){
     for(int i=1 ; i < vector.length; i++){
      for(int j=i; j >= 1; j--){
       if(vector[j] < vector[j-1]){
        int aux = vector [j-1];
        vector[j-1] = vector[j];
        vector[j] = aux;
       }
      }
     }return vector;
    }

    public static void print(int [] vector){
     for(int i = 0; i < vector.length; i++){
      System.out.print(vector[i] + " ");
     }
    }

    public static void main(String [] args){
     int [] array = { 6,11,11,3,4,2,7,-21,4,99};
     int [] vector = organizar(array);
     print(vector);
    }
} 

Ordenamiento por mezcla (MergeSort).

Este algoritmo se puede considerar más eficiente que los antes vistos, puesto que tiene complejidad : O(nlogn). No es tan sencilla su implementación como los algoritmos anteriores, pero es bastante estable y de hecho en ciertos lenguajes, el manejo de arrays utiliza este algoritmo.

Tomada de Wikipedia.

A grandes rasgos el algoritmo, empieza a dividir en mitades al vector inicial (mergeSortHelper), hasta que se encuentran elementos aislados; en este punto y gracias al metódo merge, cada par de vectores se analiza y mezcla de tal forma que se retorna uno organizado, esto pasa tantas veces como se dividió el vector inicial. Finalmente el resultado es el vector organizado. Tratar de hacer un vector ordenar partiendo de dos ordenados resulta más fácil que hacerlo sin que estos últimos no estén ordenados.

 public class MergeSort {

 //Dados dos vectores, los une y retorna uno ordenado.
 public static int[] merge(int[]a,int[]b){

  int []result= new int[a.length+b.length];
  int i=0,j=0;
  for(int k=0; k <  result.length ;k++){
   if (j==b.length || (i < a.length && a[i]<=b[j])) {
    result[k]=a[i];
       i++;
   }
   else {
    result[k]=b[j];
    j++;
   }
  }
  return result;
 }

 //Divide
 public static int[] mergeSortHelper(int []data, int bottom, int top){

  if ( bottom==top) return new int[] {data[bottom]};

    int midpoint=(bottom + top)/2;
  return merge(mergeSortHelper(data,bottom,midpoint),mergeSortHelper(data,midpoint+1,top));

 }

 public static int[] mergeSort(int [] data){
  return mergeSortHelper(data,0,data.length-1);
 }

 public static void print (int [] vect){
  System.out.print("[");
  for(int i=0; i < vect.length;i++){
   System.out.print(vect[i] + " , ");
  }
  System.out.print("]");
 }

 public static void main(String[]args){
  int[] x={-3,-7,-11,6,7,-11,6,7,-11,};
  int [] y = mergeSort(x);
  print( y);
 }
}

Ordenamiento rápido (QuickSort).

También aplica recursividad. Caso promedio O(nlogn).
Consiste en elegir un pivote y de este determinar cuales son menores y mayores, los primeros se ubicarán al lado izquiero del pivote, mientras que los mayores (o iguales) a la derecha.
El vector inicial es partido en dos, justo en donde se halla el pivote. A cada sub-vector se le aplica el mismo proceso recursivamente..
En este algoritmo el pivote es el último elemento del vector.

public class QuickSort {
 // intercambia dos elementos de un vector.
 public static void swap(int[]data, int i, int j){
  int temp=data[i];
  data[i]=data[j];
  data[j]=temp;
 }
 //ubica los elementos menores que el pivote a su izquierda
 //mientras que los mayores a su derecha.
 public static int partition(int[] data, int bottom, int top){
  int  firstAfterSmall=bottom;
  int pivot=data[top];
  for(int i=bottom; i < top;i++){
   if(data[i] <= pivot){
    swap(data,i,firstAfterSmall);
    firstAfterSmall++;
   }
  }
  swap(data,firstAfterSmall,top);
  return firstAfterSmall;
 }
 //aplica el método anterior, luego se divide en dos y a cada división
 //le aplica este mismo proceso -recursivamente-.
 public static void quickSortHelper(int[] data, int bottom, int top){
  if (bottom < top){
   int fasindex=partition(data,bottom,top);
   quickSortHelper( data,  bottom, fasindex-1);
   quickSortHelper( data,  fasindex+1, top);
  }
 }

 public static void quickSort(int[]data){
  quickSortHelper( data,  0, data.length - 1);
 }
 public static void print(int [] data){
  for(int i=0;i < data.length;i++)
   System.out.print(data[i] + " , ");
 }

 public static void main(String[]args){
  int[] x=new int[10];
  for(int i=0;i < x.length;i++)
  x[i]=(int)(Math.random()*100);

  quickSort(x);
  print(x);
 }

}

La variable denominada 'fasindex' que entre otras cosas significa First After Small index, (demasiado largo para llamar una variable así) se usa para determinar en que punto va a ser partido el vector que se maneje en el momento. En un caso ideal el vector se partirá en la mitad, en un caso desastroso en un borde...