Sorting Algorithm

Los algoritmos de ordenación disponen los elementos en orden —quicksort, merge sort y heapsort son comunes— con complejidades que van de O(n log n) a O(n²).

Propósito

Ordenar datos desordenados, base de la búsqueda, la deduplicación y la presentación.

Mecanismo

La ordenación por comparación tiene un límite inferior de O(n log n). Quicksort promedia O(n log n), peor caso O(n²), in situ. Merge sort es O(n log n), estable, pero necesita O(n) de espacio. Heapsort es O(n log n) in situ. Counting/radix son no comparativos y pueden ser O(n). Las ordenaciones estables preservan el orden relativo de los elementos iguales.

Casos de uso

ORDER BY de bases de datos
Preprocesamiento antes de buscar
Rankings y tablas de líderes
Deduplicación (ordenar + comparación adyacente)

Ejemplos

entrada
```
[3,1,4,1,5] → quicksort
```
Output
```
[1,1,3,4,5]
```
O(n log n) average

Errores comunes

Quicksort recursion overhead is high for small arrays: Use insertion sort for small arrays (a quicksort optimization)

Términos relacionados

La notación O grande describe el límite superior asintótico de una función, usada para analizar la complejidad temporal/espacial de los algoritmos ignorando constantes y términos de orden inferior.

La búsqueda binaria compara contra el elemento central de un array ordenado y reduce el rango a la mitad cada vez, localizando un objetivo en O(log n); es el algoritmo de búsqueda eficiente fundamental.

Una tabla hash mapea claves a un array de cubos mediante una función hash, ofreciendo búsqueda/inserción/borrado promedio O(1); es una de las estructuras de datos más usadas.

Herramientas relacionadas

Ordenar y eliminar duplicados

Sort lines alphabetically, numerically, by length, or naturally; deduplicate; reverse or shuffle. Gratis, privado y 100% del lado del cliente.

References