Ordenar dividiendo

Partir por la mitad, ordenar cada mitad, y juntarlas de una pasada.

1Por qué

La lección 27 midió el ordenamiento por intercambio y el número fue feo: al doblar los datos, el trabajo se cuadruplica. Ordenar un millón de cosas así no es lento, es imposible.

El problema de fondo es que compara todo con todo. Y ya viste dos veces cómo se sale de ahí: el árbol de la lección 20 y la búsqueda de la 28 ganan porque parten el problema por la mitad. Aquí se hace lo mismo.

La idea completa cabe en tres frases. Parte la lista en dos mitades. Ordena cada mitad —con esta misma función, que para eso está la recursión—. Y junta las dos mitades ya ordenadas.

Lo que hace que funcione es la última parte: juntar dos listas ya ordenadas es barato. No hay que comparar todo con todo; basta mirar el primero de cada una, tomar el menor, y seguir. Cada dato se mira una sola vez.

El resultado es que doblar los datos ya no cuadruplica el trabajo: apenas lo dobla y un poquito. Un millón de datos que con el método anterior serían medio billón de comparaciones, aquí son unos veinte millones. La diferencia no es de velocidad, es de si el programa termina o no.

Hace falta un arreglo auxiliar donde ir dejando lo mezclado. Ese es el precio: este método gasta más sitio a cambio de tiempo, y es un intercambio que vas a ver muchas veces.

2Míralo andar

Este programa funciona. Léelo, y después ejecútalo sin cambiar nada.

#include <stdio.h>
 
void mezclar(int v[], int a, int m, int b, int tmp[])
{
    int i = a;
    int j = m + 1;
    int k = a;
 
    while (i <= m && j <= b)
    {
        if (v[i] <= v[j]) tmp[k++] = v[i++];
        else tmp[k++] = v[j++];
    }
 
    while (i <= m) tmp[k++] = v[i++];
    while (j <= b) tmp[k++] = v[j++];
 
    for (int t = a; t <= b; t++)
        v[t] = tmp[t];
}
 
void ordenar(int v[], int a, int b, int tmp[])
{
    if (a >= b) return;
 
    int m = (a + b) / 2;
    ordenar(v, a, m, tmp);
    ordenar(v, m + 1, b, tmp);
    mezclar(v, a, m, b, tmp);
}
 
int main(void)
{
    int v[6] = {5, 3, 8, 1, 9, 2};
    int tmp[6];
 
    ordenar(v, 0, 5, tmp);
 
    for (int i = 0; i < 6; i++)
        printf("%d ", v[i]);
    printf("\n");
    return 0;
}

línea 11
Aquí está lo barato. Se mira el primero de cada mitad y se toma el menor. Cada dato se mira una vez.
línea 15
Una mitad se acaba antes que la otra. Lo que sobra ya está ordenado, así que se copia tal cual.
línea 23
Un trozo de un solo dato ya está ordenado. Es donde para la recursión.
línea 26
Se llama a sí misma sobre cada mitad. Cuando vuelven, las dos están ordenadas y solo queda juntarlas.

3Ahora tú

A mezclar le falta lo único que hace: tomar el menor de las dos mitades. Escribe esas dos líneas, para que salga: 1 2 3 5 8 9

#include <stdio.h>
 
void mezclar(int v[], int a, int m, int b, int tmp[])
{
    int i = a;
    int j = m + 1;
    int k = a;
 
    while (i <= m && j <= b)
    {
        
    }
 
    while (i <= m) tmp[k++] = v[i++];
    while (j <= b) tmp[k++] = v[j++];
 
    for (int t = a; t <= b; t++)
        v[t] = tmp[t];
}
 
void ordenar(int v[], int a, int b, int tmp[])
{
    if (a >= b) return;
 
    int m = (a + b) / 2;
    ordenar(v, a, m, tmp);
    ordenar(v, m + 1, b, tmp);
    mezclar(v, a, m, b, tmp);
}
 
int main(void)
{
    int v[6] = {5, 3, 8, 1, 9, 2};
    int tmp[6];
 
    ordenar(v, 0, 5, tmp);
 
    for (int i = 0; i < 6; i++)
        printf("%d ", v[i]);
    printf("\n");
    return 0;
}

↖︎ Tu parte va aquí. Son dos líneas: qué hacer si gana el de la izquierda, y qué hacer si gana el de la derecha.

Ordenar dividiendo

1Por qué

2Míralo andar

3Ahora tú

Ejecutar

Lo que dice tu programa

Qué pasó

4Qué guarda tu programa

La pila