Para resolver problemas comunes de ordenamiento de datos, existen varias familias de algoritmos ampliamente utilizados. Estos se pueden clasificar en cuatro categorías principales: por intercambio (Bubble Sort, Quick Sort), por selección (Selection Sort, Heap Sort), por inserción (Insertion Sort, Shell Sort) y por mezcla (Merge Sort). El presente artículo explora la implementación y rendimiento de varios de estos métodos en C#.

Ordenamiento por intercambio

Esta categoría incluye algoritmos que ordenan reiterativamente intercambiando elementos adyacentes o seleccionendo un pivote para particionar el conjunto.

1. Ordenamiento Burbuja (Bubble Sort)

Este algoritmo recorre repetidamente la lista, comparando elementos adyacentes y intercambiándolos si están en el orden incorrecto. Su eficiencia es O(n²) en el peor y caso promedio.

static void OrdenamientoBurbuja(int[] arreglo)
{
    int longitud = arreglo.Length;
    bool intercambio;
    for (int i = 0; i < longitud - 1; i++)
    {
        intercambio = false;
        for (int j = 0; j < longitud - i - 1; j++)
        {
            if (arreglo[j] > arreglo[j + 1])
            {
                int temporal = arreglo[j];
                arreglo[j] = arreglo[j + 1];
                arreglo[j + 1] = temporal;
                intercambio = true;
            }
        }
        if (!intercambio) break;
    }
}

2. Ordenamiento Rápido (Quick Sort)

Utiliza la estrategia de divide y vencerás. Selecciona un elemento pivote y particiona el arreglo en dos sub-arreglos: elementos menores al pivote y elementos mayores. Su complejidad promedio es O(n log n).

static void Particion(int[] arreglo, int izquierda, int derecha, out int indicePivote)
{
    int pivote = arreglo[izquierda];
    int i = izquierda;
    int j = derecha;

    while (i < j)
    {
        while (i < j && arreglo[j] >= pivote) j--;
        while (i < j && arreglo[i] <= pivote) i++;
        if (i < j)
        {
            int temp = arreglo[i];
            arreglo[i] = arreglo[j];
            arreglo[j] = temp;
        }
    }
    arreglo[izquierda] = arreglo[i];
    arreglo[i] = pivote;
    indicePivote = i;
}

static void OrdenamientoRapido(int[] arreglo, int izquierda, int derecha)
{
    if (izquierda < derecha)
    {
        Particion(arreglo, izquierda, derecha, out int pivoteIndice);
        OrdenamientoRapido(arreglo, izquierda, pivoteIndice - 1);
        OrdenamientoRapido(arreglo, pivoteIndice + 1, derecha);
    }
}

Ordenamiento por selección

Estos algoritmos funcionan seleccionando repetidamente el elemento más pequeño (o más grande) del sub-arreglo no ordenado.

3. Ordenamiento por Selección Directa (Selection Sort)

En cada pasada, encuentra el elemento mínimo del sub-arreglo no ordenado y lo coloca en su posición correcta. Teine una complejidad O(n²).

static void OrdenamientoPorSeleccion(int[] arreglo)
{
    int n = arreglo.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int indiceMinimo = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arreglo[j] < arreglo[indiceMinimo])
                indiceMinimo = j;
        }
        int temp = arreglo[indiceMinimo];
        arreglo[indiceMinimo] = arreglo[i];
        arreglo[i] = temp;
    }
}

4. Ordenamiento por Montículos (Heap Sort)

Construye un montículo máximo a partir de los datos y luego extrae repetidamente el elemento raíz (el más grande) para obtener la secuencia ordenada. Su complejidad es O(n log n).

static void AjustarMonticulo(int[] arreglo, int tamano, int raiz)
{
    int mayor = raiz;
    int izquierdo = 2 * raiz + 1;
    int derecho = 2 * raiz + 2;

    if (izquierdo < tamano && arreglo[izquierdo] > arreglo[mayor])
        mayor = izquierdo;

    if (derecho < tamano && arreglo[derecho] > arreglo[mayor])
        mayor = derecho;

    if (mayor != raiz)
    {
        int intercambio = arreglo[raiz];
        arreglo[raiz] = arreglo[mayor];
        arreglo[mayor] = intercambio;
        AjustarMonticulo(arreglo, tamano, mayor);
    }
}

static void OrdenamientoPorMonticulos(int[] arreglo)
{
    int n = arreglo.Length;
    for (int i = n / 2 - 1; i >= 0; i--)
        AjustarMonticulo(arreglo, n, i);

    for (int i = n - 1; i > 0; i--)
    {
        int temporal = arreglo[0];
        arreglo[0] = arreglo[i];
        arreglo[i] = temporal;
        AjustarMonticulo(arreglo, i, 0);
    }
}

Ordenamiento por inserción

Estos algoritmos construyen la lista ordenada final un elemento a la vez, insertando cada nuevo elemento en su posición correcta dentro de la porción ya ordenada.

5. Ordenamiento por Inserción Directa (Insertion Sort)

Similar a ordenar cartas en la mano. Es eficiente para conjuntos pequeños o casi ordenados, con complejidad O(n²).

static void OrdenamientoPorInsercion(int[] arreglo)
{
    for (int i = 1; i < arreglo.Length; i++)
    {
        int clave = arreglo[i];
        int j = i - 1;
        while (j >= 0 && arreglo[j] > clave)
        {
            arreglo[j + 1] = arreglo[j];
            j--;
        }
        arreglo[j + 1] = clave;
    }
}

6. Ordenamiento de Shell (Shell Sort)

Es una optimización del ordenamiento por inserción. Permite intercambios de elementos que están lejos entre sí, usando un intervalo decreciente. Su complejidad depende de la secuencia de intervalos usada.

static void OrdenamientoShell(int[] arreglo)
{
    int n = arreglo.Length;
    for (int intervalo = n / 2; intervalo > 0; intervalo /= 2)
    {
        for (int i = intervalo; i < n; i++)
        {
            int temporal = arreglo[i];
            int j;
            for (j = i; j >= intervalo && arreglo[j - intervalo] > temporal; j -= intervalo)
            {
                arreglo[j] = arreglo[j - intervalo];
            }
            arreglo[j] = temporal;
        }
    }
}

Ordenamiento por mezcla

7. Ordenamiento por Mezcla (Merge Sort)

Divide el arreglo en mitades, las ordena recursivamente y luego las fusiona. Es un algoritmo estable con complejidad O(n log n), pero requiere espacio adicional O(n).

static void Mezclar(int[] arreglo, int izquierda, int medio, int derecha)
{
    int[] temporal = new int[derecha - izquierda + 1];
    int i = izquierda, j = medio + 1, k = 0;
    while (i <= medio && j <= derecha)
    {
        if (arreglo[i] <= arreglo[j])
            temporal[k++] = arreglo[i++];
        else
            temporal[k++] = arreglo[j++];
    }
    while (i <= medio) temporal[k++] = arreglo[i++];
    while (j <= derecha) temporal[k++] = arreglo[j++];
    Array.Copy(temporal, 0, arreglo, izquierda, temporal.Length);
}

static void OrdenamientoPorMezcla(int[] arreglo, int izquierda, int derecha)
{
    if (izquierda < derecha)
    {
        int medio = (izquierda + derecha) / 2;
        OrdenamientoPorMezcla(arreglo, izquierda, medio);
        OrdenamientoPorMezcla(arreglo, medio + 1, derecha);
        Mezclar(arreglo, izquierda, medio, derecha);
    }
}

Consideraciones de complejidad

• Bubble Sort, Selection Sort, Insertion Sort: O(n²) en el peor caso.
• Shell Sort: Depende de la secuencia de intervalos, generalmente entre O(n log n) y O(n²).
• Quick Sort, Heap Sort, Merge Sort: O(n log n) en el promedio/peor caso.

La elección del algorimto apropiado depende de factores como el tamaño del conjunto de datos, si los datos ya están parcialmente ordenados, los requisitos de estabilidad y las restricciones de memoria.