Método de ordenación MergeSort

El método MergeSort es un algoritmo de ordenación recursivo con un número de comparaciones entre elementos del array mínimo.
Su funcionamiento es similar al Quicksort, y está basado en la técnica divide y vencerás.
De forma resumida el funcionamiento del método MergeSort es el siguiente:
- Si la longitud del array es menor o igual a 1 entonces ya está ordenado.
- El array a ordenar se divide en dos mitades de tamaño similar.
- Cada mitad se ordena de forma recursiva aplicando el método MergeSort.
- A continuación las dos mitades ya ordenadas se mezclan formando una secuencia ordenada.
La ordenación mergesort se puede implementar en Java de la siguiente forma:
public static void mergesort(int A[],int izq, int der){
    if (izq < der){
            int m=(izq+der)/2;
            mergesort(A,izq, m);
            mergesort(A,m+1, der);                                                                                
            merge(A,izq, m, der);                                                                                 
    }
}
El método ordena un array A de enteros desde la posición izq hasta la posición der. En la primera llamada al método recibirá los valores izq = 0, der = ELEMENTOS-1.
Primero se calcula el elemento central m. A continuación la primera parte del array, desde izq hasta m y la segunda parte del array, desde m+1 hasta der, se mezclan mediante llamadas recursivas al método mergesort.
La recursión termina cuando izq == der, es decir, cuando un subarray contiene solamente un elemento.
La operación principal de mezcla la realiza el método merge. Este método se puede implementar de varias formas, la más usual es la siguiente:
public static void merge(int A[],int izq, int m, int der){
   int i, j, k;
   int [] B = new int[A.length]; //array auxiliar
   for (i=izq; i<=der; i++)      //copia ambas mitades en el array auxiliar                                       
        B[i]=A[i];

   i=izq; j=m+1; k=izq;
     
   while (i<=m && j<=der) //copia el siguiente elemento más grande                                      
          if (B[i]<=B[j])
              A[k++]=B[i++];
          else
              A[k++]=B[j++];
        
   while (i<=m)         //copia los elementos que quedan de la
         A[k++]=B[i++]; //primera mitad (si los hay)
}
De forma gráfica podemos representar el funcionamiento del algoritmo de la siguiente forma:

El tiempo de ejecución promedio del método MergeSort es O(n log n).


15 comentarios:

  1. el tiempo de ejecución el muy largo, no me muestra el array.

    ResponderEliminar
    Respuestas
    1. El arreglo esta vació, ademas no hay ninguna instrucción de imprimir. De esta forma no te mostrará nada.

      Eliminar
  2. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  3. y esta bien que no devuelva nada. los metodos de ordenamiento solo hacen eso.... ordenar...
    pueden hacer un metodo que imprima arreglos y mandar como parametro el arreglo ordenado

    ResponderEliminar
  4. a este metodo no le faltara algunas llaves? Intente muchas veces y nada:'v
    public static void merge(int A[],int izq, int m, int der){
    int i, j, k;
    int [] B = new int[A.length]; //array auxiliar
    for (i=izq; i<=der; i++) //copia ambas mitades en el array auxiliar
    B[i]=A[i];

    i=izq; j=m+1; k=izq;
    while (i<=m && j<=der) //copia el siguiente elemento más grande
    if (B[i]<=B[j])
    A[k++]=B[i++];
    else
    A[k++]=B[j++];
    while (i<=m) //copia los elementos que quedan de la
    A[k++]=B[i++]; //primera mitad (si los hay)
    }

    ResponderEliminar
  5. En el ultimo while ordenas los de la primera mitad si no se han ordenado, pero no ordenas la otra mitad si estas en la misma situacion?

    ResponderEliminar
  6. muuy buena nota de manera decreciente como seria?

    ResponderEliminar
    Respuestas
    1. No se puede ordenar de manera decreciente, usando Algoritmos de Ordenamiento, lo que puedes hacer es colocar todos los datos ordenados en una pila y desde ahi sacarlos para tener el orden decreciente

      Eliminar
    2. par la forma decreciente en vez de poner if (B[i]<=B[j]), tienes que escribirlo al reverso if (B[i]>=B[j])

      Eliminar
  7. Este comentario ha sido eliminado por el autor. Gian :v

    ResponderEliminar
  8. Desarrollar una aplicación para realizar el registro de clientes. Los datos a almacenar son código, nombres, dni, genero, correo y celular. Utilizar para este ejercicio ordenamiento recursivo QuickSort.

    ResponderEliminar
  9. private static void ordenamientoPorMergeSort(double[] notas,int izquierda, int mitad) {
    izquierda = 0;
    int derecha = NOTAS_TOTALES.length - 1;
    if(izquierda < derecha) {
    mitad = (izquierda + derecha) / 2;
    ordenamientoPorMergeSort(notas, izquierda, mitad);
    ordenamientoPorMergeSort(notas, mitad + 1, derecha);
    mezcla(notas, izquierda, mitad, derecha);
    }

    }

    private static void mezcla(double[] notas, int izquierda, int mitad, int derecha) {
    int i, j, k;
    double[] aux = new double[NOTAS_TOTALES.length];
    for(i = mitad + 1; i > izquierda; i--) {
    aux[i - 1] = notas[i - 1];
    }

    i = izquierda;
    j = mitad + 1;
    k = izquierda;

    while(i <= mitad && j <= derecha) {
    if(aux[i] <= aux[j]) {
    notas[k++] = aux[i++];
    }else {
    notas[k++] = notas[j++];
    }
    }
    while(i <= mitad) {
    notas[k++] = aux[i++];
    }

    }

    ResponderEliminar
  10. Corre muy bien, gracias

    ResponderEliminar