Problem:
Counting Sort Counting sort can be used for sorting elements in an array which each of the n input elements is an integer in the range 0 to k. The idea of counting sort is to determine, for each input element x, the number of elements less than x as C[x]. This information can be used to place element x directly into its position in the output array B. This scheme must be modified to handle the situation in which several elements have the same value. Please see the following pseudocode for the detail: Counting-Sort(A, B, k)
1    for i = 0 to k
2        do C[i] = 0
3    for j = 1 to length[A]
4        do C[A[j]] = C[A[j]]+1
5    /* C[i] now contains the number of elements equal to i */
6    for i = 1 to k
7    do C[i] = C[i] + C[i-1]
8    /* C[i] now contains the number of elements less than or equal to i */
9    for j = length[A] downto 1
10       do B[C[A[j]]] = A[j]
11          C[A[j]] = C[A[j]]-1 Write a program which sorts elements of given array ascending order based on the counting sort. Input The first line of the input includes an integer n , the number of elements in the sequence. In the second line, n elements of the sequence are given separated by spaces characters. Output Print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character. Constraints  1 ≤ n ≤ 2,000,000  0 ≤ A[ i ] ≤ 10,000  Sample Input 1 7
2 5 1 3 2 3 0 Sample Output 1 0 1 2 2 3 3 5

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

C = [0]*10001
for i in A:
    C[i] += 1

tmp = C[0]
for i in range(1, 10001):
    C[i] += tmp
    tmp = C[i]

ans = [0]*N
for i in range(N-1, -1, -1):
    tmp = A[i]
    ix = C[tmp]-1
    ans[ix] = tmp
    C[tmp] -= 1

print(*ans, sep=' ')

Solution (Python):



def countingsort(A, B, k):
    n = len(A)
    C = [0 for i in range(0, k + 1)]
    for i in range(0, n):
        C[A[i]] += 1
    for i in range(0, k + 1):
        C[i] += C[i - 1]
    for i in range(n - 1, -1, -1):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1


n = int(input())
A = [int(i) for i in input().split()]
B = [None for i in range(n)]
countingsort(A, B, 10000)
for i in range(0, n - 1):
    print(B[i], end=" ")
print(B[n - 1])

Solution (Python):
maxx = 2000001;
maxnum = 10010;

n=int(input())
A=[int(x) for x in input().split()]  
A.insert(0,0) 
B=[-1 for x in range(n)]
C=[0 for x in range(maxnum)]



for a in A[1:]:
    C[a]+=1
for i in range(1,maxnum): 
    C[i]+=C[i - 1]
    
for j in range(1,n+1):
    B[C[A[j]]-1]=A[j]
    C[A[j]]-=1

lens=len(B)    
for i in range(0,lens-1):
    print(B[i],end=' ')
print(B[lens-1])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

M = [0]*10001
for a in A:
    M[a] += 1

first = True
for i, m in enumerate(M):
    if m > 0:
        if first:
            print(*([i]*m), end='')
            first = False
        else:
            print(' ', end='')
            print(*([i]*m), end='')
print()

Solution (Python):
import sys,collections
n = int(sys.stdin.readline())

A = list(map(int,sys.stdin.readline().split()))
def CountingSort(A,B,k):
  
  C = [0]*(k)
  for j in range(n):
    C[A[j]] += 1
    
  for i in range(1,k):
    C[i] = C[i]+C[i-1]
  
  for j in range(n)[::-1]:
    B[C[A[j]]-1] = A[j]
    C[A[j]] -= 1
    
    
B = [0]*n
CountingSort(A,B,10000)
print(" ".join(map(str,B)))

Solution (Python):
def CountingSort(A, B, k):
    C = [ 0 for i in range(k + 1)]
    
    for i in range(len(A)):
        C[A[i]] += 1

    for j in range(1, len(C)):
        C[j] = C[j] + C[j - 1]

    for j in reversed(range(len(A))):
        B[ C[ A[j] ] - 1 ] = A[j]
        C[ A[j] ] -= 1

def Main():
    n = int(input())

    A = [int(a) for a in input().split()]
    B = [0 for i in range(len(A))]
    k = max(A) + 1

    CountingSort(A, B, k)

    print(*B)

Main()

Solution (Python):
def countingSort(A, B, k):
    C = [0]*k

    for i in range(len(A)):
        C[A[i]] = C[A[i]] + 1
        

    for i in range(1, k):
        C[i] = C[i] + C[i-1]
        
    
    for j in range(len(A)):
        B[C[A[len(A)-1-j]]-1] = A[len(A)-1-j]
        C[A[len(A)-1-j]] = C[A[len(A)-1-j]] - 1
        

    return " ".join(map(str, B))

n = int(input())
X = [0]*n
Y = list(map(int, input().split()))

print(countingSort(Y, X, max(Y)+1))

Solution (Python):
def counting_sort(A):
    K = max(A) + 1
    N = len(A)
    C = [0] * K
    for a in A:
        C[a] += 1
    for k in range(1, K):
        C[k] = C[k - 1] + C[k]
    B = []
    b = 0
    for n in range(N):
        while n >= C[b]:
            b += 1
        B.append(b)
    return B


n = int(input())
*A, = map(int, input().split())
B = counting_sort(A)
print(*B)

Solution (Python):
def CountingSort(A,k):
    ans=[0 for _ in range(len(A))]
    C=[0 for _ in range(k+1)]
    for i in range(len(A)):
        C[A[i]]+=1
    for i in range(1,k+1):
        C[i]=C[i]+C[i-1]
    for i in reversed(range(len(A))):
        ans[C[A[i]]-1]=A[i]
        C[A[i]]-=1
    return ans
    
n=int(input())
A=list(map(int,input().split()))
k=max(A)
ans=CountingSort(A,k)

print(' '.join(map(str,ans)))

Solution (Python):
def countingsort(A, k):
    C = [0] * (k+1)
    n = len(A)
    
    for i in A:
        C[i] += 1
        
    for i in range(1, k+1):
        C[i] += C[i-1]
        
    B = [0] * n
    for i in A:
        rank = C[i]
        B[rank-1] = i
        C[i] -= 1
        
    return B
    
n = int(input())
A = [int(i) for i in input().split()]

ans = countingsort(A, 10000)
print(" ".join([str(i) for i in ans]))

Solution (Python):
def countingSort(A):
    VMAX = 10**4 
    C = [0] * VMAX
    result = [None] * (len(A))

    
    for i in range(len(A)):
        C[A[i]] += 1

    
    for i in range(1, VMAX):
        C[i] += C[i-1]

    for i in range(len(A)-1, -1, -1): 
        result[C[A[i]]-1] = A [i]
        C[A[i]] -= 1

    return result

n = int(input())
A = [i for i in map(int, input().split())]
result = countingSort(A)
result = [i for i in map(str, result)]
print(' '.join(result))

Solution (Python):
def counting_sort(A, k):
    C = [0] * (k + 1)
    for a in A:
        C[a] += 1
    j = 0
    for i, c in enumerate(C):
        for k in range(c):
            A[j + k] = i
        j += c


K = 10_000
N = int(input())
A = list(map(int, input().split()))
counting_sort(A, K)
print(*A)

Solution (Python):



def counting_sort(A, MAX=10010):
    count = [0] * MAX
    for a in A:
        count[a] += 1
    
    for i in range(1, len(count)):
        count[i] = count[i-1] + count[i]
    
    b = [None]*len(A)
    for i in range(len(A)-1, -1, -1):
        
        ai = A[i]
        ci = count[ai]
        b[ci-1] = ai
        
        count[ai] -= 1
    
    return b

n = int(input())
a = [int(i) for i in input().split()]

b = counting_sort(a)

print(*b)

Solution (Python):
N = int(input())
num_list = [int(item) for item in input().split()]

def countingSort(A, k):
    B = [0 for _ in range(N+1)]
    C = [0 for _ in range(k+1)]

    for j in range(N):
        C[A[j]] += 1
    
    for i in range(1, k+1):
        C[i] = C[i] + C[i - 1]

    for j in reversed(range(N)):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    return B[1:]


print(*countingSort(num_list, max(num_list)))

Solution (Python):
INF = int(1e4)
def countingSort(A, k):
    n = len(A)
    output = [INF for _ in range(n+1)]
    count = [0 for _ in range(k)]
    for i in range(n):
        count[A[i]] += 1

    for i in range(1, k):
        count[i] = count[i] + count[i-1] 

    for i in reversed(range(n)): 
        output[count[A[i]]] = A[i]
        count[A[i]] -= 1

    return output[1:]

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = countingSort(a, INF)
    for i in range(n):
        if i == n-1:
            print(ans[i])
        else:
            print(ans[i], end=' ')
main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

a.sort()
print(*a)

Solution (Python):
import copy

def CountingSort(A, B, k):
    C = [0] * k

    
    for j in range(n):
        C[A[j]] += 1

    
    for i in range(1, k):
        C[i] = C[i] + C[i - 1]

    for j in range(n)[::-1]:
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1



n = int(input())
A = list(map(int, input().split()))

B = [0] * (n + 1)
CountingSort(A, B, max(A) + 1)

print(*B[1:])

Solution (Python):
def counting_sort(A):
    n = len(A)
    C = [0] * 10000
    B = [0] * n
    for i in range(n):
        C[A[i]] += 1

    for i in range(1, 10000):
        C[i] = C[i] + C[i-1]

    for i in reversed(range(n)):
        
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1

    return B


if __name__ == "__main__":
    input()
    A = list(map(int, input().split()))

    A = counting_sort(A)

    print(' '.join(map(str, A)))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
k = max(a) + 1

b = [0 for i in range(n)]
c = [0 for i in range(k)]

for j in range(n):
    c[a[j]] += 1

for i in range(1, k):
    c[i] += c[i-1]

for j in range(n-1, -1, -1):
    b[c[a[j]] - 1] = a[j]
    c[a[j]] -= 1

print(*b)

Solution (Python):
def countingSort(A):
    k = max(A)
    n = len(A)
    C = [0 for i in range(k+1)]

    
    for i in range(n):
        C[A[i]] += 1

    

    
    for i in range(1,k+1):
        C[i] += C[i-1]

    

    B = [0 for i in range(n)]

    for i in range(n-1,-1,-1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
    
    return B

N = int(input())
A = list(map(int,input().split()))
ans = countingSort(A)
print(' '.join(map(str,ans)))

Solution (Python):

n_max = 2000000
a_max = 10000


input_n = int(input())
input_a = list(map(int, input().split()))
output = list()


c_list = [0] * (a_max + 1)
for i in input_a:
    c_list[i] += 1
for i in range(1, a_max+1):
    c_list[i] += c_list[i-1]


sort_list = [0 for i in range(input_n)]
for i in range(input_n-1, -1, -1):
    sort_list[c_list[input_a[i]]-1] = input_a[i]
    c_list[input_a[i]] -= 1


print(" ".join(map(str, sort_list)))

Solution (Python):


N = int(input())
lst = list(map(int, input().split()))
k = max(lst)
B = [-1]*N
C = [0] * (k+1)

def counting_sort(A, B, k):
    
    for a in A:
        C[a] += 1
    
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    for a in A[::-1]:
        C[a] -= 1
        B[C[a]] = a
        
counting_sort(lst, B, k)
print(*B)

Solution (Python):
def countingsort(a):
    max_num = max(a)
    min_num = min(a)
    count = [0]*(max_num - min_num + 1)
    for ele in a:
        count[ele - min_num] += 1

    return [ele for ele,cnt in enumerate(count,start = min_num) for _ in range(cnt)]

        

n = int(input())
A = [int(s) for s in input().split()]
print(" ".join(map(str,countingsort(A))))

Solution (Python):
def counting_sort():
    input()
    C = [0]*(10000+1)
    b = []
    for a in map(int, input().split()):
        C[a] += 1
    for i, c in enumerate(C):
        b += [str(i)]*c
    print(' '.join(b))
        
if __name__ == "__main__":
    counting_sort()

Solution (Python):
def countingSort(A,k):
    
    C=[0 for _ in range(k+1)]

    
    for i in range(len(A)):
        C[A[i]]+=1

    
    for i in range(1,k+1):
        C[i]=C[i]+C[i-1]

    B=[0 for _ in range(len(A))]
    for i in range(len(A)-1,-1,-1):

        C[A[i]]-=1
        B[C[A[i]]] = A[i]

    return B


n=int(input())
a=list(map(int,input().split()))
ans=countingSort(a, max(a))
print(*ans)

Solution (Python):
def counting_sort(A, B, n, k):
    C = [0] * (k+1)
    for ai in A:
        C[ai] += 1
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    for j in range(n)[::-1]:
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
    return B
n = int(input())
A = list(map(int, input().split(' ')))
k = max(A)
B = [0] * n
sorted_A = counting_sort(A, B, n, k)
print(" ".join(map(str, sorted_A)))

Solution (Python):
def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)

    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1
    return [ele for ele, cnt in enumerate(count, start=min_num) for _ in range(cnt)]

n=int(input())
S=list(map(int,input().split()))
S=count_sort(S)
print(' '.join(list(map(str,S))))

Solution (Python):
def Counting_Sort(A,k):
    c = [0]*(k+1)
    b = [0]*n
    for a in A:
        c[a]+=1
    for i in range(1,k+1):
        c[i] = c[i] + c[i-1]
    
    for a in A:
        rank = c[a]
        b[rank-1] = a
        c[a] -= 1
    print(*b)

n = int(input())
a = list(map(int, input().split()))
k = max(a)+1
Counting_Sort(a,k)

Solution (Python):


def CountingSort(A, B, k):
    C = [0] * (k + 1)

    
    for i in range(len(A)):
        C[A[i]] += 1

    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for i in reversed(range(len(A))):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1

    return B

n = int(input())
A = list(map(int, input().split()))
B = [0] * len(A)
k = 10000

B = CountingSort(A, B, k)

result = ''

for b in B:
    result += str(b) + ' '

print(result[:-1])

Solution (Python):
def CountingSort(A, B, k):
    C = [ 0 for i in range(0, k+1)]
    for j in range(0, len(A)):
        C[A[j]] = C[A[j]] + 1
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    for j in range(n-1, -1, -1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] = C[A[j]] - 1
        
n = int(input())
A = list(map(int, input().split()))

B = [0 for i in range(n)]
k = max(A)
CountingSort(A, B, k)

print(*B)

Solution (Python):
def countingsort(A, k):
    res = [None for _ in A]
    C = [0 for i in range(k + 1)]

    for x in A:
        C[x] += 1

    for i in range(k):
        C[i + 1] = C[i + 1] + C[i]

    for x in reversed(A):
        res[C[x] - 1] = x
        C[x] -= 1

    return res

input()
A = list(map(int, input().split()))
ret = countingsort(A, 10000)
print(" ".join(map(str, ret)))

Solution (Python):
n = int(input())

P = list(map(int, input().split()))

Q = [0 for i in range(len(P))]

m = max(P)

def CountingSort(A, B, k):
  C = [0 for i in range(k+1)]

  for j in range(len(A)):
    C[A[j]] += 1

  for i in range(1, k+1):
    C[i] += C[i-1]

  for j in range(len(A)):
    B[C[A[j]]-1] = A[j]
    C[A[j]] -= 1

CountingSort(P, Q, m)

print(" ".join(map(str, Q)))

Solution (Python):
"""
計数ソートを実装する
計算量はO(n+k)
"""
def countingSort(A, B, k):
    global n
    C = [0]*(k+1) 

    for i in range(n):
        C[A[i]] += 1 
    
    for i in range(1, k+1):
        C[i] = C[i-1] + C[i]
    
    for i in range(n-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]
    
    
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
k = max(a)

countingSort(a, b, k)
b = map(str, b)
print(' '.join(b))

Solution (Python):
def countingsort(arr,maximum):
    m = maximum + 100
    count = [0] * (m)
    for a in arr:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            arr[i] = a
            i += 1
    return arr

if __name__ == '__main__':
    N = int(input())
    l = list(map(int, input().split()))

    a = 0
    li = countingsort(l,N)
    for a in range(N-1):
        print(li[a], end=" ")
    print(li[N-1])

Solution (Python):

def countingSort(a):
    j = max(a)
    c = [0 for _ in range(j + 1)]
    b = [None for _ in range(n)]
    for k in a: 
        c[k] += 1
    for k in range(1, j+1): 
        c[k] += c[k - 1]
    for k in a[::-1]: 
        c[k] -= 1
        b[c[k]] = k
    return b

n = int(input())
a = list(map(int, input().split()))
print(*countingSort(a))

Solution (Python):
def counting_sort(A, k):
    """整数列 A を昇順に計数ソートでソートした新しいリストを返す。

    A 内の整数 x はすべて 0 <= x <= k の範囲にある。
    """
    
    C = [0 for _ in range(0, k + 1)]
    for x in A:
        C[x] += 1
    
    
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    
    n = len(A)
    B = [ None for _ in range(n) ]
    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]   
        C[A[j]] -= 1
    
    return B

if __name__ == '__main__':
    import sys

    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    k = max(A)

    print(*counting_sort(A, k))

Solution (Python):
def counting_sort(in_arr, out_arr, arr_len, max_val):
    counter = [0] * (max_val + 1)  

    for i in range(arr_len):
        counter[in_arr[i]] += 1  

    for j in range(max_val):
        counter[j + 1] = counter[j + 1] + counter[j]  

    for i in reversed(range(0, arr_len)):  
        out_arr[counter[in_arr[i]] - 1] = in_arr[i]  
        counter[in_arr[i]] -= 1


def main():
    n = int(input())
    in_arr = list(map(int, input().split(" ")))
    out_arr = [0] * n
    counting_sort(in_arr, out_arr, n, 10000)
    print(" ".join(map(str, out_arr)))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
A.insert(0,0) 
B = [-1 for x in range(n)]
C = [0 for x in range(max(A) + 1)]

for a in A[1:]:
    C[a] += 1

for i in range(1, max(A) + 1): 
    C[i] += C[i - 1]
    
for j in range(1, n + 1):
    B[C[A[j]]-1] = A[j]
    C[A[j]] -= 1

print(" ".join(map(str, B)))

Solution (Python):
n = int(input())
A = [int(i) for i in input().split()]

k=max(A)

C = [0] * (k+1)

for a in A:
  C[a] = C[a] + 1

for i in range(1, k+1):
  C[i] = C[i] + C[i-1]


B = [0] * n
for a in A:
  rank = C[a]
  B[rank  - 1] = a
  C[a] = C[a] - 1

print(*B)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
k=max(a)
b=[0]*(n)
def Count(A, B, k):
	C=[0]*(k+1)
	for j in range(n):
		C[A[j]]+=1
	for i in range(1,k+1):
		C[i]+=C[i-1]
	for i in range(n-1,-1,-1):
		B[C[A[i]]-1]=A[i]
		C[A[i]]-=1
Count(a,b,k)
print(*b)

Solution (Python):


def CountingSort(A, B, k, n):
    C = []
    for i in range(k + 1):
        C.append(0)
        
    for i in range(n):
        B.append(0)
        
    for i in range(n):
        C[A[i]] += 1
    
    for i in range(1, k + 1):
        C[i] = C[i] + C[i-1]
        

    for i in range(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
        
n = int(input())
A = list(map(int, input().split())) 
B = []
k = max(A)
CountingSort(A, B, k, n)
for i in range(n-1):
    print(B[i], end = " ")
print(B[n-1])

Solution (Python):
def countingsort(A, k):
    C = [0 for _ in range(k)]
    ret = [-1 for _ in A]
    for a in A:
        C[a] += 1
    for i in range(k - 1):
        C[i + 1] += C[i]
    for a in reversed(A):
        ret[C[a]-1] = a
        C[a] -= 1
    return ret


_, *A = map(int, open(0).read().split())
A = countingsort(A, max(A) + 1)
print(' '.join(map(str, A)))

Solution (Python):

n = int(input())
A = list(map(int, input().split()))

m = max(A)
B = [0] + [0] * m
result = [None] * n

for a in A:
  B[a] += 1

for i in range(1, m+1):
  B[i] += B[i-1]

for i in range(n-1, -1, -1):
  a = A[i]
  index = B[a] - 1
  result[index] = a
  B[a] -= 1
  
print(*result)

Solution (Python):
def count_sort(numlist, n):
    C = [0 for i in range(n + 1)]
    B = [0 for i in range(len(numlist))]
    
    for num in numlist:
        C[num] += 1
    
    for i in range(1, n + 1):
        C[i] += C[i - 1]
    for n in range(len(numlist), 0, -1):
        C[numlist[n - 1]] -= 1
        B[C[numlist[n - 1]]] = numlist[n - 1]

    return B

if __name__ == '__main__':
    n = int(input())
    numlist = [int(num) for num in input().split(' ')]
    numlist = count_sort(numlist, max(numlist))
    print(str(numlist).replace(',', '').replace('[', '').replace(']', ''))

Solution (Python):
n,*a=map(int,open(0).read().split())

print(*sorted(a))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n=int(input())
    aa=list(map(int, input().split()))
    aa.sort()
    print(*aa)
main()

Solution (Python):
MAX = 10000

def bucket_sort(A):
    count_array = [0] * MAX
    B = [0] * len(A)
    for a in A:
        count_array[a] += 1

    for i in range(1, MAX):
        count_array[i] = count_array[i] + count_array[i-1]

    for a in A[::-1]:
        B[count_array[a]-1] = a
        count_array[a] -= 1
    return B

if __name__ == "__main__":
    n = int(input())
    *A, = map(int, input().split())
    
    print(*bucket_sort(A))

Solution (Python):

N = int(input())
A = list(map(int, input().split()))

VMAX = 10000

B = [0] * (N + 1)
C = [0] * (VMAX + 1)

for a in A:
    C[a] += 1



for i in range(1, VMAX+1):
    C[i] = C[i] + C[i-1]



for j in range(N):
    B[C[A[j]]] = A[j]
    C[A[j]] -= 1

print(' '.join(map(str, B[1:])))

Solution (Python):
def CountingSort(A,B,k):
    n=len(A)
    C=[0]*(k+1)
    for i in range(n):
        C[A[i]] +=1
    for i in range(1,k+1):
        C[i]=C[i-1]+C[i]
    for i in reversed(range(n)):
        B[C[A[i]]-1]=A[i]
        C[A[i]] -=1


n=int(input())
A=list(map(int,input().split()))
B=[0]*n
CountingSort(A,B,10000)
print(*B)

Solution (Python):

from itertools import accumulate
num = int(input())
maxnum = 10000

A = [int(x) for x in input().split()]
B = [0] * (maxnum +1)
C =[0] * (len(A)+1)
for i in A:
    B[i] += 1
B = list(accumulate(B))
for i in reversed( range(0,len(A))):
    k = A[i]
    j = B[k]
    B[k] -= 1
    C[j] = k
print(*C[1:])

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]

k=max(A)
C=[0]*(k+1)

for i in range(n):
    C[A[i]]+=1

for i in range(1,k+1):
    C[i] = C[i] + C[i-1]

B=[0]*(n+1)

for i in [n-i-1 for i in range(n)]:
    B[C[A[i]]] = A[i]
    C[A[i]]-=1
    

print(*B[1:])

Solution (Python):




MAX = 10000

def getdata():
    data = map(int, input().split())
    return (list(data))

def countsort(data, max):
    C =[0*x for x in range(0,max)]

    for i in data:
        C[i] += 1

    for i in range(1,max):
        C[i] = C[i] + C[i-1]
    
    B = [i*0 for i in data]
    for i in range(len(data)-1, -1,-1):
        B[C[data[i]]-1] = data[i]   
        C[data[i]] -= 1

    return B

getdata()
ans = countsort(getdata(),MAX)
print(" ".join(map(str,ans)))

Solution (Python):
def counting_sort(A, k):
    B = [0]*len(A)
    C = [0]*(k+1)
    for j in range(0, len(A)):
        C[A[j]] += 1
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    for j in range(len(A)-1, -1, -1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
    print(*B)

k = int(input())
A = list(map(int, input().split()))
counting_sort(A, max(A)+1)

Solution (Python):
def count_sort_2(arr, max_element=10000):
    c = [0] * (max_element + 1)

    for ele in arr:
        c[ele] += 1
    for i in range(1, max_element + 1):
        c[i] += c[i - 1]

    arr_copy = list(arr)
    n = len(arr)
    for i in range(n - 1, -1, -1):
        arr[c[arr_copy[i]] - 1] = arr_copy[i]
        c[arr_copy[i]] -= 1


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    
    count_sort_2(arr)

    arr = map(str, arr)
    print(' '.join(arr))

Solution (Python):
def CountingSort(A, B, k):
    C = [0 for i in range(k+1)]
    
    for j in range(n):
        C[A[j]] += 1
     
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    
    for j in range(n-1,-1,-1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
        
n = int(input())
A = list(map(int,input().split()))
B = [0 for i in range(len(A))]
k = 10000
CountingSort(A, B, k)
print(*B)

Solution (Python):

def countingSort(A, B, k):
    C = [0 for _ in range(k+1)]
    for i in range(n):
        C[A[i]] += 1
    for i in range(1, k):
        if i > 0:
            C[i] += C[i-1]
    for i in reversed(range(n)):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1

n = int(input())
A = list(map(int, input().split(" ")))
B = [0 for _ in range(n)]
countingSort(A, B, 10000)
print(*B)

Solution (Python):
N = int(input())
A = map(int, input().split())

C = [0] * 10001
for a in A:
  C[a] += 1

B = []
for i, c in enumerate(C):
  B.extend([i] * c)
print(*B)

Solution (Python):
def CountingSort(A,k):
    C=[0]*(k+1)
    for a in A:
        C[a]+=1
    for i in range(k):
        C[i+1]+=C[i]
    ret=[0]*len(A)
    for a in A[::-1]:
        ret[C[a]-1]=a
        C[a]-=1
    return ret
n=int(input())
A=list(map(int,input().split()))
print(*CountingSort(A,max(A)))

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
B = [0 for _ in range(len(A))]
k = 10000


def main():
    CountingSort(A, B, k)
    print(' '.join(map(str, B)))


def CountingSort(A, B, k):
    C = [0 for _ in range(k)]

    
    for i in range(n):
        C[A[i]] += 1

    
    for i in range(k):
        if i > 0:
            C[i] = C[i] + C[i - 1]

    for j in range(len(B) - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1


if __name__ == '__main__':
    main()

Solution (Python):






from sys import stdin,setrecursionlimit





setrecursionlimit(10**6)
input=stdin.readline

def Counting_sort(array,max_value):
    cnt_element=[0]*(max_value+1)
    ans_array=[]
    for i in array: cnt_element[i]+=1
    for i,j in enumerate(cnt_element): ans_array+=[i]*j
    return ans_array

n=int(input().rstrip())
a=[int(i) for i in input().split()]
ans=Counting_sort(a,max(a))
print(*ans)

Solution (Python):
"""
7
2 5 1 3 2 3 0
"""

def counting_sort(A, n, max):
    B = [0] * n
    C = [0] * (max + 1)
    
    

    for j in range(n):
        C[A[j]] += 1
    

    for i in range(1, max+1):
        
        C[i] = C[i] + C[i-1]
    
    
    

    for j in reversed(range(n)):
        
        
        
        
        B[C[A[j]]-1] = A[j]
        
        C[A[j]] -= 1

    B_str = []
    for b in B:
        B_str.append(str(b))
    print(" ".join(B_str))
    

if __name__=="__main__":
    n = int(input())
    A = list(map(int, input().split()))
    max = max(A)
    counting_sort(A, n, max)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

def bucketsort(A, B):
    C = [0] * (max(A) + 1)
    
    for i in A:
        C[i] += 1
    
    for i in range(1, max(A) + 1):
        C[i] += C[i - 1]
    
    for i in (reversed(A)):
        B[C[i] - 1] = i
        C[i] -= 1
    return B

B = [0] * len(A)
ans = bucketsort(A, B)
ans = [str(i) for i in ans]
print(' '.join(ans))

Solution (Python):
def countingSort(A, B, k, n):
	C = [0] * (k + 1)

	
	for j in range(n):
		C[A[j]] += 1
	
	
	for i in range(1, k + 1):
		C[i] = C[i] + C[i - 1]

	for j in range(n - 1, -1, -1):
		B[C[A[j]] - 1] = A[j]
		C[A[j]] -= 1


if __name__ == "__main__":
	n = int(input())
	A = list(map(int, input().split()))
	k = max(A)
	B = [0] * n
	countingSort(A, B, k, n)
	print(' '.join(map(str, B)))

Solution (Python):






n = int(input())
A = list(map(int, input().split()))
A.sort()

print(*A)

Solution (Python):
import sys
from sys import stdin
input = stdin.readline

n = int(input())
NUM_LIST = list(map(int, input().split()))
result = [0]*n

count = [0]*10001 

for num in NUM_LIST:
    count[num] += 1

for i in range(1, len(count)):
    count[i] += count[i-1]

for num in NUM_LIST:
    result[count[num]-1] = num
    count[num] -= 1

print(" ".join(list(map(str, result))))

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]

def CountingSort(A,k):
    C = [0 for x in range(k+1)]
    B = [0 for x in range(N)]

    for j in range(N):
        C[A[j]] += 1

    for i in range(k):
        C[i+1] += C[i]

    for j in reversed(range(N)):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1

    return B

B = CountingSort(A,max(A))

for i in range(N):
    if i != N-1:
        print(B[i], end=" ")
    elif i == N-1:
        print(B[N-1])

Solution (Python):

import sys
def counting_sort(A, B):
    k = max(A) + 1
    C = [0] * k  

    for i in range(len(A)):
        C[A[i]] += 1

    for j in range(1, k):
        C[j] = C[j - 1] + C[j]

    for i in range(len(A) - 1, -1, -1):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1


n = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
B = [0] * n

counting_sort(A, B)
print(' '.join(map(str, B)))

Solution (Python):
def CountingSort(A, B, n, k):
    C = [0]*(k+1)
    
    
    for j in range(n):
        C[A[j]]+=1
        
    
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
        
    for j in range(n):
        B[C[A[j]]-1] = A[j]
        C[A[j]]-=1

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().split()))
    B = A[:]
    k = max(A)
    CountingSort(A, B, n, k)
    print(' '.join(map(str, B)))

Solution (Python):
import sys
input = sys.stdin.readline

def countingSort(A, k):
    n = len(A)
    C = [0] * (k+1)
    for i in A:
        C[i] += 1
    for i in range(1, k+1):
        C[i] += C[i-1]
    B = [0] * n
    A.reverse
    for i in A:
        B[C[i]-1] = i
        C[i] -= 1
    return B
def main():
    n = int(input())
    A = list(map(int, input(). split()))
    B = countingSort(A, 10000)
    print(' '.join(list(map(str, B))))

if __name__ == '__main__': main()

Solution (Python):

maxx = 2000001;
maxnum = 10010;

n=int(input())
A=[int(x) for x in input().split()]  
A.insert(0,0) 
B=[-1 for x in range(n)]
C=[0 for x in range(maxnum)]



for a in A[1:]:
    C[a]+=1
for i in range(1,maxnum): 
    C[i]+=C[i - 1]
    
for j in range(1,n+1):
    B[C[A[j]]-1]=A[j]
    C[A[j]]-=1

lens=len(B)    
for i in range(0,lens-1):
    print(B[i],end=' ')
print(B[lens-1])

Solution (Python):
def counting_sort(A, k):
    B = [0 for _ in range(len(A))]
    C = [0 for _ in range(k)]
    for i in range(len(A)):
        C[A[i]] += 1

    for i in range(1, k):
        C[i] = C[i] + C[i-1]

    for i in range(len(A)-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] = C[A[i]] - 1
    
    return B
    
n = int(input())
A = list(map(int, input().split()))
k = max(A) + 1
B = counting_sort(A, k)
print(*B)

Solution (Python):
k = 10000


def main():
    n = int(input())
    A = list(map(int, input().split(' ')))
    B = [-1] * n

    counting_sort(A, B, n, k)
    print(' '.join(map(str, B)))


def counting_sort(A, B, n, k):
    C = [0] * k

    for i in range(n):
        C[A[i]] += 1
    
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for i in range(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(n)]

def countingsort(A, B, k):
    """リストAの0からk以下の各要素の数（計n）をカウントするリストCを作成（初期値0）"""
    C = [0 for i in range(k)]
    """リストAの各要素の数をリストCに記録（Cのインデックス=Aの値）"""
    for i in range(n):
        C[A[i]] += 1
    """C[i]にi以下の値の出現数を記録"""
    for i in range(1, k):
        C[i] += C[i-1]
    """リストBに値をソートしつつ格納"""
    for i in reversed(range(n)):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1

countingsort(A, B, max(A)+1)
print(*B)

Solution (Python):
import sys

def CountingSort(A,B,k,n):

	C = [0] * k

	for i in range(n):
		C[A[i]] += 1

	for i in range(1,k):
		C[i] = C[i] + C[i-1]

	for i in range(n-1,-1,-1):
		B[C[A[i]]-1] = A[i]
		C[A[i]] -= 1


def test():

	n = int(sys.stdin.readline())
	A = list(map(int,sys.stdin.readline().split()))

	B = [0] * n

	max = 0
	for i in range(n):
		if max < A[i]:
			max = A[i]

	CountingSort(A,B,max+1,n)
	
	for i in range(n-1):
		print(f"{B[i]} ",end='')
	print(B[n-1])


if __name__ == "__main__":
	test()

Solution (Python):
def counting_sort(inArr, outArr, k):
    cntArr = [0] * (k + 1)
    for i in range(len(inArr)):
        cntArr[inArr[i]] += 1

    cntArr[0] -= 1
    for i in range(1, k+1):
        cntArr[i] += cntArr[i - 1]

    for i in range(len(inArr) - 1, -1, -1):
        outArr[cntArr[inArr[i]]] = inArr[i]
        cntArr[inArr[i]] -= 1

n = int(input())
num_list = [int(s) for s in input().split()]

sorted_list = [0] * n
counting_sort(num_list, sorted_list, 10000)

print(*sorted_list)