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



Sample input:
7
2 5 1 3 2 3 0


Sample output:
0 1 2 2 3 3 5

Submission status: Accepted

Solution code:
k = 10000+1
def counting_sort(A, B, k):
    C = [0] * k
    n = len(A)-1
    for j in range(n):
        C[A[j+1]] += 1
    for i in range(1, k):
        C[i] += C[i-1]
    for j in range(n, 0, -1):
        # print('j = {0}'.format(j))
        # print('A[{0}] = {1}'.format(j, A[j]))
        # print('C[A[j]] = {0}'.format(C[A[j]]))
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1


if __name__ == '__main__':
    # ??????????????\???
    # array_size = 7
    # A = [999, 2, 5, 1, 3, 2, 3, 0]
    array_size = int(input())
    A = [int(x) for x in input().split(' ')]
    A.insert(0, 9999999)
    B = A[:]

    # ????????????????????????
    counting_sort(A, B, k)

    # ???????????????
    # print('A = {0}'.format(' '.join(map(str, A[1:]))))
    print('{0}'.format(' '.join(map(str, B[1:]))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def CountingSort(array,maxval):
    m=maxval+1
    count=[0]*m
    for a in array:
        count[a]+=1
    i=0
    for a in range(m):
        for c in range(count[a]):
            array[i]=a
            i+=1
    return array

if __name__ == '__main__':
    maxval = 2000000
    n = int(input())
    a = [int(i) for i in input().split()]
    print(" ".join([str(s) for s in CountingSort(a,max(a))]))

Submission status: Accepted

Solution code:

def CountingSort(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 j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

n = int(input())
A = [int(a) for a in input().split()]
B = [0] * n

CountingSort(A, B, 10000)

print(*B)

Submission status: Accepted

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



if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    sorted_A = CountingSort(A, int(3E6))
    print(' '.join([str(a) for a in sorted_A[1:len(A) + 1]]))

Submission status: Accepted

Solution code:
def CountingSort(A, B, k):
    C = [0]*(k+2)
    for i in range(n):
        C[A[i]] += 1
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    x = list(range(n))
    x.reverse()
    for i in x:
        B[C[A[i]]] = A[i]
        C[A[i]] -= 1
    return B
n = int(input())
A = list(map(int,input().split()))
B = [0]*(n+1)
k = max(A)
res = CountingSort(A, B, k)
print(*res[1:])

Submission status: Accepted

Solution code:
def countingSort(A,B):
    k = max(A)
    C = [0]*(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

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

Submission status: Accepted

Solution code:
def countint_sort(A, k):
  B = [0] * (len(A))
  C = [0] * (k + 1)
  for j in range(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)):
    ib = C[A[j]] - 1
    B[ib] = A[j]
    C[A[j]] -= 1
  return B

n = int(input())
A = list(map(int, input().split()))
print(" ".join(map(str, countint_sort(A, max(A)))))

Submission status: Accepted

Solution code:
def countingSort(a,n):
    count = [0]*(max(a)+1)
    for k in a:
      count[k] += 1
    for i in range(len(count)-1):
      count[i+1] += count[i]
    
    sorted_a = [0]*n

    for k in a[::-1]:
        sorted_a[count[k]-1] = k
        count[k] -= 1
    return sorted_a

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

Submission status: Accepted

Solution code:
def CountingSort(A, B, k):
    C = [0 for i in range(k+1)]
    n = len(A)
    #C[i]???i???????????°????¨??????????
    for j in range(n):
        C[A[j]] += 1

    #C[i]???i??\????????°???????????°????¨??????????
    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]
        #print(C[A[j]])
        C[A[j]] -= 1


n = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(n)]
CountingSort(A, B, max(A))
print(*B)

Submission status: Accepted

Solution code:
def CountingSort(A, n, B, k):
  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]

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

def main():
  n = int(input())
  A = list(map(int, input().split()))
  B = [0]*n
  CountingSort(A, n, B, max(A))
  print(" ".join(map(str, B)))

if __name__ == "__main__":
  main()

Submission status: Accepted

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

n = int(input())
A = list(map(int, input().split()))
k = max(A)
B =CountingSort(A, k)
print(" ".join(map(str,B)))

Submission status: Accepted

Solution code:
def counting_sort(array, maxval):
    m = maxval + 1000
    count = [0] * (m)
    for a in array:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            array[i] = a
            i += 1
    return array
 
if __name__ == '__main__':
    N = int(input())
    l = list(map(int, input().split()))
    a = 0
    li = counting_sort(l, N)
    for a in range(N-1):
        print(li[a], end=" ") 
    print(li[N-1])

Submission status: Accepted

Solution code:
def counting_sort(array, maxval):
    m = maxval+100
    count = [0] * (m)
    for a in array:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            array[i] = a
            i += 1
    return array
 
if __name__ == '__main__':
    N = int(input())
    l = list(map(int, input().split()))
    a = 0
    li = counting_sort(l, N)
    for a in range(N-1):
        print(li[a], end=" ") 
    print(li[N-1])

Submission status: Accepted

Solution code:
# coding=utf-8

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

    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]:
        B[C[a]-1] = a
        C[a] -= 1

    return B


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

B = counting_sort(A, B, k)
print(*B)

Submission status: Accepted

Solution code:
def main():
    n = input()
    A = map(int,raw_input().split())
    B = [0]*n
    k = max(A)
    CountingSort(A,B,k,n)

    for i in range(n-1):
        print B[i],
    print B[-1]


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-1]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
B = [0] * n
k = max(A)
C = [0] * (k + 1)
for i in range(0, n):
    C[A[i]] += 1
for i in range(1, k + 1):
    C[i] += C[i - 1]
for i in range(n - 1, -1, -1):
    C[A[i]] -= 1
    B[C[A[i]]] = A[i]
print(*B)

Submission status: Accepted

Solution code:
def CountingSort(A, B, k):
    C = [0 for i in range(k+2)]
    
    for j in range(n):
        C[A[j]] += 1
        
    for i in range(k+1):
        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())
    D = list(map(int, input().split()))
    l = max(D)
    E = D[:]
    CountingSort(D, E, l)
    print(" ".join(map(str, E)))

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
	C = [0 for i in range(k+1)]
	for a in A:
		C[a] += 1
	for i in range(1,k+1):
		C[i] += C[i-1]
	for a in A:
		B[C[a]-1] = a
		C[a] -= 1


if __name__ == '__main__':
	n = int(input())
	A = [int(s) for s in input().split()]
	B = A[:]
	counting_sort(A, B, max(A))
	print(*B)

Submission status: Accepted

Solution code:
def CountingSort(A, B, k, n):
    C = [0 for i in range(k)]   #  for i = 0 to k { C[i] = 0 }

    # /* C[i] ??? i ???????????°????¨?????????? */
    for j in range(n):
        C[A[j]] += 1
#        print("j:{} Aj:{} C[Aj]:{}".format(j,A[j], C[A[j]]))

    # /* C[i] ??? i ??\????????°???????????°????¨??????????*/
    for i in range(k):
#        print("\ti:{} Ci:{} Ci-1:{}".format(i,C[i], C[i-1]))
        C[i] = C[i] + C[i-1]

    for j in reversed(range(n)):
#        print("j:{} Aj:{} C[Aj]:{} k:{}".format(j,A[j], C[A[j]],k))
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
    max = 0
    for i in range(num):
        if max < A[i]:
            max = A[i]
    if max < num:
        max = num
    max += 2
    B = [0 for i in range(num + 2)]
    CountingSort(A, B, max, num)
    print(" ".join(map(str,B[1:num+1])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())

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

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

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


b = [0 for i in range(n)]
k = max(a)
CountingSort(a, b, k)
print ' '.join(map(str, b))

Submission status: Accepted

Solution code:
def CountingSort(A, B, k):
    C = [0] * (k + 1)
    for a in A: C[a] += 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=[int(i) for i in input().split()]
B = [None] * n
CountingSort(A, B, max(A))
print(' '.join(map(str,B)))

Submission status: Accepted

Solution code:
def sort(a, k):
    c = [0]*k
    for x in a:
        c[x] += 1
    b = []
    for i in range(len(c)):
        y = c[i]
        for _ in range(y):
            b.append(i)
    return b

n = int(raw_input())
a = map(int, raw_input().split(' '))
b = sort(a, 10001)

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

Submission status: Accepted

Solution code:
def countingsort(A,n):
    k=max(A)
    
    B=[0 for i in range(n)]
    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]+C[i-1]
    
    for j in range(n-1,-1,-1):
        B[C[A[j]]-1]=A[j]
        C[A[j]]-=1
    
    print(*B)
    
n=int(input())
A=list(map(int,input().split()))

countingsort(A,n)

Submission status: Accepted

Solution code:
def CountingSort(A):
    B = [0]*len(A)
    maxnumber = 0
    for n in range(len(A)):
        if maxnumber < A[n]:
            maxnumber = A[n]
    C = [0]*(maxnumber + 1)

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

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

    return B


if __name__ == '__main__':
    cnt = input()
    A = list(map(int,input().split()))
    Ans = list(map(str,CountingSort(A)))
    print(" ".join(Ans))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = []
C = [0] * 10001
for x in A:
    C[x] += 1
for i, k in enumerate(C):
    B += [str(i)] * k
print(" ".join(B))

Submission status: Accepted

Solution code:
def counting(A, **k):
    n = len(A)
    k = max(A)
    B = [0]*(n)
    C = [0]*(k+1)
    
    for j in A:
        C[j] += 1
    for i in range(k):
        C[i+1] += C[i]
    for j in A[::-1]:
        B[C[j]-1] = j
        C[j] -= 1
    
    return B

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    B = counting(A)
    print(" ".join(map(str, B)))

Submission status: Accepted

Solution code:
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 reversed(range(n)):
    b[c[a[j]] - 1] = a[j]
    c[a[j]] -= 1

print(*b)

Submission status: Accepted

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

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

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

    for i in range(len(C)):
        while True:
            if C[i] != 0:
                B.append(i)
                C[i] -= 1
            else:
                break
    return B

result = counting_sort(a,max(a))
print(*result)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-


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

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

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

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


if __name__ == "__main__":
    n = int(input())
    lst = [int(val) for val in input().split()]
    lst.insert(0, 0)
    result = [0] * (n + 1)
    k = max(lst)
    countingSort(lst, result, k, n)
    result.pop(0)
    print(" ".join([str(val) for val in result]))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-


def countingSort(lst, n):
    cnt_lst = [0] * (max(lst)+1)

    for i in range(0, n):
        cnt_lst[lst[i]] += 1

    i = 0
    result = []
    for j, cnt in enumerate(cnt_lst):
        for _ in range(0, cnt):
            result.append(j)
    return result


if __name__ == "__main__":
    n = int(input())
    lst = [int(val) for val in input().split()]
    result = countingSort(lst, n)
    print(" ".join([str(val) for val in result]))

Submission status: Accepted

Solution code:
def countingSort(A):
    minA = min(A)
    maxA = max(A)
    C = [0]*10001

    for x in A:
        C[x] += 1
    for x in range(1,10001):
        C[x] += C[x-1]
    B = [0]*(len(A)+1)

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

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

    B = countingSort(A)
    print(*B[1:])

Submission status: Accepted

Solution code:
def CountingSort(A, B, k):
	C = []
	for i in xrange(k+1):
		C.append(0)
	for j in xrange(n):
		C[A[j]] += 1
	#print C
	#for i in xrange(1,k+1):
	#	C[i] = C[i] + C[i-1]
	#print C
	for j in xrange(len(C)):
		for k in xrange(C[j]):
			B.append(j)
	return B

n = int(raw_input())
A = map(int, raw_input().split())
k = max(A)

B = []
#for i in range(len(A)):
#	B.append(0)

B = CountingSort(A, B, k)
#print B

for i in range(len(B)):
	if i != len(B)-1:
		print(B[i]),
print B[-1]

Submission status: Accepted

Solution code:
# coding=utf-8
def counting_sort(input_list: list, upper: int) -> list:
    number = len(input_list)

    # noinspection PyUnusedLocal
    b = [0 for i in range(number+1)]
    # noinspection PyUnusedLocal
    counter_list = [0 for i in range(upper+1)]

    for j in input_list:
        counter_list[j] += 1

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

    for j in range(number):
        b[counter_list[input_list[j]]] = input_list[j]
        counter_list[input_list[j]] -= 1

    return b


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    k = 2000000
    a = counting_sort(a, k)
    a.pop(0)

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

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    C = [0 for _ in xrange(int(k+1))]
    for i in xrange(n):
        C[A[i]] += 1
    
    for i in xrange(k):
        C[i] = C[i] + C[i-1]
    
    for i in xrange(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1


n = int(raw_input())
A = map(int, raw_input().split())
B = [0 for _ in xrange(n)]

counting_sort(A, B, 10000)

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

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    C = [0 for _ in xrange(k+1)]
    for a in A:
        C[a] += 1

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

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


n = int(raw_input())
A = map(int, raw_input().split())
B = [0 for _ in xrange(n)]

counting_sort(A, B, 10000)

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

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    C = [0 for _ in xrange(k+1)]
    for a in A:
        C[a] += 1

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

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


n = int(raw_input())
A = map(int, raw_input().split())
B = [0 for _ in xrange(n)]

counting_sort(A, B, 10000)

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

Submission status: Accepted

Solution code:
def main():
    _ = input()
    li = [int(x) for x in input().split(' ')]
    out = countingSort(li, max(li))
    print(*out)


def countingSort(A, k):
    B = []
    for _ in range(len(A)):
        B.append(0)

    C = []
    for _ in range(k + 1):
        C.append(0)

    for a in A:
        C[a] += 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

    return B


main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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

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


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))

Submission status: Accepted

Solution code:
def cSort(hoge, k):
    sorted_list = [0] * (len(hoge)-1)
    sorted_list.insert(0, None)
    count_list = [0] * (k+1)
    for i in range(1, len(hoge)):
        count_list[hoge[i]] += 1
    
    for i in range(1, len(count_list)):
        count_list[i] = count_list[i] + count_list[i-1]
    
    for j in range(1, len(hoge))[::-1]:
        sorted_list[count_list[hoge[j]]] = hoge[j]
        count_list[hoge[j]] -= 1
    
    sorted_list.remove(None)
    return sorted_list
    
if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    max_num = max(hoge)
    hoge.insert(0, None)
    print (' '.join([str(x) for x in cSort(hoge, max_num)]))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
m=max(A)+1
B=A[:]
C=[0]*m
for a in A:C[a]+=1
for i in range(1,m):C[i]+=C[i-1]
for j in A[::-1]:B[C[j]-1]=j;C[j]-=1
print(*B)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
m=10001
B=A[:]
C=[0]*m
for a in A:C[a]+=1
for i in range(1,m):C[i]+=C[i-1]
for j in A[::-1]:B[C[j]-1]=j;C[j]-=1
print(*B)

Submission status: Accepted

Solution code:
input()
A=list(map(int,input().split()))
B=[]
C=[0]*(max(A)+1)
for a in A:C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Submission status: Accepted

Solution code:
input()
A=list(map(int,input().split()))
B=[]
C=[0]*10001
for a in A:C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Submission status: Accepted

Solution code:
input()
B=[]
C=[0]*10001
for a in map(int,input().split()):C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Submission status: Accepted

Solution code:
input()
B,C,i=[],[0]*10001,0
for a in map(int,input().split()):C[a]+=1
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Submission status: Accepted

Solution code:
input()
C=[0]*10001
for a in map(int,input().split()):C[a]+=1
B=[];i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Submission status: Accepted

Solution code:
def s():
 input()
 C=[0]*10001
 for a in map(int,input().split()):C[a]+=1
 B=[];i=0
 for k in C:B+=[str(i)]*k;i+=1
 print(' '.join(B))
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
def counting_sort(A, k):
    C = [0 for i in range(k)]
# C[i]にiの出現数を記録する
    for l in A:
        C[l] += 1
# C[i]にi以下の数の出現数を記録する
    for i in range(1, k):
        C[i] = C[i] + C[i-1]

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

    return B

input()
a = list(map(int, input().split()))
b = counting_sort(a, 10000)
print(*b)

Submission status: Accepted

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


def countingsort(a, k):
    c = [0 for i in range(k+1)]
    b = [0 for i 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, 10000)
print(*b)

Submission status: Accepted

Solution code:
MAXVAL = 10000


def counting_sort(li):
    """Sort li by counting the number of occurrences of each
    element in li.
    All the elements in li are supposed to be 0..10000.

    >>> counting_sort([2, 5, 1, 3, 2, 3, 0])
    [0, 1, 2, 2, 3, 3, 5]
    """
    counter = [0] * (MAXVAL+1)

    for e in li:
        counter[e] += 1

    for i in range(1, MAXVAL+1):
        counter[i] += counter[i-1]

    result = [None] * len(li)
    for e in reversed(li):
        counter[e] -= 1
        result[counter[e]] = e

    return result


def run():
    _ = int(input())  # flake8: noqa
    xs = [int(i) for i in input().split()]

    print(" ".join([str(i) for i in counting_sort(xs)]))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
def countingSort(A):
    k = max(A)
    B = [0]
    B.extend(A)
    C = []
    n = len(A)
    for i in range(k + 1):
        C.append(0)

    for j in range(0, n):
        C[A[j]] += 1
    
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    
    for j in range(n - 1, -1, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    print(' '.join(list(map(str, B[1:]))))
    return
N = int(input())
a = list(map(int, input().split()))
countingSort(a)

Submission status: Accepted

Solution code:
def countingsort(a, b, k):
    c = [0 for i in range(k)]
    for i in range(len(a)):
        c[a[i]] += 1
    for i in range(1,k):
        c[i] += c[i - 1]
    for i in range(len(a))[::-1]:
        b[c[a[i]] - 1] = a[i]
        c[a[i]] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(n)]
countingsort(a, b, max(a) + 1)
print(" ".join(map(str, b)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 22:47:34 2018
ALDS1_6_A
@author: maezawa
"""

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n+1)]

def counting_sort(a, b, k):
    c = [0 for _ in range(k+1)]
    
    for aj in a:
        c[aj] += 1
    
    for i in range(1, k+1):
        c[i] += c[i-1]
        
    for j in reversed(range(n)):
        #print(j, a[j], c[a[j]])
        b[c[a[j]]] = a[j]
        c[a[j]] -= 1
    
k = max(a)    
counting_sort(a, b, k)
print(b[1],end='')
for i in range(2,n+1):
    print(' {}'.format(b[i]), end='')
print()

Submission status: Accepted

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

    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, -1, -1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1

    return B

n = int(input())
A = list(map(int, input().split(' ')))
B = counting_sort(A, 10000)
print(' '.join(map(str, B)))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Aizu Online Judge Algorithm and Data Structure, counting sort

import sys

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

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

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


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

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    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] + 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()))
    B=[-1 for i in range(n)]
    counting_sort(A,B,max(A)+1)
    print(*B)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split())) # 入力配列
B = [0 for i in range(n)] # 出力配列
C = [0 for i in range(10001)] # カウンタ配列

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

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

for a in reversed(A):
    B[C[a] - 1] = a
    C[a] -= 1

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

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
k = max(s)
c = [0 for i in range(k+1)]
def counting_sort(a, k):
    global c
    b = [0 for i in range(len(a)+1)]
    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 reversed(range(n)):
        b[c[a[i]]] = a[i]
        c[a[i]] -= 1
    return b
res = counting_sort(s, k)[1:n+1]
print(*res)
#print(c)

Submission status: Accepted

Solution code:
def counting_sort(ary, bry, k):
    cry = [0 for i in range(k)]

    for j in range(n):
        cry[ary[j]] += 1

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

    for j in range(n - 1, -1, -1):
        bry[cry[ary[j]] - 1] = ary[j]
        cry[ary[j]] -= 1

if __name__ == '__main__':
    n = int(input())
    ary = [int(_) for _ in input().split()]
    bry = [0 for i in range(n)]
    counting_sort(ary, bry, 10 ** 5)
    print(*bry)

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    len_A = len(A)

    C = [0 for _ 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] + C[i - 1]

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


n = int(input())
input_list = list(map(int, input().split(' ')))

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

counting_sort(input_list, B, max(input_list) + 1)

print(*B)

Submission status: Accepted

Solution code:
def CountingSort(n, input_line, max_num):
    max_num += 1
    count_list = [0 for i in range(max_num)]
    output_line = [0 for i in range(n)]
    for i in range(n):
        count_list[input_line[i]] += 1
    for i in range(1,max_num):
        count_list[i] = count_list[i] + count_list[i-1]
    for i in range(n-1,-1, -1):
        output_line[count_list[input_line[i]]-1] = str(input_line[i])
        count_list[input_line[i]] -= 1
    return output_line

n = int(input())
input_line = [int(i) for i in input().split()]
max_num = max(input_line)
output_line = CountingSort(n, input_line, max_num)
print(' '.join(output_line))

Submission status: Accepted

Solution code:
def counting_sort(a, b, k):
    c = [0 for _ in range(k+1)]
    n = len(a)

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

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

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


def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x, end=" ")
    print(a[-1])


n = int(input())
a = [int(x) for x in input().split()]
b = a.copy()
k = max(a)

counting_sort(a, b, k)

print_list_split_whitespace(b)

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    C = {i: 0 for i in range(k+1)}

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

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

    for j in A[::-1]:
        B[C[j]-1] = j
        C[j] -= 1

def print_list(B):
    for i, j in enumerate(B):
        if i == n - 1:
            print(j)
        else:
            print(j, end=" ")

n = int(input())
A = [int(e) for e in input().split()]
B = [0 for i in range(n)]
counting_sort(A, B, max(A))
print_list(B)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    numbers = list(map(int, input().split()))
    counters = [0] * 10001
    sortedNumbers = [0] * n
    for number in numbers:
        counters[number] += 1

    for i in range(1, 10001, 1):
        counters[i] += counters[i - 1]

    for i in range(n - 1, -1, -1):
        sortedNumbers[counters[numbers[i]] - 1] = numbers[i]
        counters[numbers[i]] -= 1

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

if __name__ == '__main__':
    main()