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, k):
  C = [0 for i in range(k + 1)]

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

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

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

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

CountingSort(A, B, max(A))
print(*B[1:])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Counting sort 計数ソート


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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def countingSort(A):
    VMAX = 10**4 # A[i] の取りうる範囲
    C = [0] * VMAX
    result = [None] * (len(A))

    # C に A の各要素の出現回数を記録
    for i in range(len(A)):
        C[A[i]] += 1

    # C に A の各要素以下の出現回数を記録 (累積)
    for i in range(1, VMAX):
        C[i] += C[i-1]

    for i in range(len(A)-1, -1, -1): # A の添字を後ろからたどる
        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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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
        #b[count[A[i]]] = A[i]
        count[ai] -= 1
    
    return b

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

b = counting_sort(a)

print(*b)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

a.sort()
print(*a)

Submission status: Accepted

Solution code:
import copy

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

    # C[i] に i の出現数を記録する
    for j in range(n):
        C[A[j]] += 1

    # C[i] に i 以下の数の出現数を記録する
    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:])

Submission status: Accepted

Solution code:
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)):
        # print('len B {}, i, {} A[i] {}'.format(len(B), i, A[i]))
        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)))

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

print(*b)

Submission status: Accepted

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

    #C[i]にAの要素としてのiの出現数を記録する
    for i in range(n):
        C[A[i]] += 1

    #print(C)

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

    #print(C)

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

Submission status: Accepted

Solution code:
#初期値
n_max = 2000000
a_max = 10000

#インプットdata
input_n = int(input())
input_a = list(map(int, input().split()))
output = list()

#カウンタ配列Cの作成
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)))

Submission status: Accepted

Solution code:
# Counting Sort

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def countingSort(A,k):
    #カウント配列初期化
    C=[0 for _ in range(k+1)]

    #Aの各要素の出現数をカウント
    for i in range(len(A)):
        C[A[i]]+=1

    #カウント配列の累積和をとる->AにC[i]以下の数はいくつあるかわかる
    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):
#        print(i,A,B,C)
        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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#Counting Sort

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

    #C[i]に出現数を記録する
    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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ALDS1_6_A
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): # bにおけるインデックスを記録
        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))

Submission status: Accepted

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

    A 内の整数 x はすべて 0 <= x <= k の範囲にある。
    """
    # A 内の整数 i の出現数を C[i] に記録していく。
    C = [0 for _ in range(0, k + 1)]
    for x in A:
        C[x] += 1
    
    # A 内の整数のうち、i 以下の出現頻度を C[i] に記録する。
    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))

Submission status: Accepted

Solution code:
def counting_sort(in_arr, out_arr, arr_len, max_val):
    counter = [0] * (max_val + 1)  # 0, 1, 2, 3, ..., max_valのカウンター

    for i in range(arr_len):
        counter[in_arr[i]] += 1  # counterに出現数を記録

    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]  # out_arrはindex, counterは個数なので1挽く
        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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
def count_sort(numlist, n):
    C = [0 for i in range(n + 1)]
    B = [0 for i in range(len(numlist))]
    # store times that num has appear
    for num in numlist:
        C[num] += 1
    # cal index
    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(']', ''))

Submission status: Accepted

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

print(*sorted(a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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())
    # A = [0] + A
    print(*bucket_sort(A))

Submission status: Accepted

Solution code:

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

# print(C)

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

# print(C)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python
# coding=utf-8


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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    # Aの要素iの出現回数をCiに書きこむ
    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()

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from copy import deepcopy
#import heapq
#import math
#import string

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)

Submission status: Accepted

Solution code:
"""
7
2 5 1 3 2 3 0
"""

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

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

    for i in range(1, max+1):
        # print(i)
        C[i] = C[i] + C[i-1]
    # print("A", A)
    # print("B", B)
    # print("C", C)

    for j in reversed(range(n)):
        # print(j)
        # # print(j)
        # print(A[j])
        # print(C[A[j]])
        B[C[A[j]]-1] = A[j]
        # print(B)
        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)
    # print(B)
    # B_str = []
    # for b in B:
    #     B_str.append(str(b))
    # print(" ".join(B_str))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https: // onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_A
# 要素のmaxであるkさえわかっていればO(n+k)でソートできる高速なソート。天才かと思った。
# ソートしたい配列の数字をidxに対応させて、count 配列を作成. count配列を累積和。それがidxに対応しているというびっくり方法。
# ! 0 based-indexにするために、本とは違う実装


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

print(*A)

Submission status: Accepted

Solution code:
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 #(max(NUM_LIST)+1)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ALDS1_6_A Counting Sort
import sys
def counting_sort(A, B):
    k = max(A) + 1
    C = [0] * k  # k = max(A)

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