Data Structure & Algorithms
Counting sort, radix sort y criterios para elegir algoritmos de ordenamiento según rango, representación, estabilidad, memoria y garantías.
Los algoritmos de sorting basados únicamente en comparaciones tienen un límite de Ω(n log n) en el peor caso para ordenar claves arbitrarias.
Counting sort y radix sort pueden superar ese límite porque usan información adicional sobre las claves: rango numérico, dígitos o representación. No contradicen el límite; trabajan bajo un modelo diferente.
Un algoritmo por comparación debe distinguir entre n! órdenes posibles. Cada comparación tiene al menos dos resultados y puede verse como una bifurcación en un árbol de decisiones.
Para tener al menos n! hojas, la altura debe satisfacer:
2^h ≥ n!
h ≥ log₂(n!) = Ω(n log n)Merge sort y heap sort alcanzan O(n log n) en el peor caso. Quick sort lo alcanza en promedio, pero puede degradarse a O(n²).
Counting sort funciona cuando las claves son enteros dentro de un rango manejable.
Si los valores están entre min y max, define:
k = max - min + 1Cuenta cuántas veces aparece cada clave y reconstruye el resultado.
function countingSort(values: number[]): number[] {
if (values.length <= 1) return [...values];
let min = values[0];
let max = values[0];
for (const value of values) {
if (!Number.isInteger(value)) {
throw new TypeError("Counting sort requires integers");
}
min = Math.min(min, value);
max = Math.max(max, value);
}
const range = max - min + 1;
const counts = Array(range).fill(0);
for (const value of values) {
counts[value - min] += 1;
}
const result: number[] = [];
for (let offset = 0; offset < counts.length; offset += 1) {
for (let count = 0; count < counts[offset]; count += 1) {
result.push(offset + min);
}
}
return result;
}O(n + k);O(k) más el resultado;n: cantidad de valores;k: tamaño del rango.Si ordenas 100 números entre 0 y 10, es excelente. Si son 100 números entre 0 y 10¹², reservar el rango es inviable.
La reconstrucción anterior ordena números, pero no conserva el orden relativo de objetos con la misma clave.
Para estabilidad:
type Item = {
key: number;
id: string;
};
function stableCountingSort(items: Item[], maxKey: number): Item[] {
const counts = Array(maxKey + 1).fill(0);
for (const item of items) {
if (!Number.isInteger(item.key) || item.key < 0 || item.key > maxKey) {
throw new RangeError("Key is outside the configured range");
}
counts[item.key] += 1;
}
for (let key = 1; key < counts.length; key += 1) {
counts[key] += counts[key - 1];
}
const result = Array<Item>(items.length);
for (let index = items.length - 1; index >= 0; index -= 1) {
const item = items[index];
const position = --counts[item.key];
result[position] = item;
}
return result;
}Recorrer de derecha a izquierda es lo que conserva el orden relativo de claves iguales.
Radix sort procesa una parte de la clave por pasada, normalmente dígitos o bytes.
Procesa desde el dígito menos significativo hacia el más significativo.
170, 45, 75, 90, 802, 24, 2, 66
↓ unidades
↓ decenas
↓ centenas
resultado ordenadoCada pasada debe usar un sorting estable. Si no, una pasada posterior destruye el orden establecido por las anteriores.
function radixSortNonNegative(values: number[]): number[] {
if (values.some((value) => !Number.isSafeInteger(value) || value < 0)) {
throw new TypeError("This version requires non-negative safe integers");
}
let result = [...values];
const max = result.length === 0 ? 0 : Math.max(...result);
for (let divisor = 1; Math.floor(max / divisor) > 0; divisor *= 10) {
const buckets: number[][] = Array.from({ length: 10 }, () => []);
for (const value of result) {
const digit = Math.floor(value / divisor) % 10;
buckets[digit].push(value);
}
result = buckets.flat();
}
return result;
}Esta implementación es educativa. Math.max(...result) puede fallar con arrays enormes por la cantidad de argumentos y flat() crea arrays adicionales. Una versión de producción usaría counting sort estable por dígito y un máximo calculado con loop.
Si hay d dígitos y la base tiene tamaño b:
O(d(n + b));O(n + b).No es simplemente O(n): d depende del tamaño de las claves y de la base.
La versión anterior no los admite. Una estrategia es:
Debes tratar -0, límites de enteros y representación si el dominio los incluye.
Puede procesar caracteres desde una posición, pero surgen decisiones:
Orden lexicográfico de producto no equivale necesariamente a comparar code points.
Distribuye valores en buckets según un rango, ordena cada bucket y concatena.
Su buen rendimiento depende de una distribución aproximadamente uniforme. Con una distribución adversarial, todos los elementos pueden caer en el mismo bucket y el costo depende del algoritmo interno.
Un sorting es estable si elementos con claves equivalentes conservan su orden relativo.
entrada: Ana(2), Luis(1), Sara(2)
estable: Luis(1), Ana(2), Sara(2)La estabilidad importa al ordenar varias veces por criterios. Puedes ordenar primero por nombre y luego de forma estable por departamento para conservar el orden secundario.
“In-place” suele significar O(1) o O(log n) de memoria auxiliar, pero la definición puede variar respecto al call stack y a la salida.
O(n) adicional.Un comparador debe cumplir:
compare(a, a) = 0;Un comparador inconsistente puede producir resultados impredecibles incluso si el algoritmo está implementado correctamente.
Con números en JavaScript:
const ascending = (a: number, b: number) => a - b;Debes decidir qué hacer con NaN, Infinity, -0 y valores fuera de Number.isSafeInteger cuando importen.
| Situación | Elección razonable | Motivo |
|---|---|---|
| Uso general en aplicación | Sort nativo con comparador | Implementación optimizada y probada |
| Necesitas peor caso O(n log n) y estabilidad | Merge sort | Garantías claras |
| Memoria auxiliar mínima | Heap sort | In-place y peor caso O(n log n) |
| Array pequeño o casi ordenado | Insertion sort | Bajo overhead y adaptativo |
| Enteros en rango pequeño | Counting sort | O(n + k) |
| Claves con dígitos acotados | Radix sort | Evita comparación global |
| Solo necesitas k menores/mayores | Heap o selection | No ordena trabajo innecesario |
En trabajo real, no reimplementes sorting sin una razón. La implementación educativa enseña invariantes; la biblioteca del runtime suele ser mejor para producción.
Dos algoritmos con la misma Big O pueden rendir distinto por:
Mide con datos representativos, pero no uses un benchmark pequeño para negar una diferencia asintótica.
O(n) sin mencionar k.O(n).O(n).Ω(n log n) aplica a sorting por comparaciones arbitrarias.O(n + k) solo es atractivo si k es razonable.¿Por qué counting sort puede ser peor que merge sort aunque su fórmula parezca lineal?
Porque su costo incluye k, el tamaño del rango. Si k es mucho mayor que n, inicializar y recorrer el array de frecuencias puede consumir más tiempo y memoria que O(n log n).