25.10.2022

Ordenamiento_por_conteo( A, B, k )
1  Sea C[0..k] un nuevo arreglo
2  for i=0 to k
3      C[i] = 0      # se limpia del arreglo C
4  for j=1 to A.length
5      C[ A[j] ] += 1
6  # C[i] contiene ahora el número de elementos iguales a i
7  for i=1 to k
8      C[i] += C[i-1]
9  # C[i] contiene ahora el número de elementos menores o iguales que i
10 for j=A.lenght downto 1
11     key = A[j]
11     B[ C[ key ] ] = key
12     C[ key ] -= 1

Un ejemplo,

A = [ 2 5 3 0 2 3 0 3 ]

Las llaves van desde el 0 hasta el 5, entonces k=5. k es la llave más grande.

C[0..5]
En el ciclo de las líneas 2-3
C[ 0 0 0 0 0 0 ]

En el ciclo de las líneas 4-5 se cuentan los
elementos y se almacenan en C

  i   C[i]  líneas 7-8
--------------------.-
  0    2       2
  1    0       2
  2    2       4
  3    3       7
  4    0       7
  5    1       8

Ciclo de las líneas 10-12

A = [ 2 5 3 0 2 3 0 3 ]

j=8
key = 3 
B[7] = 3
B = [ - - - - - - 3 - ]
C = [ 2 2 4 6 7 8 ]

j=7
key = 0
B[2] = 0
B = [ - 0 - - - - 3 - ]
C = [ 1 2 4 6 7 8 ]

j=6
key = 3
B[6] = 3
B = [ - 0 - - - 3 3 - ]
C = [ 1 2 4 5 7 8 ]

j=5
key = 2
B[4] = 2
B = [ - 0 - 2 - 3 3 - ]
C = [ 1 2 3 5 7 8 ]

j=4
key = 0
B[1] = 0
B = [ 0 0 - 2 - 3 3 - ]
C = [ 0 2 3 5 7 8 ]

j=3
key = 3
B[5] = 3
B = [ 0 0 - 2 3 3 3 - ]
C = [ 0 2 3 4 7 8 ]

j=2
key = 5
B[8] = 5
B = [ 0 0 - 2 3 3 3 5 ]
C = [ 0 2 3 4 7 7 ]

j=1
key = 2
B[3] = 2
B = [ 0 0 2 2 3 3 3 5 ]
C = [ 1 2 2 4 7 7 ]

y el resultado está en B, que ya está ordenado

Ok!