Ordenar por intercambio

Compara vecinos y cámbialos de sitio hasta que ninguno sobre.

1Por qué

Ya viste dos veces que tener los datos ordenados cambia todo: el árbol de la lección 20 descarta media búsqueda, y la lista de la 25 nunca hay que ordenarla porque cada dato entra en su sitio.

Pero muchas veces los datos llegan como llegan —de un archivo, del teclado— y hay que ordenarlos después.

La forma más simple de hacerlo es también la más fácil de entender: mira dos vecinos, y si están al revés, cámbialos. Repite hasta que no quede ninguno al revés. En cada pasada, el mayor de los que quedan burbujea hasta el final, y de ahí el nombre.

El cambio de sitio necesita una cajita extra, exactamente como en la lección 9: si copias uno sobre el otro sin guardarlo antes, pierdes el valor y acabas con el mismo número dos veces.

Fíjate en el n - 1 - i del ciclo de dentro. No es un detalle de estilo: después de cada pasada, el final de la lista ya está ordenado, y volver a mirarlo sería trabajo tirado. Este algoritmo es lento, y en la lección siguiente vas a medir cuánto.

2Míralo andar

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

#include <stdio.h>
 
int main(void)
{
    int v[5] = {5, 2, 9, 1, 7};
    int n = 5;
 
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (v[j] > v[j + 1])
            {
                int t = v[j];
                v[j] = v[j + 1];
                v[j + 1] = t;
            }
 
    for (int i = 0; i < n; i++)
        printf("%d ", v[i]);
    printf("\n");
    return 0;
}

línea 8
Una pasada por cada elemento menos uno. Con la última ya colocada, la lista entera lo está.
línea 9
El - i es lo que evita repasar el final, que ya quedó ordenado en las pasadas anteriores.
línea 10
Aquí vive la dirección del orden. Con > sale de menor a mayor; con <, al revés.
línea 12
La cajita extra, igual que en la lección 9: sin ella se pierde uno de los dos valores.

3Ahora tú

A este ordenamiento le falta la pregunta que decide si hay que cambiar. Escríbela para que salga: 1 2 5 7 9

#include <stdio.h>
 
int main(void)
{
    int v[5] = {5, 2, 9, 1, 7};
    int n = 5;
 
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (/* Escribe tu orden aquí */)
            {
                int t = v[j];
                v[j] = v[j + 1];
                v[j + 1] = t;
            }
 
    for (int i = 0; i < n; i++)
        printf("%d ", v[i]);
    printf("\n");
    return 0;
}

Ordenar por intercambio

1Por qué

2Míralo andar

3Ahora tú

Ejecutar

Lo que dice tu programa

Qué pasó

4Qué guarda tu programa

La pila