Sorting algorithm - Merge Sort


  • administrators

    Este algoritmo es muy rapido pero consume mucha memoria no sugiero usarlo si la cantidad de items que necesitas ordenar es mayo a 40000.

    A continuacion te dejo mi implementacion en C++.

    #include <time.h>
    #include <iostream>
    #include <stdio.h>
    #include <cmath>
    using namespace std;
    
    const int MAX = 40000;
    int data[MAX+1];
    
    void mergeSort(int desde, int hasta) {
        if (hasta - desde <= 1) return;
        int middle = (desde + hasta) / 2;
        mergeSort(desde, middle);
        mergeSort(middle, hasta);
        int dPtr, lPtr, rPtr, result[hasta];
        dPtr = lPtr = desde;
        rPtr = middle;
        while (dPtr < hasta) {
            if (lPtr == middle)
                result[dPtr++] = data[rPtr++];
            else if (rPtr == hasta)
                result[dPtr++] = data[lPtr++];
            else if (data[lPtr] < data[rPtr])
                result[dPtr++] = data[lPtr++];
            else
                result[dPtr++] = data[rPtr++];
        }
        while (desde < hasta)
            data[desde++] = result[desde];
    }
    
    int main() {
        int n;
        printf("Ingresar cuandos datos se ordenarann");
        scanf("%d", &n);
        for (int i=0; i < n ; i++)
            data[i] = rand() % 1000000000;
        mergeSort(0, n); //aqui ordena el array de enteros
        for (int i=0; i < n ;i++)
        cout << data[i] << " ";
    }
    

    Como puedes ever el algoritmo es simple, separa las colecciones del Array hasta que los items quedan solos luego las une (Merge es Unir en ingles) pero al mezclarse los almacena en el orden correcto, este algoritmo no necesita comparar todos los elementos ya que las colecciones que necesitamos ordenar ya están ordenadas y la tarea solo es almacenarlas en orden.

    muy importante a la hora de crear los sub-arrays o sub-conjuntos para tener una velocidad aceptable es necesario solo pasar apuntadores o indices, si implementas este algoritmo creando nuevos Arrays en cada division tu algoritmo sera mas pesado.

             {18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11} // input / array desordenado
            {18, 6, 9, 1, 4}   {15, 12, 5, 6, 7, 11} // split
          {18, 6}  {9, 1, 4}   {15, 12, 5}  {6, 7, 11} // split
        {18} {6}  {9} {1, 4}   {15} {12, 5} {6}  {7, 11} // split
       {18} {6}  {9} {1} {4}   {15} {12} {5} {6}  {7} {11} // todos quedaron separados.
        {18} {6}  {9} {1, 4}   {15} {5, 12} {6}  {7, 11} // merge
          {6, 18}  {1, 4, 9}   {5, 12, 15} {6, 7, 11} // merge
            {1, 4, 6, 9, 18}   {5, 6, 7, 11, 12, 15} // merge
             {1, 4, 5, 6, 6, 7, 9, 11, 12, 15, 18} // resultado