Mergesort

Publicado por admin en

ordenamiento mergesort

ORDENAMIENTO POR MEZCLA

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

La particularidad de esta versión en java es que los métodos no son estáticos, con lo cuál, las modificaciones de los parámetros se verán reflejadas también fuera de ellos. Además no se podrá llamar al método principal(“mergesort”) desde el método “main”, porque este es estático. La solución a este pequeño problema sería crear una clase con el algoritmo y en el “main” se creará un objeto de esa clase, y este llamará a “mergesort” para realizar el ordenamiento

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];
 
 
    }

Deja un comentario