Conceptos Fundamentales

El ordenamiento organiza elementos según criterios específicos para facilitar su búsqueda y comparación. La estabilidad de un algoritmo garantiza que elementos iguales mantengan su orden relativo original. Los algoritmos estables incluyen enserción directa y ordenamiento por fusión, mientras que rápido y por montón son inestables. El ordenamiento se clasifica en interno (datos en memoria) y externo (datos en disco).

Inserción Directa

Este algoritmo construye una secuencia ordenada incrementando elementos uno a uno. Para cada posición, se compara el elemento actual con los anteriores y se desplazan los mayores para insertarlo en su lugar correcto.

void ordenarPorInsercion(int* vector, int longitud) {
    for (int i = 1; i < longitud; ++i) {
        int valorActual = vector[i];
        int j = i - 1;
        
        while (j >= 0 && vector[j] > valorActual) {
            vector[j + 1] = vector[j];
            j--;
        }
        vector[j + 1] = valorActual;
    }
}

Su complejidad temporal es O(n²) en el peor caso (arreglo inversamente ordenado) y O(n) en el mejor caso (arreglo casi ordenado). Es estable y usa O(1) de espacio adicional.

Ordenamiento de Shell

Mejora la inserción directa mediante comparaciones entre elementos distantes, reduciendo progresivamente la brecha. Esto acerca los elementos a su posición final antes del refinamiento final.

void ordenamientoShell(int* vector, int tam) {
    for (int brecha = tam/2; brecha > 0; brecha /= 2) {
        for (int i = brecha; i < tam; i += 1) {
            int temp = vector[i];
            int j;
            
            for (j = i; j >= brecha && vector[j - brecha] > temp; j -= brecha) {
                vector[j] = vector[j - brecha];
            }
            vector[j] = temp;
        }
    }
}

Su complejidad es O(n^(1.3-2)) en promedio, inestable y usa O(1) de espacio adicional.

Selección Directa

Busca iterativamente el elemento mínimo/máximo y lo intercambia con la posición actual. Una versión optimizada busca ambos extremos en cada pasada.

void ordenarPorSeleccion(int* datos, int n) {
    int izquierda = 0, derecha = n - 1;
    
    while (izquierda < derecha) {
        int minIdx = izquierda, maxIdx = derecha;
        
        for (int k = izquierda; k <= derecha; ++k) {
            if (datos[k] < datos[minIdx]) minIdx = k;
            if (datos[k] > datos[maxIdx]) maxIdx = k;
        }
        
        intercambiar(&datos[izquierda], &datos[minIdx]);
        if (izquierda == maxIdx) maxIdx = minIdx;
        intercambiar(&datos[derecha], &datos[maxIdx]);
        
        izquierda++;
        derecha--;
    }
}

Su complejidad es O(n²) en todos los casos, inestable y usa O(1) de espacio adicional.

Ordenamiento por Burbuja

Compara elemetnos adyacentes y los intercambia si están en orden incorrecto, propagando los elementos más grandes al final.

void ordenamientoBurbuja(int* arreglo, int tam) {
    bool intercambio;
    
    for (int i = 0; i < tam - 1; ++i) {
        intercambio = false;
        
        for (int j = 0; j < tam - 1 - i; ++j) {
            if (arreglo[j] > arreglo[j + 1]) {
                intercambiar(&arreglo[j], &arreglo[j + 1]);
                intercambio = true;
            }
        }
        
        if (!intercambio) break;
    }
}

Su complejidad es O(n²) en el peor caso, O(n) en el mejor caso. Es estable y usa O(1) de espacio adicional.

Ordenamiento Rápido (Quicksort)

Selecciona un pivote y particiona el arreglo en elementos menores y mayores, aplicando recursión a cada subarreglo.

Implementación con método de los punteros

int particionar(int* datos, int inicio, int fin) {
    int pivote = datos[inicio];
    int i = inicio + 1;
    
    for (int j = inicio + 1; j <= fin; ++j) {
        if (datos[j] < pivote) {
            intercambiar(&datos[i], &datos[j]);
            i++;
        }
    }
    intercambiar(&datos[inicio], &datos[i - 1]);
    return i - 1;
}

void quicksort(int* arr, int ini, int fin) {
    if (ini < fin) {
        int pivoteIdx = particionar(arr, ini, fin);
        quicksort(arr, ini, pivoteIdx - 1);
        quicksort(arr, pivoteIdx + 1, fin);
    }
}

Optimizaciones

Selección de pivote con mediana de tres: evita el peor caso en datos ordenados.

int obtenerMediana(int* arr, int a, int b, int c) {
    if ((arr[a] <= arr[b] && arr[b] <= arr[c]) || (arr[c] <= arr[b] && arr[b] <= arr[a]))
        return b;
    else if ((arr[b] <= arr[a] && arr[a] <= arr[c]) || (arr[c] <= arr[a] && arr[a] <= arr[b]))
        return a;
    else
        return c;
}

Optimización para subarreglos pequeños: usa inserción directa para menos de 10 elementos.

Complejidad promedio: O(n log n). Espacio: O(log n) a O(n). Inestable.

Ordenamiento por Fusión (Merge Sort)

Divide recursivamente el arreglo y fusiona subarreglos ordenados.

void fusionar(int* arr, int izq, int med, int der) {
    int n1 = med - izq + 1;
    int n2 = der - med;
    
    int L[n1], R[n2];
    for (int i = 0; i < n1; ++i) L[i] = arr[izq + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[med + 1 + j];
    
    int i = 0, j = 0, k = izq;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int* arr, int ini, int fin) {
    if (ini < fin) {
        int med = ini + (fin - ini) / 2;
        mergeSort(arr, ini, med);
        mergeSort(arr, med + 1, fin);
        fusionar(arr, ini, med, fin);
    }
}

Complejidad: O(n log n). Espacio: O(n). Estable.

Ordenamiento por Conteo

Algoritmo no comparativo que cuenta ocurrencias de cada valor, adecuado para anteros no negativos en rango acotado.

void ordenamientoConteo(int* arr, int tam) {
    int max = *max_element(arr, arr + tam);
    int min = *min_element(arr, arr + tam);
    int rango = max - min + 1;
    
    int* conteo = new int[rango]();
    int* salida = new int[tam];
    
    for (int i = 0; i < tam; ++i) conteo[arr[i] - min]++;
    for (int i = 1; i < rango; ++i) conteo[i] += conteo[i - 1];
    
    for (int i = tam - 1; i >= 0; --i) {
        salida[conteo[arr[i] - min] - 1] = arr[i];
        conteo[arr[i] - min]--;
    }
    
    for (int i = 0; i < tam; ++i) arr[i] = salida[i];
    
    delete[] conteo;
    delete[] salida;
}

Complejidad: O(n + k) donde k es el rango. Espacio: O(n + k). Estable.

Análisis Comparativo