La importancia de mejorar los algoritmos de ordenamiento

En el mundo de la informática, ordenar datos ha sido siempre una tarea fundamental. Aunque a primera vista parezca un problema resuelto, la investigación demuestra que siempre existe espacio para optimizar los algoritmos clásicos. El artículo de Alnihoud y Mansi lo evidencia al proponer dos mejoras concretas: el Selection Sort mejorado (ESS) y el Bubble Sort mejorado (EBS)

El ordenamiento por selección mejorado conserva la complejidad O(n²), pero introduce una diferencia sustancial: reduce drásticamente el número de intercambios, ajustándose a la naturaleza de los datos de entrada. Así, si una lista ya está ordenada, no realiza operaciones innecesarias. Este detalle, que podría parecer menor, resulta crucial en escenarios donde la escritura en memoria es costosa, como en sistemas embebidos o dispositivos de almacenamiento especializado

Más sorprendente aún es la propuesta de ordenamiento por burbuja mejorado, que logra reducir la complejidad a O(n log n), superando la ineficiencia histórica del Bubble Sort. Esta innovación demuestra que algoritmos aparentemente obsoletos pueden revitalizarse con ideas creativas y prácticas, convirtiéndose en alternativas viables en contextos reales

En conclusión: los problemas más estudiados pueden replantearse para ganar eficiencia. Estas mejoras no solo tienen valor académico, sino que refuerzan un principio clave de la ciencia de la computación: la búsqueda constante de soluciones más simples, rápidas y adaptadas a las necesidades del presente.

código 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <iostream> using namespace std; // Algoritmo de Ordenación por Selección Mejorada (versión recursiva) void seleccionMejorada(int A[], int n) { // Caso base: si el tamaño es menor o igual a 1, ya está ordenado if (n <= 1) return; int indice = n - 1; // Se asume que el último es el mayor int maximo = A[indice]; // Valor máximo inicial // Buscar el máximo en el rango [0, n-2] for (int i = 0; i < n - 1; i++) { if (A[i] >= maximo) { maximo = A[i]; indice = i; } } // Intercambiar si el máximo no está ya en la última posición if (indice != n - 1) { int temp = A[n - 1]; A[n - 1] = maximo; A[indice] = temp; } // Llamada recursiva para el subarreglo de tamaño n-1 seleccionMejorada(A, n - 1); } // Función para mostrar el arreglo void imprimir(int A[], int n) { for (int i = 0; i < n; i++) { cout << A[i] << " "; } cout << endl; } int main() { int A[] = {64, 25, 12, 22, 11}; int n = sizeof(A) / sizeof(A[0]); cout << "Arreglo original: "; imprimir(A, n); seleccionMejorada(A, n); cout << "Arreglo ordenado: "; imprimir(A, n); return 0; }

pseudo código 

Algoritmo SeleccionMejorada(A, n)

1. Si n > 1 entonces
2.     Definir variables: indice, temp, maximo
3.     indice := n - 1
4.     maximo := A[indice]

5.     Para i desde 0 hasta n - 2 hacer
6.         Si A[i] ≥ maximo entonces
7.             maximo := A[i]
8.             indice := i
9.         FinSi
10.    FinPara

11.    Si indice ≠ n - 1 entonces
12.        temp := A[n - 1]
13.        A[n - 1] := maximo
14.        A[indice] := temp
15.    FinSi

16.    // Llamada recursiva con tamaño reducido
17.    SeleccionMejorada(A, n - 1)

18. Si no
19.     retornar A
20. FinSi

Código:

#include <iostream>

using namespace std;

// Algoritmo de Ordenación por Burbuja Mejorada (EBS)
void enhancedBubbleSort(int arr[], int firstIndex, int lastIndex) {
    if (firstIndex >= lastIndex) return; // Caso base: ya está ordenado

    int minIndex = firstIndex;
    int maxIndex = lastIndex;
    int minVal = arr[firstIndex];
    int maxVal = arr[lastIndex];

    // Encontrar el mínimo y el máximo en el rango actual
    for (int i = firstIndex; i <= lastIndex; i++) {
        if (arr[i] < minVal) {
            minVal = arr[i];
            minIndex = i;
        }
        if (arr[i] > maxVal) {
            maxVal = arr[i];
            maxIndex = i;
        }
    }

    // Colocar el mínimo en la primera posición
    if (minIndex != firstIndex) {
        swap(arr[firstIndex], arr[minIndex]);
        // Ajustar el índice del máximo si fue movido
        if (maxIndex == firstIndex) maxIndex = minIndex;
    }

    // Colocar el máximo en la última posición
    if (maxIndex != lastIndex) {
        swap(arr[lastIndex], arr[maxIndex]);
    }

    // Llamada recursiva con el rango reducido
    enhancedBubbleSort(arr, firstIndex + 1, lastIndex - 1);
}

// Función para imprimir el arreglo
void imprimir(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Arreglo original: ";
    imprimir(arr, n);

    enhancedBubbleSort(arr, 0, n - 1);

    cout << "Arreglo ordenado: ";
    imprimir(arr, n);

    return 0;
}

pseudocodigo

función EnhancedBubbleSort (matriz, tamaño, primerIndice, ultimoIndice)
1. si tamaño > 1 entonces
2.     var temp, maxCounter := ultimoIndice
3.     var minCounter := primerIndice
4.     var max := array[ultimoIndice], min := array[primerIndice]
5.     para a desde primerIndice hasta ultimoIndice hacer
6.         si array[a] ≥ max entonces
7.             max := array[a]
8.             maxCounter := a
9.         fin si
10.        si array[a] < min entonces
11.            min := array[a]
12.            minCounter := a
13.        fin si
14.    fin para
15.    // Colocar mínimo y máximo en sus posiciones correctas
16.    intercambiar(array[primerIndice], array[minCounter])
17.    intercambiar(array[ultimoIndice], array[maxCounter])
18.    primerIndice := primerIndice + 1
19.    ultimoIndice := ultimoIndice - 1
20.    tamaño := tamaño - 2
21.    return EnhancedBubbleSort(array, tamaño, primerIndice, ultimoIndice)
22. sino
23.    return array
24. fin si