Implementación y Comparativa de Algoritmos de Ordenamiento: Bubble, Shell y Quick Sort en C#

Introducción a los Algoritmos de Ordenamiento

Este documento presenta la implementación de tres algoritmos de ordenamiento fundamentales: Bubble Sort, Shell Sort y Quick Sort. Cada sección incluye el código fuente en C# y la instrumentación para medir métricas de rendimiento como el número de pasadas, comparaciones e intercambios, lo que permite una comprensión práctica de su funcionamiento.

1. Algoritmo de Ordenamiento Burbuja (Bubble Sort)

El Bubble Sort es uno de los algoritmos de ordenamiento más sencillos. Funciona revisando repetidamente la lista a ordenar, intercambiando elementos adyacentes 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. Aunque es fácil de entender, su eficiencia es baja para grandes conjuntos de datos.

Implementación en C#

int N = numerosControl.Length;
int temp;
for (int K = 1; K <= N - 1; K++)
{
    pasadas++;
    for (int L = 0; L <= N - 1 - K; L++)
    {
        comparaciones++;
        if (numerosControl[L] > numerosControl[L + 1])
        {
            temp = numerosControl[L];
            numerosControl[L] = numerosControl[L + 1];
            numerosControl[L + 1] = temp;
            intercambios++;
        }
    }
}

2. Algoritmo de Ordenamiento Shell (Shell Sort)

El Shell Sort, también conocido como ordenamiento por inserción con saltos, es una mejora del algoritmo de ordenamiento por inserción. En lugar de comparar y mover elementos adyacentes, compara elementos separados por un "salto" o "incremento" determinado. Este salto se reduce progresivamente hasta que el último paso es un ordenamiento por inserción estándar. Esto permite que los elementos se muevan a sus posiciones correctas más rápidamente que en el ordenamiento por inserción simple.

Implementación en C#

int[] incrementos = new int[] { 1, 2, 3, 5, 7, 11, 13, 17, 19, 23 };
int m, h, j, n, i, k;
n = numerosControl.Length;
for (m = incrementos.Length - 1; m >= 0; m--)
{
    h = incrementos[m];
    pasadas++;
    for (j = h; j < numerosControl.Length; j++)
    {
        comparaciones++;
        i = j - h;
        k = numerosControl[j];
        while (i >= 0 && k < numerosControl[i])
        {
            numerosControl[i + h] = numerosControl[i];
            intercambios++;
            i = i - h;
        }
        numerosControl[i + h] = k;
        i = i + h;
    }
}

3. Algoritmo de Ordenamiento Rápido (Quick Sort)

El Quick Sort es un algoritmo de ordenamiento eficiente basado en la estrategia de "divide y vencerás". Selecciona un elemento de la lista, llamado "pivote", y particiona los demás elementos en dos sublistas: aquellos menores que el pivote y aquellos mayores. Luego, ordena recursivamente las sublistas. Es uno de los algoritmos de ordenamiento más rápidos en la práctica para grandes conjuntos de datos.

Implementación en C#

La función principal para iniciar el ordenamiento rápido se invoca de la siguiente manera:

Ordenar(0, numerosControl.Length - 1); // Se llama a este método para iniciar el proceso.

Y la implementación del método recursivo Ordenar es la siguiente:

public void Ordenar(int l, int r)
{
    int i = l;
    int j = r;
    int w;
    int x = numerosControl[(l + r) / 2]; // Pivote
    do
    {
        while (numerosControl[i] < x)
        {
            comparaciones++;
            i++;
        }
        while (numerosControl[j] > x)
        {
            j--;
            comparaciones++;
        }
        if (i <= j)
        {
            w = numerosControl[i];
            numerosControl[i] = numerosControl[j];
            numerosControl[j] = w;
            i++;
            j--;
            intercambios++;
        }
    } while (i <= j);
    if (l < j) { pasadas++; Ordenar(l, j); }
    if (i < r) { pasadas++; Ordenar(i, r); }
}

Consideraciones sobre el Rendimiento

Las variables pasadas, comparaciones e intercambios han sido incluidas en cada implementación para permitir un seguimiento detallado del comportamiento de los algoritmos. Estas métricas son cruciales para comprender la eficiencia y la complejidad de cada método de ordenamiento en diferentes escenarios de datos.