Sorting: bubble, selection, and insertion · ⁨Ordenación: burbuja, selección e inserción⁩

Ordenar un array

• Ordenar reorganiza un array para que los elementos vayan de menor a mayor.
• Ordenamos in situ: movemos los elementos dentro del mismo array, sin devolver ningún valor.
• Tres métodos clásicos hacen esto: ordenamiento por burbuja, inserción y selección.

Intercambiar dos elementos

• Todo algoritmo de ordenación necesita intercambiar dos elementos. Guarde uno en una variable temporal, luego sobreescriba el otro.
• int t = a[i]; a[i] = a[j]; a[j] = t; intercambia las posiciones i y j.
• Olvidar la variable temporal hace perder uno de los valores — siempre guárdela.

Ordenamiento por burbuja

• Recorra el array y compare cada par de vecinos: a[j] y a[j + 1].
• Si están en el orden incorrecto, intercámbielos. El valor más grande "burbujea" hacia el final.
• Repita los pasadas hasta que todo el array esté ordenado.

Ordenamiento por inserción

• Trate la parte izquierda del array como ya ordenada, y agrándela un elemento a la vez.
• Tome el siguiente elemento como clave, desplace los elementos ordenados mayores hacia la derecha, luego inserte la clave en el hueco.
• Así es como muchas personas ordenan cartas de juego en su mano.

#include <stdio.h>

int main(void) {
    int a[] = {3, 1, 2};
    // one bubble pass: compare neighbours and swap if out of order
    for (int j = 0; j < 2; j++) {
        if (a[j] > a[j + 1]) {
            int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
        }
    }
    printf("%d %d %d\n", a[0], a[1], a[2]);   // 1 2 3
    return 0;
}

Errores comunes

• El ordenamiento por burbuja, selección e inserción son todos O(n²).
• Trace a mano un array pequeño para verificar su algoritmo de ordenación.

Ahora practique

• Ordene en sentido ascendente (menores primero), in situ, sin devolver ningún valor.
• El verificador prueba varios arrays, incluyendo negativos y uno ya ordenado.
• No escriba un main — el verificador proporciona uno.