Conceptos Fundamentales

Definición de Ordenamiento

Organizar una secuencia de elementos según un criterio específico.

Terminología Clave

• Estable: Elementos equivalentes mantienen su orden relativo
• Inestable: Elementos equivalentes pueden cambiar su posición
• Ordenamiento Interno: Todos los datos caben en memoria
• Ordenamiento Externo: Datos almacenados en dispositivos secundarios
• Complejidad Temporal: Tiempo de ejecución en función del tamaño de entrada
• Complejidad Espacial: Memoria adicional requerida

Clasificación de Algoritmos

Comparativos: Basados en comparaciones entre elementos (QuickSort, MergeSort, HeapSort, BubbleSort). Complejidad típica O(n log n).

No Comparativos: Utilizan propiedades de los datos (CountingSort, RadixSort, BucketSort). Complejidad potencial O(n) pero con restricciones de distribución.

Algoritmos de Ordenamiento

Ordenamiento de Burbuja

Intercambia repetidamante elementos adyacentes en orden incorrecto.

public static int[] ordenarBurbuja(int[] datos) {
    for (int i = 0; i < datos.length - 1; i++) {
        for (int j = 0; j < datos.length - i - 1; j++) {
            if (datos[j] > datos[j + 1]) {
                int aux = datos[j];
                datos[j] = datos[j + 1];
                datos[j + 1] = aux;
            }
        }
    }
    return datos;
}

Complejidad: Mejor O(n) - Peor O(n²)

Ordenamiento por Selección

Selecciona repetidamente el elemento mínimo del segmento no ordenado.

public static int[] ordenarSeleccion(int[] datos) {
    for (int i = 0; i < datos.length; i++) {
        int idxMinimo = i;
        for (int j = i + 1; j < datos.length; j++) {
            if (datos[j] < datos[idxMinimo]) 
                idxMinimo = j;
        }
        int aux = datos[i];
        datos[i] = datos[idxMinimo];
        datos[idxMinimo] = aux;
    }
    return datos;
}

Complejidad: O(n²) en todos los casos

Ordenamiento por Inserción

Construye una secuencia ordenada insertando elementos uno por uno.

public static int[] ordenarInsercion(int[] datos) {
    for (int i = 1; i < datos.length; i++) {
        int actual = datos[i];
        int j = i - 1;
        while (j >= 0 && actual < datos[j]) {
            datos[j + 1] = datos[j];
            j--;
        }
        datos[j + 1] = actual;
    }
    return datos;
}

Complejidad: Mejor O(n) - Peor O(n²)

Ordenamiento Shell

Optimización de inserción que compara elementos distantes.

public static int[] ordenarShell(int[] datos) {
    int intervalo = datos.length / 2;
    while (intervalo > 0) {
        for (int i = intervalo; i < datos.length; i++) {
            int temp = datos[i];
            int j = i;
            while (j >= intervalo && datos[j - intervalo] > temp) {
                datos[j] = datos[j - intervalo];
                j -= intervalo;
            }
            datos[j] = temp;
        }
        intervalo /= 2;
    }
    return datos;
}

Complejidad: O(n log² n)

Ordenamiento por Mezcla

Divide recursivamente y combina subarreglos ordenados.

public static int[] ordenarMezcla(int[] datos) {
    if (datos.length <= 1) return datos;
    
    int medio = datos.length / 2;
    int[] izquierda = Arrays.copyOfRange(datos, 0, medio);
    int[] derecha = Arrays.copyOfRange(datos, medio, datos.length);
    
    return combinar(ordenarMezcla(izquierda), ordenarMezcla(derecha));
}

private static int[] combinar(int[] izq, int[] der) {
    int[] resultado = new int[izq.length + der.length];
    int i = 0, j = 0, k = 0;
    
    while (i < izq.length && j < der.length) {
        resultado[k++] = (izq[i] <= der[j]) ? izq[i++] : der[j++];
    }
    System.arraycopy(izq, i, resultado, k, izq.length - i);
    System.arraycopy(der, j, resultado, k + izq.length - i, der.length - j);
    return resultado;
}

Complejidad: O(n log n)

Ordenamiento Rápido (QuickSort)

Divide usando pivotes y ordena recursivamente las particiones.

public static void ordenarRapido(int[] datos, int inicio, int fin) {
    if (inicio < fin) {
        int indicePivote = particionar(datos, inicio, fin);
        ordenarRapido(datos, inicio, indicePivote - 1);
        ordenarRapido(datos, indicePivote + 1, fin);
    }
}

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

Complejidad: Mejor O(n log n) - Peor O(n²)

Ordenamiento por Montículos (HeapSort)

Construye un heap máximo y extrae elementos en orden.

public static void ordenarMonticulo(int[] datos) {
    int n = datos.length;
    for (int i = n / 2 - 1; i >= 0; i--)
        ajustarMonticulo(datos, n, i);
    
    for (int i = n - 1; i > 0; i--) {
        intercambiar(datos, 0, i);
        ajustarMonticulo(datos, i, 0);
    }
}

private static void ajustarMonticulo(int[] datos, int n, int raiz) {
    int maximo = raiz;
    int izq = 2 * raiz + 1;
    int der = 2 * raiz + 2;
    
    if (izq < n && datos[izq] > datos[maximo]) maximo = izq;
    if (der < n && datos[der] > datos[maximo]) maximo = der;
    
    if (maximo != raiz) {
        intercambiar(datos, raiz, maximo);
        ajustarMonticulo(datos, n, maximo);
    }
}

Complejidad: O(n log n)

Ordenamiento por Conteo

Cuenta apariciones de elementos y reconstruye el arreglo.

public static int[] ordenarConteo(int[] datos) {
    int max = Arrays.stream(datos).max().getAsInt();
    int[] contadores = new int[max + 1];
    
    for (int valor : datos) contadores[valor]++;
    
    int indice = 0;
    for (int i = 0; i <= max; i++) {
        while (contadores[i]-- > 0) 
            datos[indice++] = i;
    }
    return datos;
}

Complejidad: O(n + k) (k = rango de valores)

Ordenamiento por Cubetas

Distribuye elementos en contenedores y ordena individualmente.

public static List<integer> ordenarCubetas(List<integer> datos, int tamañoCubeta) {
    int min = Collections.min(datos);
    int max = Collections.max(datos);
    
    List<list>> cubetas = new ArrayList<>();
    int numCubetas = (max - min) / tamañoCubeta + 1;
    for (int i = 0; i < numCubetas; i++) 
        cubetas.add(new ArrayList<>());
    
    for (int valor : datos) 
        cubetas.get((valor - min) / tamañoCubeta).add(valor);
    
    List<integer> resultado = new ArrayList<>();
    for (List<integer> cubeta : cubetas) {
        Collections.sort(cubeta);
        resultado.addAll(cubeta);
    }
    return resultado;
}</integer></integer></list></integer></integer>

Complejidad: Mejor O(n + k) - Peor O(n²)

Ordenamiento Radix

Ordena por dígitos individuales desde el menos significativo.

public static int[] ordenarRadix(int[] datos) {
    int max = Arrays.stream(datos).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) 
        contarOrdenar(datos, exp);
    return datos;
}

private static void contarOrdenar(int[] datos, int exp) {
    int[] salida = new int[datos.length];
    int[] contador = new int[10];
    
    for (int valor : datos) 
        contador[(valor / exp) % 10]++;
    
    for (int i = 1; i < 10; i++) 
        contador[i] += contador[i - 1];
    
    for (int i = datos.length - 1; i >= 0; i--) {
        salida[contador[(datos[i] / exp) % 10] - 1] = datos[i];
        contador[(datos[i] / exp) % 10]--;
    }
    System.arraycopy(salida, 0, datos, 0, datos.length);
}

Complejidad: O(n * k) (k = número de dígitos)