Estructuras de Datos

0x0042 INICIALIZANDO...
0x7ffe-stack
*p = malloc(sizeof(Node))
0x3b2a - heap
ptr -> next = NULL
Unidad 04

Ordenamiento Básico

Bubble Sort (ordenamiento en burbuja) recibe su nombre de la idea de que los elementos más grandes "burbujean" hacia el final de la lista en cada pasada. La lógica consiste en recorrer el arreglo comparando pares adyacentes e intercambiarlos si están en el orden incorrecto.

4.1 Bubble Sort: La Burbuja
Mirar en YouTube
Imagen 15. Bubble Sort Pasada 1 y 2

Imagen 15. Bubble Sort Pasada 1 y 2

Ejemplo gráfico: En la primera pasada, el valor 6 se compara e intercambia sucesivamente hasta llegar a su posición final.

main.cpp
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Bubble Sort tiene una complejidad de O(n²) tanto en el peor caso como en el promedio. Es un algoritmo "en sitio" (espacio O(1)) y estable, pero su baja eficiencia lo limita a fines principalmente educativos.

Selection Sort mejora al Bubble Sort reduciendo el número de intercambios. En cada pasada, busca el elemento mínimo de la sección no ordenada y lo coloca directamente en su posición final.

Imagen 17. Selection Sort

Imagen 17. Selection Sort

Ejemplo paso a paso: Se identifica el valor mínimo (1) y se intercambia con la primera posición.

main.cpp
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
4.2 Selection Sort: Selección Directa
Mirar en YouTube

Este algoritmo construye la lista ordenada de manera incremental, similar a como ordenamos cartas en la mano. Toma cada nuevo elemento e "inserta" en la posición correcta dentro de la sublista ordenada.

4.3 Insertion Sort: Método de la Baraja
Mirar en YouTube
main.cpp
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int clave = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > clave) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = clave;
    }
}
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int clave = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > clave) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = clave;
    }
}
Imagen 18. Insertion Sort

Imagen 18. Insertion Sort

Visualización de cómo se desplazan los elementos mayores para hacer espacio al valor clave.

Aunque los tres algoritmos tienen complejidad cuadrática O(n²), difieren en la práctica: 1. Bubble Sort: Mayormente didáctico. 2. Selection Sort: Realiza el menor número de intercambios. 3. Insertion Sort: El más eficiente para listas pequeñas o casi ordenadas.

4.4 Comparativa de Algoritmos O(n²)
Mirar en YouTube
Volver al nivel