Comparación de Métodos de Ordenación

Ordenación Rápida (Quicksort)

La ordenación rápida es un algoritmo eficiente y ampliamente utilizado en la práctica.

1. Uso en C

Se encuentra en la biblioteca stdlib.h. La función tiene el siguiente prototipo:

void qsort(void *base, size_t num, size_t width, int (*compare)(const void *, const void *));

Parámetros:

• base: Dirección inicial del arreglo a ordenar.
• num: Cantidad de elementos en el arreglo.
• width: Tamaño en bytes de cada elemento.
• compare: Puntero a una función de comparación.

Ejemplo de función de comparación para orden ascenednte:

int comparar_ascendente(const void *a, const void *b) {
    return (*(int *)a) - (*(int *)b);
}

Para orden descendente:

int comparar_descendente(const void *a, const void *b) {
    return (*(int *)b) - (*(int *)a);
}

2. Implementación Detallada

El algoritmo se basa en la técnica de división y conquista. Se elige un pivote, se particiona el arreglo de modo que los elementos menores queden a la izquierda y los mayores a la derecha, y luego se aplica recursión a las sublistas.

Proceso de partición: Se toma el primer elemento como pivote. Dos índices se mueven hacia el centro desde los extremos. El índice derecho se desplaza a la izquierda hasta encontrar un elemento menor o igual al pivote, y el índice izquierdo se desplaza a la derecha hasta encontrar uno mayor. Luego se intercambian los elementos. Esto continúa hasta que los índices se encuentran, momento en que el pivote se coloca en su posición final.

void ordenar_rapido(int *arreglo, int inicio, int fin) {
    if (inicio >= fin) return;
    int izquierda = inicio;
    int derecha = fin;
    int pivote = arreglo[inicio];
    
    while (izquierda < derecha) {
        while (izquierda < derecha && arreglo[derecha] >= pivote) derecha--;
        while (izquierda < derecha && arreglo[izquierda] <= pivote) izquierda++;
        if (izquierda < derecha) {
            int temp = arreglo[izquierda];
            arreglo[izquierda] = arreglo[derecha];
            arreglo[derecha] = temp;
        }
    }
    arreglo[inicio] = arreglo[izquierda];
    arreglo[izquierda] = pivote;
    ordenar_rapido(arreglo, inicio, izquierda - 1);
    ordenar_rapido(arreglo, izquierda + 1, fin);
}

La eficiencia de quicksort radica en sus intercambios a saltos, a diferencia de la ordenación burbuja. Su complejidad promedio es O(nlogn), aunque en el peor caso puede degenerar a O(n2).

Ordenación Burbuja (Bubble Sort)

Este método funciona comparando pares adyacentes e intercambiándolos si están en orden incorrecto. En cada pasada, el elemento más grande se desplaza al final del arreglo.

Implementación:

void ordenar_burbuja(int vector[], int longitud) {
    for (int i = 0; i < longitud - 1; i++) {
        for (int j = 0; j < longitud - 1 - i; j++) {
            if (vector[j] > vector[j + 1]) {
                int aux = vector[j];
                vector[j] = vector[j + 1];
                vector[j + 1] = aux;
            }
        }
    }
}

Ordenación por Selección (Selection Sort)

En cada iteración, se busca el mínimo del subarreglo no ordenado y se intercambia con el primer elemento de ese subarreglo, expandiendo gradualmente la porción ordenada.

Código de ejemplo:

void ordenar_seleccion(int datos[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int indice_min = i;
        for (int j = i + 1; j < n; j++) {
            if (datos[j] < datos[indice_min]) {
                indice_min = j;
            }
        }
        if (indice_min != i) {
            int temp = datos[i];
            datos[i] = datos[indice_min];
            datos[indice_min] = temp;
        }
    }
}

Ordenación por Inserción (Insertion Sort)

Este algoritmo construye la solución elemento a elemento, insertando cada nuevo elemento en su posición corecta dentro de la sublista ya ordenada.

Proceso: Se toma el segundo elemento y se compara con los anteriores, moviendo los mayores hacia la derecha hasta encontrar su lugar. Se repite para todos los elementos restantes.

void ordenar_insercion(int arr[], int tam) {
    for (int i = 1; i < tam; i++) {
        int clave = arr[i];
        int pos = i;
        while (pos > 0 && arr[pos - 1] > clave) {
            arr[pos] = arr[pos - 1];
            pos--;
        }
        arr[pos] = clave;
    }
}