Mergesort en Java

ordenamiento mergesort

El algoritmo mergesort en Java es muy común, pero antes de la implementación conozcamos de que trata esta algoritmo

Merge sort(ordenamiento por mezcla) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás, que fue desarrollado por John Von Neumann en 1945.

El ordenamiento externo se requiere cuando la información a ordenar no cabe en la memoria principal de la computadora(RAM) y un tipo de memoria más lenta(Disco Duro) tiene que utilizarse para el proceso de ordenamiento.

ALGORITMO DE ORDENAMIENTO

El funcionamiento del algoritmo es el siguiente:

  • Si la longitud de la lista es 0 o 1, la lista ya está ordenada. En cualquier otro caso:
    • Dividir la lista en dos sublistas de la mitad de tamaño
    • Ordenar cada sublista recursivamente
    • Mezclar las dos sublistas en un sola lista ordenada

EXPLICACIÓN DEL ALGORITMO EN JAVA

El código anterior esta dividido en dos métodos:

  • mergesort: tiene cómo función dividir recursivamente en mitades el vector utilizando los límites y aplicar el método de mezcla en las mitades.
  • merge: método de mezcla que tiene como función mezclar y ordenar porciones del vector dadas con los limites(li,mitad,ls)
    • Se hacen uso de parámetros auxiliares:
      • aux: vector auxiliar donde se irá almacenando el vector ordenado
      • i, j, k: indices para la parte izquierda, derecha y vector resultante.
    • El método esta formado por 4 bucles:
      1. Mientras que el indice «i» esta en la parte izquierda y «j» en la derecha, se realiza una condición, dependiendo de ella en la posición «k» de «aux» se almacenará la posición «i» o «j» del vector original. Además se incrementarán los indices mediante post-incremento(incremento después de uso) para la siguiente interacción.
      2. Bucle que copia los elementos que estaban en la posición correcta de la parte izquierda mediante los indices correspondientes
      3. Misma función que el anterior, pero, para la parte derecha del vector
      4. Bucle «for» que simplemente copia los datos del vector auxiliar en el original

ordenamiento de un vector mediante mezcla

ALGORITMO EN JAVA

Una posible implementación del algoritmo mergesort en Java se puede ver a continuación:

public void mergesort(int vector[],  int li, int ls){
   int mitad;
   if (ls > li){
     mitad = (ls + li)/2;
     mergesort(vector, li, mitad);
     mergesort(vector, mitad+1, ls);
     merge(vector, li, mitad+1, ls);
   }
   
 }
 
 private void merge(int vector[], int li, int mitad, int ls){
   int[] aux = new int[vector.length];//Vector auxiliar
   int contador = 0;
   int i = li;//Indice de la parte izquierda
   int j = mitad;//Indice de la parte derecha
   int k = li;//Indice del vector resultante
   
   while ((i <= mitad - 1) && (j <= ls)){
     //Mientras que i esta en la parte izq y j en la dcha
     if (vector[i] <= vector[j])
       aux[k++] = vector[i++];
     else
       aux[k++] = vector[j++];
     
   }
   //Copia los elementos que estaban en la posicion correcta:
   while (i <= mitad - 1)
     aux[k++] = vector[i++];
 
   while (j <= ls)
     aux[k++] = vector[j++];
     
   //Copia los elementos en el vector original
   for (i=li; i <= ls; i++)
     vector[i] = aux[i];

 

curso programación en java

Deja un comentario