Algoritmos de Ordenamiento

El algoritmo de ordenamiento más básico que compara repetidamente elementos adyacentes y los intercambia si están en orden incorrecto. Como burbujas que suben a la superficie, los valores más grandes se mueven gradualmente al final del arreglo. Ideal para conjuntos de datos pequeños o con fines educativos para comprender los fundamentos del ordenamiento.

Encuentra el elemento más pequeño y lo mueve al frente repetidamente. Cada iteración "selecciona" el mínimo de los elementos restantes y lo coloca después de la porción ordenada. Fácil de implementar con uso mínimo de memoria, pero siempre toma tiempo O(n²) independientemente de la entrada.

Un algoritmo de ordenamiento altamente eficiente que selecciona un elemento pivote y particiona el arreglo con valores más pequeños a la izquierda y más grandes a la derecha. Promedia O(n log n) y es el método de ordenamiento más utilizado en la práctica. Forma la base de las funciones de ordenamiento integradas en la mayoría de los lenguajes de programación.

Utiliza una estructura de datos de montículo binario construyendo primero un montículo máximo, luego extrayendo repetidamente el elemento raíz para ordenar. Garantiza complejidad de tiempo O(n log n) en todos los casos sin requerir memoria adicional. También sirve como base para implementaciones de colas de prioridad.

Un algoritmo de ordenamiento sin comparación que cuenta las ocurrencias de cada elemento y usa aritmética para determinar posiciones. Logra complejidad de tiempo O(n+k) donde k es el rango de valores de entrada. Ideal para ordenar enteros dentro de un rango conocido y limitado. Forma la base del ordenamiento radix.

Un algoritmo de ordenamiento sin comparación que procesa elementos dígito por dígito del menos significativo al más significativo. Usa counting sort como subrutina para cada posición de dígito. Logra tiempo O(d(n+k)) donde d es el número de dígitos. Excelente para ordenar enteros o cadenas de longitud fija.

Una optimización del ordenamiento por inserción que permite el intercambio de elementos que están muy separados. Usa una secuencia de brechas que disminuye a 1, permitiendo que el algoritmo mueva elementos más cerca de sus posiciones finales más rápido. Nombrado en honor a Donald Shell, quien lo inventó en 1959.

Un algoritmo de ordenamiento basado en distribución que distribuye elementos en varios cubos. Luego, cada cubo se ordena individualmente usando otro algoritmo de ordenamiento. Funciona mejor cuando la entrada está distribuida uniformemente en un rango. La complejidad de tiempo promedio es O(n+k).

Un algoritmo de divide y vencerás que divide el arreglo por la mitad, ordena cada mitad recursivamente y luego las fusiona nuevamente. Garantiza tiempo O(n log n) y es estable, pero requiere memoria adicional. Particularmente efectivo para conjuntos de datos grandes y ordenamiento de listas enlazadas.

Funciona como ordenar cartas de juego en tus manos: insertando cada elemento uno a la vez en su posición correcta. Se ejecuta en tiempo O(n) para datos ya ordenados, lo que lo hace muy eficiente para arreglos pequeños o conjuntos de datos casi ordenados. Algoritmo simple pero adaptativo.

Mejora del ordenamiento burbuja que elimina valores pequeños cerca del final de la lista (tortugas). Usa una secuencia de brechas decrecientes comenzando con la longitud del arreglo, mejorando la complejidad del peor caso. Práctico para conjuntos de datos de tamaño medio donde se valora la simplicidad de implementación sobre el rendimiento óptimo.

Algoritmo de ordenamiento simple similar al ordenamiento por inserción, nombrado por la forma en que los gnomos de jardín ordenan macetas de flores. Se mueve hacia atrás cuando los elementos están fuera de orden, luego hacia adelante nuevamente. Aunque O(n²) como el ordenamiento burbuja, su simplicidad lo hace útil para enseñar conceptos de ordenamiento y manejar conjuntos de datos pequeños.