Método de Ordenamiento por Mezclas (Merge Sort)

Equipo 5 (Merge-Sort)

Integrantes:

-Liliana Guadalupe Vera Zapata

-Cristian Jareth Santibáñez Ramírez  

-Leonardo Javier Ortega Cabrera

-Eduardo David Ponce Ramírez

-Diego Armando Vallejo Ayala

-Néstor Javier Romero Flores

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás.

1. Si la lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. De lo contrario hacer lo siguiente:

1. Dividir la lista al medio, formando dos sublistas de (aproximadamente) el mismo tamaño cada una.

1. Ordenar cada una de esas dos sublistas (usando este mismo método).

1. Una vez que se ordenaron ambas sublistas, intercalarlas de manera ordenada.

Este método se basa en la siguiente idea:

Por ejemplo, si la lista original es [6, 7, -1, 0, 5, 2, 3, 8] deberemos ordenar recursivamente [6, 7, -1, 0] y [5, 2, 3, 8] con lo cual obtendremos [-1, 0, 6, 7] y [2, 3, 5, 8]. Si intercalamos ordenadamente las dos listas ordenadas obtenemos la solución buscada: [-1, 0, 2, 3, 5, 6, 7, 8].

Presentacion De Merge - Sort

Codigo Merge-Sort

package javaapplication1;

// fichero Mergesort.java

import java.util.Date;

public class JavaApplication1 {

    public static void main(String [] arg) {

        int n = 10000;

        // generar n números aleatoriamente

        int [] v = new int[n];

        for (int i=1; i<n; i++) {

            v[i] = (int) (Math.random()*100);

        }

        

        System.out.println("Vector antes de ordenar:"); 

        for (int i=1; i<n; i++) {

            System.out.println("v["+i+"] = "+v[i]);

        }

        // ordenar los números

        Date antes = new Date();

        mergesort(v, n);

        Date despues = new Date();

        long etime = despues.getTime()-antes.getTime();

        System.out.println("\nTiempo utilizado por mergesort(): " +

                           etime + " milisegundos.");

        

        System.out.println("\nVector despues de ordenar:"); 

       for (int i=0; i<n; i++) {

            System.out.println("v["+i+"] = "+v[i]);

        }

        System.out.println("Ya he terminado.");

    } // fin de main()

    // mezclar ordenadamente dos ficheros ordenados

    // na, nb número de elementos de los conjuntos a y b

    // ia, ib, ic posición donde empiezan los conjuntos en 

    //     los vectores a[], b[] y c[]

    static void merge(int a[], int ia, int b[], int ib, 

                      int c[], int ic, int na, int nb)

    {

        int i=ia, j=ib, k=ic;

        // copiar ordenadamente a y b sobre c

        while (i<na+ia && j<nb+ib) {

            if (a[i] < b[j]) {

                c[k++] = a[i++];

            }

            else {

                c[k++] = b[j++];

            }

        }

        

        while (i<na+ia) {

            c[k++] = a[i++];

        }

        while (j<nb+ib) {

            c[k++] = b[j++];

        }

    } // fin de merge()

    public static void mergesort(int vect[], int n)

    {

        // se supone que n debe ser potencia de 2

        int [] aux = new int[n];

        // valores de k: 1, 2, 4, 8, ...

        for (int k=1; k<n; k*=2) {

            // valores de j = 0, 2, 4, 6, 8, ... (k=1)

            //            j = 0, 4, 8,12,16, ... (k=2)

            //for (j = 0; j<n-k; j+=2*k) // para n potencia de 2

            for (int j = 0; j<=n-k; j+=2*k) {

                merge( vect, j, vect, j+k, aux, j, 

                      Math.min(k,n-j), Math.min(k,n-j-k) );

            }

            System.arraycopy(aux, 0, vect, 0, n);

        }

        aux = null;

    } // fin de mergesort()

} // fin de la clase Mergesort

Animacion de Merge Sort