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 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 = 10001

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

Submission status: Accepted

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


main()

Submission status: Accepted

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


main()

Submission status: Accepted

Solution code:
def counting_sort(A, n, k):
    C = [0] * (k + 1)
    B = [0] * n
    for ai in A:
        C[ai] += 1
    # C[i]にi以下の出現数を記録する
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    for ai in reversed(A):
        B[C[ai] - 1] = ai
        C[ai] -= 1
    return B
n = int(input())
k = 10000
print(*counting_sort(list(map(int, input().split())), n, k))

Submission status: Accepted

Solution code:
n = int(input())
A = [int(_) for _ in input().split()]
len_C = max(A) + 1
C = [0] * (len_C)
B = [0] * n
# 各値のカウント
for i in range(n):
    C[A[i]] += 1
# カウントの和をとる
for i in range(1, len_C):
    C[i] += C[i-1]
# print("C", C)

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

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

Submission status: Accepted

Solution code:
n=int(input())
A=[0]*(n+1)
B=[0]*(n+1)
i=0
mx=(1<<30)*-1
for v in list(map(int,input().split())):
	A[i+1] = v
	mx=max(mx,A[i+1])
	i+=1	

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

st=str(B[1])
for i in range(2,n+1):
	st += ' ' + str(B[i])
print(st)

Submission status: Accepted

Solution code:
def counting_sort(array, max_val = 10000):
    max_val = min(max(array), max_val)
    counting_array = [0 for x in range(0, max_val+1)]
    sorted_array = [0 for x in range(len(array))]

    for i in array:
        counting_array[i] += 1

    for i in range(1, max_val + 1):
        counting_array[i] += counting_array[i-1]

    for i in range(len(array))[::-1]:
        val = array[i]
        sorted_array[counting_array[val]-1] = val
        counting_array[val] -= 1

    return sorted_array


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    sorted_array = counting_sort(array)
    print(" ".join(map(str, sorted_array)))
    return

main()

Submission status: Accepted

Solution code:
def counting_sort(array, max_val=10000):
    max_val = min(max(array), max_val)
    counting_array = [0] * (max_val+1)
    sorted_array = [0 for x in range(len(array))]

    for i in array:
        counting_array[i] += 1

    for i in range(1, max_val + 1):
        counting_array[i] += counting_array[i-1]

    for i in range(len(array))[::-1]:
        val = array[i]
        sorted_array[counting_array[val]-1] = val
        counting_array[val] -= 1

    return sorted_array


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    sorted_array = counting_sort(array)
    print(" ".join(map(str, sorted_array)))
    return

main()

Submission status: Accepted

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

    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, B, k):
    C = [0] * (k+1)
    for i in range(k):
        C[i] = 0
    #C[i] に i の出現数を記録する 
    for j in range(0,n):
        C[A[j]]+=1
    #print("C ",j,C[:100])
    #C[i] に i 以下の数の出現数を記録する
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    #print("C' ",j,C[:100])
    for j in range(n-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,100000)
print(' '.join(map(str,B[1:])))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * (n+1)
m = max(a)
c = [0] * (m+1)
for i in a:
    c[i] += 1
for j in range(1, m+1):
    c[j] = c[j] + c[j-1]
#print(c)
for k in reversed(a):
    #print(k)
    #print(b)
    b[c[k]] = k
    c[k] -= 1

for i in range(1,n):
    print(b[i], end=' ')
print(b[n])

Submission status: Accepted

Solution code:
def InputData():
    
    sequence_len = int(input())
    sequence = [None] + [int(a) for a in input().split(" ")]

    return sequence_len, sequence

def countingSort(sequence, k, sequence_len):
    
    B = [None]*(sequence_len+1)
    C = [0]*k
    
    for j in range(1, sequence_len+1):
        C[sequence[j]] += 1
    
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(sequence_len, 0, -1):
        B[C[sequence[j]]] = sequence[j]
        C[sequence[j]] -= 1

    return B

def PrintOut(sequence):
    print(' '.join( map(str, sequence)))

def main():
    [sequence_len, sequence] = InputData()
    sequence_out = countingSort(sequence, 10000, sequence_len)
    PrintOut(sequence_out[1:])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def counting_sort(lst,ans,max):
    cnt_lst = [0] * (max+1)
    for i in range(0,len(lst)):
        cnt_lst[lst[i]] += 1
    for j in range(1,max+1):
        cnt_lst[j] = cnt_lst[j] + cnt_lst[j-1]

    for k in range(len(lst)-1,-1,-1):
        ans[cnt_lst[lst[k]]-1] = lst[k]
        cnt_lst[lst[k]] -= 1
    return ans

n = int(input())
n_lst = list(map(int,input().split()))
ans = [0] * len(n_lst)
ans = map(str,counting_sort(n_lst,ans,max(n_lst)))
print(' '.join(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]+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
o=int(input())
a=list(map(int,input().split()))
q=max(a)
ret=countingsort(a,q)
for i in range(o):
    if i!=o-1:
        print(ret[i],end=" ")
    else:
        print(ret[i])

Submission status: Accepted

Solution code:
#計数ソート
n = int(input())
a = list(map(int, input().split()))

def countSort(a):
    N = max(a)
    c = [0]*(N+2)
    b = [0]*len(a)
    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(*b)

countSort(a)

Submission status: Accepted

Solution code:
def counting_sort(A):
    # init
    bucket = {}
    for i in range(10000):
        bucket[i] = 0

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



    k = 0
    for i in range(10000):
        for j in range(bucket[i]):
            A[k] = i
            k += 1

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

counting_sort(A)

print(*A)

Submission status: Accepted

Solution code:
def counting_sort(A):
    # init
    bucket = []
    for i in range(10000):
        bucket.append(0)

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

    k = 0
    for i in range(10000):
        for j in range(bucket[i]):
            A[k] = i
            k += 1

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

counting_sort(A)

print(*A)

Submission status: Accepted

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

    C = [0] * (k+1)

    # カウント
    for a in A:
        # print(a)
        C[a] += 1
    # print(*C)
    # print('just done')

    # 累積カウント
    for i in range(1, k+1):
        C[i] += C[i-1]

    # print(*C)

    # Bに移植
    for i in range(n-1, -1, -1):
        index_to_insert = C[A[i]] - 1
        C[A[i]] -= 1
        B[index_to_insert] = A[i]
        # print(*C)

    return B

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

B = []
B = counting_sort(A, B, 10000)
print(*B)

Submission status: Accepted

Solution code:
def CountingSort(A,B,num):

	k = max(A)
	C = [0 for _ in range(k+1)]
	#C[i]にiの出現回数を記録する
	for i in A:
		C[i] += 1

	#C[i]にi以下の数の出現数を記録する =>累積度数分布を出力
	for j in range(1,k+1):
		C[j] += C[j-1]
	for h in range(num-1,-1,-1):
		B[C[A[h]]-1] = A[h]
		C[A[h]] -= 1

if __name__ == '__main__':

	num = int(input())
	A = [int(i) for i in input().split()]

	B = [0 for _ in range(num+1)]
	CountingSort(A,B,num)

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

Submission status: Accepted

Solution code:
input()
print " ".join(sorted(raw_input().split(),key=int))

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 countingsort(a, b, k):
    c = [0 for i 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] * n
countingsort(a, b, max(a))
print(*b)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def CountingSort(A, k):
    count = [0] * k
    offset = [0] * k
    for x in A:
        count[x] += 1
    offset[0] = 0
    for i in xrange(1, k):
        offset[i] = offset[i-1] + count[i-1]

    R = [0] * len(A)
    for i in xrange(len(A)):
        target = A[i]
        R[offset[target]] = target
        offset[target] += 1
    return R

n = int(raw_input())
A = map(int, raw_input().split())
B = CountingSort(A, 10000)
print ' '.join(map(str, B))

Submission status: Accepted

Solution code:
def CountingSort(A,B,k):
    C = []
    for i in range(0,k+1):
        C.append(0)
    for j in A:
        C[j] += 1
    for i in range(0,k+1):
        while(C[i] != 0):
            B.append(i)
            C[i] -= 1
B = []
n = int(input())
st = input()
A = list(map(int,st.split()))
max = 0
for x in A:
    if x > max:
        max = x
CountingSort(A,B,max)
for i in range(0,n-1):
    print(B[i],end=" ")
print(B[n-1])

Submission status: Accepted

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


import array
import sys


def counting_sort(a, n, k=10000):
    b = array.array("I", (0 for x in range(n)))
    c = array.array("I", (0 for x in range(k + 1)))
    for j in range(0, n):
        c[a[j]] += 1
    for i in range(0, 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
    return b


def main():
    n = int(sys.stdin.readline())
    a = array.array("I", map(int, sys.stdin.readline().split()))
    print(" ".join(map(str, counting_sort(a, n))))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
S = map(int,raw_input().strip().split(' '))

def counting_sort(S,k):
    C = [0]*(k+1)
    B = [0]*len(S)
    for v in S:
        C[v] += 1
    for i in range(1,k+1):
        C[i] += C[i-1]
    for i in range(len(S)):
        B[C[S[i]]-1] = S[i]
        C[S[i]] -= 1
    return B

B = counting_sort(S,10000)
for b in B:
    print b,

Submission status: Accepted

Solution code:
#coding:utf-8
#1_6_A
def counting_sort(array):
    cnt = [0 for i in range(max(array)+1)]
    result = [0 for  i in range(len(array))]

    for j in range(len(array)):
        cnt[array[j]] += 1

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

    for j in reversed(range(len(array))):
        result[cnt[array[j]]-1] = array[j]
        cnt[array[j]] -= 1

    return result

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

Submission status: Accepted

Solution code:
n, a = int(input()), list(map(int, input().split()))
b, c = [0] * n, [0] * 10001

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

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

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

print(*b)

Submission status: Accepted

Solution code:
"""Counting Sort."""

def countingSort(A, B, k):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and k, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

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

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

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

    print(*B[1:])


n = int(input())

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

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

k = max(A)

countingSort(A, B, k)

Submission status: Accepted

Solution code:
"""Counting Sort."""

def countingSort(A, B):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and k, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

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

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

    print(*B[1:])


n = int(input())

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

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

# k = max(A)

countingSort(A, B)

Submission status: Accepted

Solution code:
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and k, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    k = max(A)
    
    C = [0 for i in range(k + 1)]

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

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

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

    print(*B[1:])


n = int(input())

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

countingSort(A, n)

Submission status: Accepted

Solution code:
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

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

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

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

    print(*B[1:])


n = int(input())

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

countingSort(A, n)

Submission status: Accepted

Solution code:
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

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

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

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

    print(*B[1:])


import sys

n = int(sys.stdin.readline())

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

countingSort(A, n)

Submission status: Accepted

Solution code:
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

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

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

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

    print(*B[1:])


import sys

n = int(sys.stdin.readline())

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

countingSort(A, n)

Submission status: Accepted

Solution code:
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

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

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

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

    print(*B[1:])


import sys

n = int(sys.stdin.readline())

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

countingSort(A, n)

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
B = [0] * n

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

def main():
    CountingSort(A, B, 10000)
    print ' '.join(map(str,B))
    return 0

main()

Submission status: Accepted

Solution code:
class CountingSort:
    def countingSort(self, a, b, k):
        n = len(a)
        c = [0] * (k + 1)
        for j in a:
            c[j] += 1
        
        for i in range(1, k + 1):
            c[i] = c[i] + c[i-1]
            
        for j in a[::-1]:
            b[c[j]] = j
            c[j] -= 1
        return b[1:]

if __name__ == '__main__':
    n = int(input().rstrip())
    a = [int(i) for i in input().rstrip().split(" ")]
    b = [0] * (n + 1)
    k = max(a)
    x = CountingSort()
    print(" ".join([str(i) for i in x.countingSort(a, b, k)]))

Submission status: Accepted

Solution code:
def counting_sort(A, k):
    B, C = [], [0]*(k+1)
    for j in range(0, len(A)):
        C[A[j]] += 1
    for i in range(0, len(C)):
        while True:
            if C[i] != 0:
                B.append(i)
                C[i] -= 1
            else:
                break
    return B

input()
num = list(map(int, input().split()))
result = counting_sort(num, max(num))
print(*result)

Submission status: Accepted

Solution code:
def countingsort(A,B,k):
    global n
    C=[0 for i in xrange(k+1)]
    for j in xrange(1,n+1):
        C[A[j]]+=1
    for i in xrange(1,k+1):
        C[i]+=C[i-1]
    for j in xrange(n,0,-1):
        B[C[A[j]]]=A[j]
        C[A[j]]-=1

n=input()
A=[0]
a=map(int,raw_input().split())
for i in a:
    A.append(i)
B=[0]*n+[0]
k=max(A)
countingsort(A,B,k)
B=map(str,B)
print(" ".join(B[1:]))

Submission status: Accepted

Solution code:
import sys

def countingSort(A, B, k):
    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 - 1]

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

    del B[0]
    print " ".join([str(b) for b in B])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    B = []
    countingSort(A, B, max(A))

Submission status: Accepted

Solution code:


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

    # C[i]???i???????????°????¨??????????
    for j in range(0, n):
        C[A[j]] += 1

    # C[i]???i??\????????°???????????°????¨??????????
    for i in range(0, k):
        C[i + 1] +=  C[i]

    for j in reversed(range(0, n)):
        B[C[A[j]]] = str(A[j])
        C[A[j]] -= 1
    return ' '.join(B[1:])

n = int(input())
A = list(map(int, input().split()))
k = max(A)
print(counting_sort(A, k))

Submission status: Accepted

Solution code:
import sys

'''
def countingSort(A, B, k):
    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]

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

    del B[0]
    print " ".join([str(b) for b in B])
    '''

def countingSort(A, B, k):
    C = [0] * (k + 1)
    for i in range(len(A)):
        C[A[i]] += 1
    for i in range(len(C)):
        for j in range(C[i]):
            B.append(i)
    print " ".join([str(b) for b in B])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    B = []
    countingSort(A, B, 10000)

Submission status: Accepted

Solution code:
import sys

def countingSort(A, k):
    Sorted = []
    Cnt = [0] * (k + 1)

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

    for i in range(len(Cnt)):
        for j in range(Cnt[i]):
            Sorted.append(i)

    print " ".join([str(v) for v in Sorted])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    countingSort(A, 10000)

Submission status: Accepted

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

def countSort(A, m):
    count = [0]*(m+1)
    n = len(A)
    B = [0]*2000001
    j = 0
    for i in range(n):
        count[A[i]] += 1
    for i in range(1, m):
        count[i] += count[i-1]
    for i in range(n-1, -1, -1):
        j = count[A[i]]
        B[j] = A[i]
        count[A[i]] = j-1
    for i in range(n):
        A[i] = B[i+1]
    return A

n = int(raw_input())
A = map(int, raw_input().split())
B = countSort(A, 10000)
print " ".join(map(str, B))

Submission status: Accepted

Solution code:
def countingSort(A,k):
    C = {}
    for ai in A:
        C[ai] = C.get(ai,0) + 1
    for i in range(1,k+1):
        C[i] = C.get(i,0) + C.get(i-1,0)
    B = A[:]
    for ai in A:
        B[C[ai]-1] = ai
        C[ai] -= 1
    return B

if __name__=='__main__':
    n=int(input())
    print(*countingSort(list(map(int,input().split())),10000))

Submission status: Accepted

Solution code:
def countingSort(A,k):
    C = {}
    for ai in A:
        C[ai] = C.get(ai,0) + 1
    for i in range(1,k+1):
        C[i] = C.get(i,0) + C.get(i-1,0)
    B = A[:]
    for ai in A[::-1]:
        B[C[ai]-1] = ai
        C[ai] -= 1
    return B

if __name__=='__main__':
    n=int(input())
    print(*countingSort(list(map(int,input().split())),10000))

Submission status: Accepted

Solution code:
def countingsort(a, n):
    c = [0]*10001

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

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

    b = [0]*(n+1)

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

    return b[1:]


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

Submission status: Accepted

Solution code:
def counting_sort(a,k):
    C = []
    for i in range(k):
        C.append(0)
    for ai in a:
        C[ai] += 1
    s = 0
    for i in range(k):
        s += C[i]
        C[i] = s
    b = []
    for i in range(len(a)):
        b.append(None)
    p = 0
    for i in range(k):
        while p < C[i]:
            b[p] = i
            p += 1
    return b


n = int(raw_input())
a = map(int,raw_input().split(' '))
print ' '.join(map(str,counting_sort(a,10000)))

Submission status: Accepted

Solution code:
class CountingSort:
    def countingSort(self, a, b, k):
        n = len(a)
        c = [0] * (k + 1)
        for j in a:
            c[j] += 1
         
        for i in range(1, k + 1):
            c[i] = c[i] + c[i-1]
             
        for j in a[::-1]:
            b[c[j]] = j
            c[j] -= 1
        return b[1:]
 
if __name__ == '__main__':
    n = int(input().rstrip())
    a = [int(i) for i in input().rstrip().split(" ")]
    b = [0] * (n + 1)
    k = max(a)
    x = CountingSort()
    print(" ".join([str(i) for i in x.countingSort(a, b, k)]))

Submission status: Accepted

Solution code:
import array
import sys
def counting_sort(A, B, n, k=10000):
    C = array.array('I', [0 for i in range(k+1)])
    for j in range(0, n):
        x = A[j]
        C[x] += 1
    for i in range(0, 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 = list(map(int , sys.stdin.readline()[:-1].split()))

B = array.array("I", [0 for i in range(n)])
counting_sort(A, B, n)

print(*B)

Submission status: Accepted

Solution code:
#coding:UTF-8

def Max(A):
    max=0
    for i in range(len(A)):
        if A[i]>max:
            max=A[i]
    return max

def CS(A,n):
    B=[]
    C=[]
    cn=Max(A)+1
    for i in range(n):
        B.append(0)
    for i in range(cn):
        C.append(0)
    for j in range(n):
        C[A[j]]+=1
    for i in range(1,cn):
        C[i]+=C[i-1]
    for j in reversed(range(n)):
        B[C[A[j]]-1]=A[j]
        C[A[j]]-=1
    for i in range(len(B)):
        B[i]=str(B[i])
    print(" ".join(B))
 
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    CS(A,n)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A&lang=jp
#?¨???°?????????

def counting_sort(target_list):
    counter = [0 for i in range(10000)]

    for n in target_list:
        counter[n] += 1

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

    result = [0 for i in range(len(target_list))]
    for n in target_list[::-1]:
        result[counter[n] - 1] = n
        counter[n] -= 1
    
    return result
if __name__ == "__main__":
    n_list = int(input())
    target_list = [int(s) for s in input().split()]
    sorted_list = counting_sort(target_list)
    print(" ".join([str(s) for s in sorted_list]))

Submission status: Accepted

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


import sys


def counting_sort(A, max_occurance):
    result = [0] * array_length
    count_list = [0] * max_occurance

    for j in range(array_length):
        count_list[A[j]] += 1
    # print('1', C[:array_length])

    for i in range(1, max_occurance):
        count_list[i] += count_list[i - 1]
    # print('2', C[:array_length])

    for m in array[::-1]:
        result[count_list[m] - 1] = m
        count_list[m] -= 1

    return result


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    max_elem = int(1e4)
    result = counting_sort(A=array, max_occurance=max_elem)
    print(*result)

Submission status: Accepted

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


import sys


def counting_sort(A, max_occurance):
    result = [0] * array_length
    count_list = [0] * max_occurance

    for j in range(array_length):
        count_list[A[j]] += 1
    # print('1', C[:array_length])

    for i in range(1, max_occurance):
        count_list[i] += count_list[i - 1]
    # print('2', C[:array_length])

    for m in array[::-1]:
        result[count_list[m] - 1] = m
        count_list[m] -= 1

    return result


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    # assert len(array) == array_length
    max_elem = int(1e4)
    result = counting_sort(A=array, max_occurance=max_elem)
    print(*result)

Submission status: Accepted

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


import sys


def counting_sort(A, max_occurance):
    result = [0] * array_length
    count_list = [0] * max_occurance

    for j in range(array_length):
        count_list[A[j]] += 1
    # print('step-1', C[:array_length])

    for i in range(1, max_occurance):
        count_list[i] += count_list[i - 1]
    # print('step-2', C[:array_length])

    for m in array[::-1]:
        result[count_list[m] - 1] = m
        count_list[m] -= 1

    return result


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    max_elem = int(1e4)
    result = counting_sort(A=array, max_occurance=max_elem)
    print(*result)