Bubble Sort

Bubble Sort o Ordenamiento Burbuja es uno de los algoritmos más simples que existen. Su complejidad es cuadrática, es decir $O(n^2)$.

La idea básica consiste en encontrar el elemento más pequeño o grande (según sea el ordenamiento) y hacer que pase al final del array (burbujearlo). Una vez pasado este elemento, debemos encontrar el siguiente más grande o más pequeño de los elementos restantes y pasarlo al penúltimo lugar, y asi sucesivamente hasta a acabar con todos los elementos.

La acción de mover un elemento al final se realiza con comparaciones de dos elementos adyacentes consecutivos de izquierda a derecha.

Ejemplo:

Supongamos que ordenamos de mayor a menor y la lista a ordenar es la siguiente:

7 6 5 4 3

Primera iteración

Comparamos los dos primeros elementos (7 y 6), y si estan en desorden los intercambiamos.

7 6 5 4 3 -> 6 7 5 4 3

Comparamos el siguiente par de elementos (7 y 5), y si están en desorden los intercambiamos.

6 7 5 4 3 -> 6 5 7 4 3

Comparamos el siguiente par de elementos (7 y 4), y si están en desorden los intercambiamos.

6 5 7 4 3 -> 6 5 4 7 3

Comparamos el siguiente par de elementos (7 y 3), y si están en desorden los intercambiamos.

6 5 4 7 3 -> 6 5 4 3 7

Como pudiste observar el elemento que quedó al final fue el mayor de todos (el 7). Repetimos el proceso puesto que la lista aún no está ordenada.

Segunda Iteración

Comparamos los dos primeros elementos (6 y 5), y si estan en desorden los intercambiamos

6 5 4 3 7 -> 5 6 4 3 7

Comparamos el siguiente par de elementos (6 y 4), y si están en desorden los intercambiamos.

5 6 4 3 7 -> 5 4 6 3 7

Comparamos el siguiente par de elementos (6 y 3), y si están en desorden los intercambiamos.

5 4 6 3 7 -> 5 4 3 6 7

El siguiente par de elementos es (5 y 7), pero por la iteración anterior podemos asegurar que la comparación es innecesaria puesto que el 7 ya está ordenado, es decir, el 7 fue burbujeado hasta al final por la primer iteración por ser el mayor de todos y por tanto cualquier otro elemento anterior no puede ser mayor a este.

Tercera iteración

Comparamos los dos primeros elementos (5 y 4), y si estan en desorden los intercambiamos

5 4 3 6 7 -> 4 5 3 6 7

Comparamos el siguiente par de elementos (5 y 3), y si están en desorden los intercambiamos.

4 5 3 6 7 -> 4 3 5 6 7

El siguiente par de elementos es (5 y 6), pero por la iteración anterior podemos asegurar que la comparación es innecesaria puesto que el 6 ya está ordenado, es decir, el 6 fue burbujeado hasta el penúltimo lugar por la segunda iteración por ser el mayor de todos los elementos anteriores.

Cuarta Iteración

Comparamos los dos primeros elementos (5 y 4), y si estan en desorden los intercambiamos

4 3 5 6 7 -> 3 4 5 6 7

El siguiente par de elementos es (4 y 5), pero por la iteración anterior podemos asegurar que la comparación es innecesaria puesto que el 5 ya está ordenado, es decir, el 5 fue burbujeado hasta el antepenúltimo lugar por la segunda iteración por ser el mayor de todos los elementos anteriores.

Además notemos que una cuarta iteración es innecesaria puesto que al acomodar el los n-1 elementos del array automaticamente el n-ésimo elemento es acomodado. Así podemos deducir que el máximo de iteraciones necesarias para ordenar un arreglo de tamaño N es N-1 iteraciones.

Código

bubble_sort.cpp

#include<iostream>
using namespace std;

#define MAX_SIZE 10

int array[MAX_SIZE] = {3, 5, 6, 1, 7, 12, 45, 4, 15, 9};

// Imprime el array
void print_array(int array[MAX_SIZE], int size) {
    for (int i = 0; i < size; i++) {
        cout << array[i] << ' ';
    }
    cout << endl;
}

void bubble_sort(int array[MAX_SIZE], int size) {
    // Necesitamos a lo más size - 1 iteraciones para 
    // asegurarnos que el array está ordenado
    for (int i = 0; i < size - 1; i++) {
        // Comparamos cada par de elementos ignorando el 
        // (n-i)ésimo elemento en cada iteración de i
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j+1]){
                // Intercambiamos los dos elementos desordenados
                int tmp = array[j+1];
                array[j+1] = array[j];
                array[j] = tmp;
            }
        }
    }
}

int main() {

    print_array(array, MAX_SIZE);
    bubble_sort(array, MAX_SIZE);
    print_array(array, MAX_SIZE);

    return 0;
}