Se aborda el estudio de los algoritmos de ordenación de arrays, categorizándolos en métodos básicos y avanzados. Entre los algoritmos fundamentales se encuentran la ordenación por selección, por inserción y por intercambio (burbuja). Los algoritmos más eficientes, como la ordenación rápida (quicksort), la ordenación por montículos (heapsort) y la ordenación por mezcla (mergesort), son considerados avanzados. Una distinción clave entre estas categorías radica en su complejidad temporal: los algoritmos básicos suelen tener una complejidad de O(n2), mientras que los algoritmos avanzados logran una complejidad de O(n log n). La complejidad O(n log n) a menudo se asocia con estrategias de "divide y vencerás", donde un conjunto de datos se subdivide repetidamente para su procesamiento.

Además de la complejidad temporal, la estabilidad es un criterio importante al evaluar algoritmos de ordenación. Un algoritmo se considera estable si mantiene el orden relativo de elementos con valores idénticos en la secuencia ordenada. Por ejemplo, en una lista como {5, 10, 100a, 90, 80, 100b}, si después de la ordenación, 100a precede a 100b, el algoritmo es estable. De lo contrario, es inestable.

A continuación, se presenta una tabla resumen de la complejidad y estabilidad de los algoritmos de ordenación mencionados:

1. Ordenación por Selección La ordenación por selección opera encontrando repetidamente el elemento mínimo (o máximo) del sub-array no ordenado y colocándolo al principio (o al final) del sub-array ordenado. Es un algoritmo con dos bucles anidados, resultando en una complejidad de O(n2).

#include <vector>
#include <algorithm> // Para std::swap

class Solucion {
public:
    std::vector<int> ordenarArray(std::vector<int>& arr) {
        int tamano = arr.size();
        for (int i = 0; i < tamano - 1; ++i) {
            int indiceMinimo = i;
            // Buscar el elemento mínimo en la parte no ordenada del array
            for (int j = i + 1; j < tamano; ++j) {
                if (arr[j] < arr[indiceMinimo]) {
                    indiceMinimo = j;
                }
            }
            // Intercambiar el elemento mínimo encontrado con el primer elemento de la parte no ordenada
            if (indiceMinimo != i) {
                std::swap(arr[i], arr[indiceMinimo]);
            }
        }
        return arr;
    }
};

La ordenación por selección es inestable. Considérese la secuencia {100a, 100b, 50, 20, 10}. En la primera iteración, el 10 es el mínimo y se intercambiará con 100a. Esto resultará en que 100b (originalmente en la segunda posición) ahora preceda a 100a (que se movió desde la primera posición), alterando su orden relativo original.

2. Ordenación por Intercambio (Burbuja) También conocida como "Bubble Sort", este algoritmo recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto. Las pasadas a través de la lista se repiten hasta que no se necesiten más intercambios, lo que indica que la lista está ordenada. Su complejidad es también O(n2).

#include <vector>
#include <algorithm> // Para std::swap

class Solucion {
public:
    std::vector<int> ordenarArray(std::vector<int>& dataVector) {
        int dataSize = dataVector.size();
        bool intercambioRealizado; // Bandera para optimización: si no hay intercambios, ya está ordenado

        for (int i = 0; i < dataSize - 1; ++i) {
            intercambioRealizado = false;
            // La parte final del array ya estará ordenada después de cada pasada
            for (int j = 0; j < dataSize - i - 1; ++j) {
                if (dataVector[j] > dataVector[j + 1]) {
                    std::swap(dataVector[j], dataVector[j + 1]);
                    intercambioRealizado = true;
                }
            }
            // Si no hubo intercambios en esta pasada, el array ya está ordenado
            if (!intercambioRealizado) {
                break;
            }
        }
        return dataVector;
    }
};

La ordenación por burbuja es un algoritmo estable. Esto se debe a que solo se realizan intercambios cuando un elemento es estrictamente mayor que el siguiente. Si dos elementos tienen el mismo valor, no se intercambian, preservando así su orden relativo original.

3. Ordenación por Inserción La ordenación por inserción construye la secuencia ordenada un elemento a la vez. En cada iteración, se toma un elemento de la parte no ordenada y se inserta en su posición correcta dentro de la parte ya ordenada. Es otro algoritmo con una complejidad de O(n2).

#include <vector>

class Solucion {
public:
    std::vector<int> ordenarArray(std::vector<int>& theArray) {
        int arraySize = theArray.size();
        for (int i = 1; i < arraySize; ++i) {
            int valorClave = theArray[i];
            int j = i - 1;

            // Mover los elementos de theArray[0...i-1], que son mayores que valorClave,
            // una posición adelante de su posición actual
            while (j >= 0 && theArray[j] > valorClave) {
                theArray[j + 1] = theArray[j];
                j = j - 1;
            }
            theArray[j + 1] = valorClave;
        }
        return theArray;
    }
};

La ordenación por inserción es un algoritmo estable. Cuando se inserta un elemento, se le coloca antes de todos los elementos mayores que él. Si encuentra un elemento igual, se detiene el desplazamiento y se inserta después de él (o en su posición actual si no hay elementos menores antes), manteniendo así el orden relativo de elementos duplicados.

4. Ordenación Rápida (Quicksort) Quicksort es un algoritmo de ordenación eficiente y recursivo que utiliza una estrategia de "divide y vencerás". Funciona seleccionando un 'pivote' de la array y particionando los otros elementos en dos sub-arrays, según sean menores o mayores que el pivote. Los sub-arrays se ordenan recursivamente.

#include <vector>
#include <algorithm> // Para std::swap

class Solucion {
public:
    std::vector<int> ordenarArray(std::vector<int>& elementos) {
        quicksort(elementos, 0, elementos.size() - 1);
        return elementos;
    }

private:
    // Función auxiliar para realizar la partición (esquema de Hoare)
    int particionar(std::vector<int>& elementos, int bajo, int alto) {
        int pivote = elementos[bajo]; // Elegimos el primer elemento como pivote
        int i = bajo - 1;
        int j = alto + 1;

        while (true) {
            do {
                i++;
            } while (elementos[i] < pivote);

            do {
                j--;
            } while (elementos[j] > pivote);

            if (i >= j) {
                return j;
            }
            std::swap(elementos[i], elementos[j]);
        }
    }

    // Función principal de QuickSort (recursiva)
    void quicksort(std::vector<int>& elementos, int bajo, int alto) {
        if (bajo < alto) {
            // idx_pivote es el índice de partición, elementos[idx_pivote] está ahora en su lugar
            int idx_pivote = particionar(elementos, bajo, alto);

            // Ordenar los elementos antes y después del pivote
            quicksort(elementos, bajo, idx_pivote); // El esquema de Hoare incluye el pivote en las particiones recursivas
            quicksort(elementos, idx_pivote + 1, alto);
        }
    }
};

Quicksort es generalmente inestable. La inestabilidad puede surgir durante el proceso de partición, especialmente cuando hay elementos duplicados. Por ejemplo, al elegir un pivote y mover elementos mayores o menores, el orden relativo de elementos iguales puede alterarse si uno de ellos se mueve a un lado del pivote y otro permanece en el otro lado, o si se intercambian con elementos no idénticos.

5. Ordenación por Montículos (Heapsort) Heapsort es un algoritmo de ordenación basado en árboles binarios, que utiliza la estructura de datos "montículo binario". Es un algoritmo eficiente con una complejidad de O(n log n). Funciona construyendo un montículo máximo (o mínimo) a partir de los datos de entrada, y luego extrayendo repetidamente el elemento raíz del montículo (que es el máximo o mínimo) y reconstruyendo el montículo, hasta que no queden elementos. La ordenación por montículos es inestable.
6. Ordenación por Mezcla (Mergesort) Mergesort es otro algoritmo de ordenación basado en el paradigma de "divide y vencerás". Divide la array en dos mitades, llama recursivamente a Mergesort para cada mitad y luego mezcla las dos mitades ordenadas. Su complejidad es O(n log n) en el peor, promedio y mejor caso, lo que lo hace muy fiable. Mergesort es un algoritmo estable, ya que la operación de mezcla se puede implementar de manera que preserve el orden relativo de elementos iguales.