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:
def CountingSort(A, B, n, k):
    C = [0]*(k+1)
    
    # 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):
        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)))

Submission status: Accepted

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

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:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

    return B

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

    B = countingSort(A,n,10000)

    print(*B)
             
if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(*B)

Submission status: Accepted

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

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

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

    return B


k = 10 ** 4 + 1
n = int(input())
A = list(map(int, input().split()))
B = counting_sort(A, n, k)
print(*B[:n])

Submission status: Accepted

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

maxA = max(A) + 1
B = [0] * n
C = [0] * maxA

for a in A:
    C[a] += 1
    
j = 0
for i in range(maxA):
    for k in range(C[i]):
        B[j] = i
        j += 1
        
print(" ".join(map(str, B)))

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(i) for i in input().split()]
B = [[] for i in range(n)]
CountingSort(A,B,max(A))
print(" ".join(map(str,B)))

Submission status: Accepted

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

    B = [0] * n
    C = [0] * 10001

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

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

    for i in A:
        B[C[i] - 1] = i
        C[i] -= 1
    
    print(' '.join(map(str, B)))

Submission status: Accepted

Solution code:
from typing import List


def counting_sort(elements: List[int]) -> List[int]:
    C = [0] * (max(elements) + 1)
    B = [0] * (len(elements) + 1)

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


if __name__ == "__main__":
    _ = int(input())
    elements = list(map(lambda x: int(x), input().split()))

    sorted_elements = counting_sort(elements)

    print(" ".join([str(elem) for elem in sorted_elements]))

Submission status: Accepted

Solution code:
MAXV = 10000

if __name__ == '__main__':
    n = int(raw_input())

    # input, 1-origin, range [1, n]
    A = [0] + map(int, raw_input().split())

    # output, 1-origin
    B = A[:]

    # counter, 0-origin: range [0, MAXV]
    C = [0 for i in range(MAXV + 1)]

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

    # let the number of elements that are <= x be f(x)
    # then f(x) = x + f(x-1)
    for i in range(1, MAXV + 1):
        C[i] += C[i - 1]

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

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

Submission status: Accepted

Solution code:
class Counting_Sort():
    def __init__(self, N, input_number_list):
        self.N = N
        self.number_list = input_number_list
        self.print_number_list = list()

    def counting_sort(self):
        counting_list = list()
        for i in range(10001):
            counting_list.append(0)
        for i in range(self.N):
            counting_list[self.number_list[i]] += 1
            self.print_number_list.append(0)
        for i in range(1,10001):
            counting_list[i] += counting_list[i-1]
        for i in range(self.N-1,-1,-1):
            self.print_number_list[counting_list[self.number_list[i]]-1] = self.number_list[i]
            counting_list[self.number_list[i]] -= 1

def print_number_list(number_list, N):
    for i in range(N):
        if i != N - 1:
            print(number_list[i],end=' ')
        else:
            print(number_list[i])

def main():
    N = int(input())
    input_number_list = [int(i) for i in input().split()]
    sort = Counting_Sort(N,input_number_list)
    sort.counting_sort()
    print_number_list(sort.print_number_list,N)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

n = int(input())
A = list(map(int,input().split()))
B = countingSort(A,max(A))
print(*B)

Submission status: Accepted

Solution code:
from collections import deque


def bucket_sort_deque(a):
    # Dequeは高速な双方向リスト，Pythonでリストを使うときにはDeque
    m = 10**5
    b = [deque() for _ in range(m)]
    for i in a:
        b[i].append(i)
    i = 0
    for d in b:
        while len(d) != 0:
            a[i] = d.pop()
            i += 1
n = int(input())
l = list(map(int,input().split()))
bucket_sort_deque(l)
for i in l[:n-1]:
    print(i,end = ' ')
print(l[-1])

Submission status: Accepted

Solution code:
n=int(input())
L=input().split( )
A=[int(L[i]) for i in range(n)]
k=10002
C=[]
for i in range(k):
    C += [0]
#print(C[:20])

for j  in range(n):
     C[A[j]]+=1
#print(C[:20])
B=[]

for j in range(k):
    for l in range(C[j]):
        B.append(j)

print(*B)

Submission status: Accepted

Solution code:
def counting_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 = input()
arr = list(map(int, input().split()))
print(*counting_sort(arr))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    k = 10000
    B = [None] * n
    C = [0] * k
    for i in range(n):
        C[A[i]] += 1

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

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

    print(*B)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


data = [0]*(n)
data = CountingSort(A,data,max(A))

print(*data)

Submission status: Accepted

Solution code:
A_NUM_MAX = 10001


def counting_sort(A):
    B = [None] * len(A)
    C = [0] * A_NUM_MAX

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

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

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

    return B


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

B = counting_sort(A)

print(*B)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(lambda x:int(x),input().split()))
b=[0]*n
c=[0]*10001
for j in range(n):
    c[a[j]]+=1

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

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

for j in range(n-1):
    print(b[j],end=" ")
print(b[n-1])

Submission status: Accepted

Solution code:
def counting_sort(a, b, k):
    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-1] # 積み重ねたもの
    

    for i in range(len(a))[::1]:
        b[c[a[i]] -1] = a[i]
        c[a[i]] -= 1
    
    return b



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

    B = [0 for _ in range(len(A))]

    b = counting_sort(A, B, max(A)+1)

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().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, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

B = [0] * n
CountingSort(A, B, 10000)

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())

    A = [None] + list(map(int, input().split()))
    B = [None]*(n+1)

    C = [0]*10001

    k = 10000

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

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


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

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

Submission status: Accepted

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

def countingSort(A, k):
    B = [0 for i in range(len(A))]
    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 reversed(A):
        B[C[a]-1] = a
        C[a] -= 1
    return B

print(*countingSort(A, 10000))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import accumulate


def counting_sort(A, k):
    counter = Counter(A)
    B = [0]*(len(A)+1)
    C = list(accumulate((counter[i] for i in range(k+1))))
    for n in A[::-1]:
        B[C[n]] = n
        C[n] -= 1

    return B[1:]


if __name__ == "__main__":
    input()
    a = list(map(int, input().split()))
    print(*counting_sort(a, 10000))

Submission status: Accepted

Solution code:
from sys import stdin

def counting_sort(nums, k):
    out = [0] * len(nums)
    cnts = [0] * (k + 1)
    offsets = [0] * (k + 1)
    for n in nums:
        cnts[n] = cnts[n] + 1
    
    for i in range(len(cnts)):
        if i > 0:
            offsets[i] = offsets[i - 1] + cnts[i - 1]
    
    for n in nums:
        out[offsets[n]] = n
        offsets[n] = offsets[n] + 1
    return out

def main():
    lines = stdin.readlines()
    nums = list(map(int, lines[1].split(' ')))
    n_max = max(nums)
    sorted_nums = counting_sort(nums, n_max)
    print(' '.join(map(str, sorted_nums)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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] + C[i-1]
        # 累積和
    for j in range(n-1, -1, -1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
    return B


k = max(A)
B = [0] * n
B = CountingSort(A, B, k)
print(*B)

Submission status: Accepted

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

def countingSort(A,N):
    C = [0]*(max(A)+2)

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

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


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

    return B

ans = countingSort(nums,n)
print(' '.join(map(str,ans)))

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] + C[i-1]
#     print(C)
    
    for j in range(n-1, -1, -1):
        B[ (C[A[j]]-1) ] = A[j]
        C[A[j]] -= 1

n = int(input())
A = [int(num) for num in input().split()] 
B = [0] * n
k = max(A)
CountingSort(A,B,k)
print(" ".join(map(str,B)))

Submission status: Accepted

Solution code:
def CountingSort(arr_size, in_arr, out_arr, maximum):

    c = [0] * (maximum + 1)
    for j in range(arr_size):
        c[in_arr[j]] += 1
    for i in range(1, maximum + 1):
        c[i] += c[i - 1]
    for j in range(arr_size - 1, -1, -1):
        out_arr[c[in_arr[j]]] = in_arr[j]
        c[in_arr[j]] -= 1

n = int(input())
A = list(map(int, input().split()))
B = [0] * (n + 1)
CountingSort(arr_size=n, in_arr=A, out_arr=B, maximum=max(A))
print(' '.join(map(str, B[1:])))

Submission status: Accepted

Solution code:
k = 10000
c = [0] * (k + 1)


def countingSort(a, b):
    global k
    n = len(a) - 1
    for i in range(k + 1):
        c[i] = 0
    for j in range(n):
        c[a[j + 1]] += 1

    #print(c)

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

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


n = int(input())
*a, = map(int, input().split())
a.insert(0, 0)
b = [0] * (n + 1)

countingSort(a, b)
b.pop(0)
print(" ".join([str(v) for v in b]))

Submission status: Accepted

Solution code:
# coding: utf-8

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

n = int(input().rstrip())
A = [int(i) for i in input().rstrip().split()]
B = [0 for i in range(n)]
countingSort(A, B, 10000)
print(" ".join([str(i) for i in B]))

Submission status: Accepted

Solution code:
def Countingsort(A, k, n):
    index = 0
    Out = []
    Count = [0 for i in range(k + 1)]
    for i in range(n):
        Count[A[i]] += 1
    while index <= k:
        if Count[index] > 0:
            Out.append(index)
            Count[index] -= 1
        else:
            index += 1
    print(*Out)

max = -1
n = int(input())
A = list(map(int,input().split()))
for i in range(n):
    if A[i] > max:
        max = A[i]
Countingsort(A, max, n)

Submission status: Accepted

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

"""
バケットソート
・累積和
"""

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = LIST()

def CountingSort(A, k):
    C = [0] * (k+1)
    B = [0] * N
    # C[i] に i の出現数を記録する
    for i in range(N):
        C[A[i]] += 1
    # C[i] に i 以下の数の出現数を記録する
    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つ場所を確定させたので、1減らしておく
        C[A[i]] -= 1
    return B

B = CountingSort(A, max(A))
print(*B)

Submission status: Accepted

Solution code:
from sys import stdin

def countingSorted(A):
    VALUE_MAX = max(A)
    B = [0] * (len(A)+1)
    C = [0] * (VALUE_MAX+1)

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

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

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

    return B[1:]

n = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
print(*countingSorted(A))

Submission status: Accepted

Solution code:
from typing import List


def counting_sort(target: List[int], max_val: int) -> List[int]:
    """[summary]

    Args:
        target (List[int]): ソート対象の配列
        max_val (int): ソートする要素の最大値

    Returns:
        List[int]: ソート後の配列
    """
    result = [-1 for i in range(len(target) + 1)]

    # indexがtargetに格納される値に相当するリスト
    counta = [0 for i in range(max_val + 1)]

    # counta[i]にtの出現数を記録する。
    for t in target:
        counta[t] += 1

    # counta[i]にi以下の数の出現数を記録する。
    for i in range(1, max_val + 1):
        counta[i] += counta[i - 1]

    for t in reversed(target):
        result[counta[t]] = t
        counta[t] -= 1

    return result


n = int(input())
target = [int(i) for i in input().split()]
result = counting_sort(target, max(target))

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

Submission status: Accepted

Solution code:
def counting_sort(a, b, k):
    c = [0 for _ in range(k + 1)]
    for i in range(len(a)):
        c[a[i]] += 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]] - 1] = a[i]
        c[a[i]] -= 1

n = input()
a = list(map(int, input().split()))
b = [0 for _ in range(len(a))]
counting_sort(a, b, max(a))
print(*b)

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


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 csort(A,B,k):
    C=[0]*(k+1)
    for i in range(len(A)):
        C[A[i]]+=1
    for i in range(1,len(C)):
        C[i]+=C[i-1]
    for i in range(len(A))[::-1]:
        B[C[A[i]]-1]=A[i]
        C[A[i]]-=1
        
# input
n=int(input())
data=list(map(int, input().split()))
result=[0]*len(data)
csort(data,result,10000)
print(*result)

Submission status: Accepted

Solution code:
def counting_sort(data):
    count_list=[0]*(max(data)+1)
    sorted_data=[0]*len(data)
    
    for i in data:
        count_list[i]+=1
    
    for loop in range(len(count_list) -1 ):
        count_list[loop+1]+=count_list[loop]
    
    for i in data:
        sorted_data[count_list[i] -1 ] =i
        count_list[i]-=1
    
    return sorted_data


n=int(input())
data=list(map(int,input().split()))
result=counting_sort(data)

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

from itertools import repeat

N = int(readline())
L = 10001

C = [0]*L;
for a in map(int, readline().split()):
    C[a] += 1


ans = []
for i, c in enumerate(C):
    if c:
        ans.extend(repeat(str(i), c))
write(" ".join(ans))
write("\n")

Submission status: Accepted

Solution code:
import sys

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

    #   C[i] に i の出現数を記録する
    for j in A:
        C[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, -1, -1): # n downto 1
        B[C[A[j]]-1] = A[j]
        C[A[j]]-=1

    return B


n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = [0] * n

CountingSort(a, b, max(a))
print(' '.join(map(str, b)))

Submission status: Accepted

Solution code:
length = int(input())
target = (int(n) for n in input().split(" "))
bucket = [0 for n in range(10001)]
for t in target:
    bucket[t] += 1
answer = []
for i, b in enumerate(bucket):
    answer += [i] * b
print(*answer)

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(max(A)+1)]
for i in A:
    C[i]+=1
for i in range(1, len(C)):
    C[i]+=C[i-1]
for i in range(0, n):
    B[C[A[i]]-1] = A[i]
    C[A[i]]-=1
print(" ".join(map(str, B)))

Submission status: Accepted

Solution code:
def counting_sort(a,b,k):
  c = [0 for _ in range(k+1)]
  for i in range(len(a)):
    c[a[i]] += 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]]- 1] = a[i]
    c[a[i]] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(len(a))]
counting_sort(a, b, max(a))
print(*b)

Submission status: Accepted

Solution code:
n=int(raw_input().strip())

arr=map(int, raw_input().strip().split())


print ' '.join(str(n) for n in sorted(arr))

Submission status: Accepted

Solution code:
def CountingSort(A, k):
    n = len(A)
    C = [0for i in range(k+1)]
    #C[i] に i の出現数を記録する
    for i in range(n):
        C[A[i]] += 1
    #C[i] に i 以下の数の出現数を記録する
    for i in range(1,k+1):
        C[i] += C[i-1]
    
    B = [0for i in range(n)]  ##출력 배열 (出力配列)
    for j in range(n):
        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)
print(*CountingSort(A,k))

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    n = len(A)
    C = [0]*(k+1)
    
    # 整数kがAに何回現れるかを数える(n)
    for j in range(n):
        C[A[j]] += 1    
        
    # k以下の整数がAに何回現れるかを数える(k)
    for j in range(1, k+1):
        C[j] = C[j] + C[j-1]        
    
    # Cの情報を利用して並べ替える(n)
    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]*len(A)

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

Submission status: Accepted

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

n = int(input())
A = [int(i) for i in input().split()]
print(*counting_sort(A, n), sep=" ")

Submission status: Accepted

Solution code:
n = int(input())
a = [int(v) for v in input().split()]

vmax = 10000
b = [-1] * len(a)
c = [0] * (vmax + 1)
for v in a:
    c[v] += 1

for i in range(1, vmax + 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(' '.join([str(v) for v in b]))

Submission status: Accepted

Solution code:
# Sort II - Counting Sort
def	countingSort(A,n,k):
    result = []
    # Prepare Bucket
    C = [0]*(k+1)
    # Throw number into bucket
    for a in A:
        C[a] += 1
    # Pick up index from first in order
    for i,c in enumerate(C):
        while c > 0:
            result.append(i)
            c -= 1
    return result

n = int(input())
A = list(map(int, input().split()))
k = max(A)
B = countingSort(A,n,k)
print(*B)

Submission status: Runtime Error

Solution code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		String[] strArray = reader.readLine().split(" ");
		int[] a = new int[n];
		int[] c = new int[10000];
		int k = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(strArray[i]);
			k = Math.max(k, a[i]);
			c[a[i]]++;
		}
		int[] b = new int[n];
		countingSort(a, b, c, k);
		System.out.print(b[0]);
		for (int i = 1; i < n; i++) {
			System.out.print(" " + b[i]);
		}
		System.out.println("");
	}

	private static void countingSort(int[] a, int[] b, int[] c, int k) {
		for (int i = 1; i <= k; i++) {
			c[i] = c[i] + c[i - 1];
		}
		for (int i = a.length - 1; i >= 0; i--) {
			b[c[a[i]] - 1] = a[i];
			c[a[i]]--;
		}
	}
}

Submission status: Runtime Error

Solution code:
def counting_sort(MAX):
    C = [0 for _ in range(MAX+1)]

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

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

    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()))

MAX = 0
for n in A:
    if MAX < n:
        MAX = n

B = [0 for _ in range(N)]
counting_sort(MAX)
print(" ".join(B))

Submission status: Runtime Error

Solution code:
def counting_sort(A, k):
    B = [0] * len(A)
    C = [0] * k

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

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

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

    return B


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(*counting_sort(A, 11))


main()

Submission status: Runtime Error

Solution code:
def CountingSort(A, B, k):
    C = [0] * (k+1)
    #C[i] に i の出現数を記録する 
    for j in range(0,k):
        C[A[j]]+=1
    #print("C ",j,C[:k+1])
    #C[i] に i 以下の数の出現数を記録する
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    #print("C' ",j,C[:k+1])
    for j in range(k-1,-1,-1):
        B[C[A[j]]] = A[j]
        C[A[j]]-=1
        #print(j,A[j],C[A[j]],B[C[A[j]]],B,C)

n = int(input())
A = list(map(int,input().split()))
B = [0] * (n+1)
CountingSort(A,B,n)
print(' '.join(map(str,B[1:])))

Submission status: Runtime Error

Solution code:
n = int(input())
temp = [int(i) for i in input().split()]
A = [None for i in range(10000)]
B = [0 for i in range(n)]
k = 0
for i in range(n):
    A[i] = temp[i]
    if(A[i]>k):
        k=A[i]
def cntSort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(0, n):
        C[A[j]] += 1
    for i in range(1, k):
        C[i] += C[i-1]
    for i in range(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
cntSort(A, B, k+1)
print(*B)

Submission status: Runtime Error

Solution code:
n = int(input())
temp = [int(i) for i in input().split()]
A = [None for i in range(200000)]
B = [0 for i in range(n)]
k = 0
for i in range(n):
    A[i] = temp[i]
    if(A[i]>k):
        k=A[i]
    if(k>10000):
        break
def cntSort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(0, n):
        C[A[j]] += 1
    for i in range(1, k):
        C[i] += C[i-1]
    for i in range(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
cntSort(A, B, k+1)
print(*B)

Submission status: Runtime Error

Solution code:
n = int(input())
temp = [int(i) for i in input().split()]
A = [None for i in range(200001)]
B = [0 for i in range(n)]
k = 0
for i in range(n):
    A[i] = temp[i]
    if(A[i]>k):
        k=A[i]
    if(k>10000):
        break
def cntSort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(0, n):
        C[A[j]] += 1
    for i in range(1, k):
        C[i] += C[i-1]
    for i in range(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
cntSort(A, B, k+1)
print(*B)