Counting Sort (Ordenamiento por conteo)
Algoritmos como Merge Sort realizan operaciones para ordenar una secuencia de elementos. La mayoría de las funciones integradas de
sort() en diferentes lenguajes de programación también llevan a cabo operaciones. Surge la pregunta natural: ¿existe alguna forma de ordenar más rápidamente?Un algoritmo básico que ordena una secuencia de elementos en tiempo lineal—es decir, que realiza operaciones—es el algoritmo Counting sort (ordenamiento por conteo). Counting sort es un método eficiente de ordenación en tiempo lineal, especialmente adecuado para colecciones de elementos en las que se sabe que los valores son números enteros pequeños.
La idea básica detrás de Counting sort consiste en usar una estructura similar a un histograma para contar cuántos elementos de la colección de entrada tienen un valor determinado y, a continuación, emplear esta información para reordenar los elementos de la colección en el orden deseado.
Entonces, para ordenar un arreglo con valores
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7], crearíamos un histograma que muestre cuántas repeticiones hay de cada número; por ejemplo, se observa que hay 6 unos, 2 doses, 5 treses, etc.: [6, 2, 5, 4, 5, 1, 6, 1] (como se muestra en la imagen).
a = ...
bottom, top = min(a), max(a) + 1 # Determinar el rango
hist = [0] * (top - bottom) # Llenar el rango con ceros => sin recuentos
for num in a: # Iterar a través del arreglo
hist[num - bottom] += 1 # Incrementar el valor en el histograma
res = [] # Inicializar el arreglo de resultado
for num in range(bottom, top): # Iterar sobre el rango
res += [num] * hist[num - bottom] # Añadir tantas repeticiones de 'num' al resultado como indique el histogramaAl final, el resultado tendrá el valor
[1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8].Ten en cuenta que este método solo funciona con números, concretamente valores pequeños. Por otro lado, algoritmos como Bubble sort u Merge sort funcionan con cualquier tipo de elemento siempre que sea posible compararlos entre sí.
Por lo tanto, el algoritmo realiza en total operaciones, donde
n es el número de elementos del arreglo inicial y r es el tamaño del rango de valores en dicho arreglo. Esto puede ser especialmente rápido en comparación con algoritmos como Merge sort cuando se trata de números que presentan un rango de valores relativamente pequeño.🤔
¿Existen otros algoritmos en tiempo lineal para ordenar?
Sí, puedes echar un vistazo a Radix-sort (ordenamiento por base). Sin embargo, estos métodos solo funcionan con números.
En el caso de algoritmos basados en comparaciones, que pueden trabajar con cualquier tipo de secuencia siempre y cuando los elementos se puedan comparar, el mejor algoritmo posible realiza operaciones, no menos.
Entrada
La primera línea de la entrada contiene un entero
n (1 ≤ n ≤ ).La siguiente línea contiene
n enteros separados por espacios: (-100 ≤ ≤ 100).Salida
El programa debe imprimir los
n enteros dados, separados por un espacio, en orden creciente.Ejemplos
Entrada | Salida |
5
-3 5 -1 2 10 | -3 -1 2 5 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB