Complejidad Temporal
Mejor: O(n + k)
Prom: O(n + k)
Peor: O(n + k)
Counting Sort es un algoritmo de ordenamiento no basado en comparaciones. Cuenta las ocurrencias de cada valor y usa aritmética para determinar posiciones.
Cómo funciona:
1. Encontrar el rango de valores de entrada (mín a máx)
2. Crear un arreglo de conteo para almacenar la frecuencia de cada valor
3. Modificar el arreglo de conteo para almacenar conteos acumulados
4. Construir el arreglo de salida colocando elementos en sus posiciones correctas
Complejidad Temporal:
Mejor: O(n + k)
Promedio: O(n + k)
Peor: O(n + k)
donde k es el rango de valores de entrada
Complejidad Espacial: O(n + k)
Propiedades:
- Ordenamiento estable
- No es in-place
- No basado en comparaciones
- Muy eficiente cuando k es pequeño respecto a n
Counting Sort es ideal para ordenar enteros dentro de un rango conocido y pequeño. Se usa como subrutina en Radix Sort.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Counting Sort (Ordenamiento por Conteo)?
- Counting Sort es un algoritmo de ordenamiento no basado en comparaciones. Cuenta las ocurrencias de cada valor y usa aritmética para determinar posiciones.
- ¿Cuál es la complejidad de Counting Sort (Ordenamiento por Conteo)?
- Tiempo (promedio): O(n + k) · Espacio: O(n + k)
- ¿Para quién es este visualizador de Counting Sort (Ordenamiento por Conteo)?
- La visualización de Counting Sort (Ordenamiento por Conteo) está pensada para nivel intermedio, dentro de la categoría Ordenamiento. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Counting Sort (Ordenamiento por Conteo)?
- En la misma categoría (Ordenamiento) puedes explorar: Bubble Sort, Selection Sort, Insertion Sort. Todos tienen visualización interactiva.