Motivation
Lección 2 de 9 del curso Counting Sort - Serie de DSA de Coddy.
Counting Sort nunca compara dos elementos. Utiliza sus valores directamente como índices en un arreglo count, que es lo que le permite ejecutarse en tiempo lineal.
¿Por qué aprender Counting Sort?
- Tiempo lineal: se ejecuta en O(n + k), donde n es el número de elementos y k es el rango de valores. Cuando k es pequeño, eso supera a O(n log n).
- Estable (cuando se hace con cuidado): una base para Radix Sort, que encadena varias pasadas de counting-sort.
- Una idea diferente: ordenar contando valores en lugar de compararlos.
La desventaja: necesita memoria O(k) para el arreglo count, por lo que no es adecuado cuando el rango de valores es enorme (por ejemplo, ordenar un puñado de números hasta mil millones).
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
