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:
n = int(input())
A = list(map(int, input().split()))

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

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

    for j in range(0, n)[::-1]:
        B[C[A[j]] - 1] = A[j]
        C[A[j]]-=1
    return B
        
print(' '.join(map(str, countingSort(A, [0] * n, 10000))))

Submission status: Accepted

Solution code:
def countingsort(A, k):
    C = [0 for i in range(k+1)]
    B = [0 for i in range(len(A))]
    for e in A:
        C[e] += 1
    for i in range(1, k+1):
        C[i] += C[i-1]
    for e in A[::-1]:
        B[C[e]-1] = e
        C[e] -= 1
    return B
    
n = input()
x = map(int, raw_input().split())

x = countingsort(x, max(x))

for e in x:
    print e,

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from collections import Counter


def counting_sort(a, b, k):
    c = Counter()
    for j in a:
        c[j] += 1
    for i in range(1, k+1):
        c[i] += c[i-1]
    for j in a[::-1]:
        b[c[j]] = j
        c[j] -= 1


n = int(stdin.readline())
data = [int(s) for s in stdin.readline().split()]
output = [0] * (n+1)
counting_sort(data, output, 10000)
print(*output[1:])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
n=int(raw_input())
A=map(int, raw_input().split())
A.sort()
print ' '.join(map(str,A))

Submission status: Accepted

Solution code:
def CountingSort(A, B, k):
    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]-1] = j
        C[j] -= 1


n = int(input())
inlst = list(map(int, input().split()))
k = max(inlst)
outlst = [0]*n
CountingSort(inlst, outlst, k)
print(*outlst)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = [int(x) for x in input().split()]
C = [0] * 10001
B = [0] * (n)
for a in A:
    C[a] += 1
for i in range(1, 10001):
    C[i] += C[i-1]
    if C[i] == n:
        break
for a in A[::-1]:
    B[C[a]-1] = a
    C[a] -= 1
print(*B)

Submission status: Accepted

Solution code:
# 計数ソート
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_A
# 計算量 O(n+k)

import sys
input = sys.stdin.buffer.readline

n = int(input())
A = [int(i) for i in input().split()]
B = [None] * n
C = [0] * 10001

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

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

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

print(" ".join([str(b) for b in 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,k+1):
        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
    return B

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

for i in range(len(B)):
    if i<len(B)-1:
        print(B[i],end=' ')
    else:
        print(B[i])

Submission status: Accepted

Solution code:
# 係数ソート
def countingSort(A, B, k, n):
    c = [0] * (k+1)
        
    for i, a in enumerate(A):
        c[a] += 1

    for i in range(1, k+1):
        c[i] = c[i] + c[i-1]
        
    for j, a in enumerate(reversed(A)):
        B[c[a]-1] = a
        c[a] -= 1
        
    print(*b)
    return

import sys
import copy
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
b = [0] * n
k = max(a)

countingSort(a, b, k, n)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in list(input().split())]
b = [0] * (n + 1)
c = [0] * 10001
k = max(a)

# C[i] に i の出現数を記録する
for i in a:
    c[i] += 1

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

for i in reversed(a):
    b[c[i]] = i
    c[i] -= 1

print(*b[1:])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int,input().split()))
    B = [0]*(len(A))
    #print(B)

    A1 = A
    A1.sort(reverse = True)

    C = [0]*(A1[0] + 1)
    #要素の数をCに記憶
    for i in range(n):
        C[A[i]] += 1
    #print(C)

    #累積和をとるよ
    for i in range(len(C)):
        if i == 0:
            continue
        else:
            C[i] += C[i-1]
    #print(C)

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

    return B

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

Submission status: Accepted

Solution code:
def countingSort(A,k):
    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(len(A))]
    for i in A:
        x=C[i]
        B[x-1]=i
        C[i]-=1
    return B
n=int(input())
a=[int(i)for i in input().split()]
b=countingSort(a,10000)
print(" ".join(map(str,b)))

Submission status: Accepted

Solution code:
def counting_sort(A):
    B = A.copy()
    C = [0 for _ in range(max(A) + 1)]
    
    for num in A:
        C[num] += 1
    for index in range(1, len(C)):
        C[index] = C[index] + C[index-1]

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

num = int(input())
arr = list(map(int, input().split()))
arr = counting_sort(arr)
print(" ".join(map(str, arr)))

Submission status: Accepted

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

SIZE = 10001
max = max(A)

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

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

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

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

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def counting_sort(A, B, C, K, N):
    # 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 reversed(range(N)):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    K = max(A)
    B = [0] * N
    C = [0] * (K + 1)

    counting_sort(A, B, C, K, N)
    print(*B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def countingSort(A, k=None):
    if not k:
        k = max(A)
    C = [ 0 for i in range(k+1)]
    for j in range(len(A)):
        C[A[j]] += 1
    total = 0
    for k in range(len(C)):
        total += C[k]
        C[k] = total
    B = [ 0 for l in range(len(A))]
    for _A in A[::-1]:
        B[C[_A]-1] = _A
        C[_A] -= 1
    return B


if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    print(' '.join(map(str,countingSort(A))))

Submission status: Accepted

Solution code:
def countingSort(a,m):
    m += 100
    cnt = [0]*m
    for i in a:
        cnt[i] += 1
    i = 0
    for b in range(m):
        for c in range(cnt[b]):
            a[i] = b
            i+=1
    return a
n = int(input())
a = countingSort(list(map(int,input().split())),n)
print(*a)

Submission status: Accepted

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

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

    return B


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

    B = counting_sort(A, n, 10000)
    print(*B)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def countingSort(A):
    max_a = max(A)
    C = []
    for i in range(max_a+1):
        C.append(0)

    for a in A:
        C[a] += 1
    cum_sum = 0
    for i in range(max_a+1):
        cum_sum += C[i]
        C[i] = cum_sum
        
    B = []
    for _ in range(len(A)):
        B.append(None)
    for a in A[::-1]:
        B[C[a]-1] = a
        C[a] -= 1
    return B

_ = input()
A = list(map(int, input().rstrip().split(" ")))
B = countingSort(A)
print(" ".join(list(map(str, B))))

Submission status: Accepted

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

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 reversed(range(0,n)):
    #print(A[j])
    #print(C[A[j]])
    #print(B[C[A[j]]])
    #print('---')
    B[C[A[j]]-1]=A[j]
    C[A[j]]-=1

countingSort(A,B,max(A))
print(*B)

Submission status: Accepted

Solution code:
def counting_sort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(n):
        C[A[j]] += 1
    #C[i] now contains the number of elements equal to i

    for i in range(1, k):
        C[i] += C[i - 1]
    #C[i] now contains the number of elements less than or equal to i

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

k = max(A) + 1
B = [0 for _ in range(n)]


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

Submission status: Accepted

Solution code:
import sys


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]

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

    # 個数を数える
    for a in A:
        C[a] += 1

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

    B = [None] * N

    # 個数に基づいて新しい配列を設定する

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

    print(" ".join(list(str(x) for x in B)))


main()

Submission status: Accepted

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

b = [0] * n
c = [0] * (MAXAI + 1)
for i in range(n):
    c[a[i]] += 1
for i in range(1, MAXAI + 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

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

Submission status: Accepted

Solution code:

from typing import List, Callable
# verified @AOJ ALDS1_6_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A&lang=jp
def counting_sort_destructive(L: List[int], k: int, key: Callable[[int], int] =lambda x: x) -> None:
    """
    counting_sort() の破壊関数版

    Args:
        L (list)
        k (int): L の要素は 0 to k であると仮定する
        key (function): key が指定されている場合、key を L の各要素に適用してからソートを行う

    Raises:
        ValueError: L の要素のいずれかが 0 <= x <= k を満たしていなかった場合

    Examples:
        >>> seq = [1, 3, 5, 10, 4, 6, 15, 7, 2, 0] 
        >>> counting_sort_destructive(seq, 15)    # 0 to 15
        >>> seq
        [0, 1, 2, 3, 4, 5, 6, 7, 10, 15]
    """
    if any(map(lambda x: key(x) < 0 or key(x) > k, L)):
        raise ValueError(f"counting_sort_destructive(): key(x) (x: element of L) should be 0 <= key(x) <= k. got k: {k}")

    n = len(L)
    accum_sum_memo = [0] * (k + 1)    # 0 to k なので

    for i in range(n):
        accum_sum_memo[key(L[i])] += 1
    for i in range(1, k+1):
        accum_sum_memo[i] += accum_sum_memo[i-1]
    
    tmp = tuple(L)    # もとの L のメモは変更されてはならない！
    for j in range(n-1, -1, -1):
        L[accum_sum_memo[key(tmp[j])] - 1] = tmp[j]
        accum_sum_memo[key(tmp[j])] -= 1    # 同じ値のものが来た時、一つ前の位置におさまるように調節してやる



# partially verified @AOJ ALDS1_6_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A&lang=jp
def radix_sort(L: List[int], bucket_bit_size: int=8) -> None:
    """
    bucket_size = 2 ** bucket_bit_size とする (除算を避けビットシフトのみで実装するため、bucket_size は 2 の冪を仮定している)
    O(digit_length * (n + bucket_size)) で L を安定的かつ破壊的に基数ソートする (digit_length = log(n, bucket_size) である)
    
    Args:
        L (list)
        bucket_bit_size (int): L の各値を何 bit ごとに分けて基数ソートを行うかの値
    
    Raises:
        ValueError: L に負の値が含まれているとき

    Examples:
        >>> seq = [4321, 5500, 8686, 5586, 1234, 1235, 0, 24, 7, 1000000007]
        >>> radix_sort(seq, bucket_bit_size=8)
        >>> seq
        [0, 7, 24, 1234, 1235, 4321, 5500, 5586, 8686, 1000000007]
    """
    if any(map(lambda x: x < 0, L)):
        raise ValueError(f"radix_sort(): element of L should be positive. got L: {L}")
    if L:
        M = max(L)
        # 各整数を bucket_bit_size ビットごとに区切ると最大で何個のかたまりになりうるか
        max_digit_chank = (M.bit_length() + bucket_bit_size - 1) // bucket_bit_size
        # bucket_bit_size ビット分が 1 埋めされた bit mask
        mask = (1 << bucket_bit_size) - 1    # bit shift は +, - より優先度が低いので注意
        for i in range(max_digit_chank):
            key_func = lambda x: (x >> (i * bucket_bit_size)) & mask
            counting_sort_destructive(L, mask, key_func)




if __name__ == "__main__":
    n = int(input())
    L = list(map(int, input().split()))
    radix_sort(L, 16)
    print(*L, sep=' ')

Submission status: Accepted

Solution code:
def CountingSort(A, k):
    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 a in A:
      B[C[a]-1] = a
      C[a] -= 1
      
    return B
    
n = int(input())
a = list(map(int, input().split()))
ans = CountingSort(a, 10000)
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

input()
C = [0]*10_001

for a in map(int, input().split()):
    C[a] += 1
    
B = []
i = 0
for c in C:
    B += [i]*c
    i += 1
print(*B)

Submission status: Accepted

Solution code:
def countingSort(A, B, k):
    from collections import defaultdict
    C = defaultdict(int)
    for a in A:
        C[a] += 1
    cnt = 0
    for i in range(max(C.keys()) + 1):
        for _ in range(C[i]):
            B[cnt] = i
            cnt += 1


def resolve():
    n = int(input())
    A = [int(i) for i in input().split()]
    B = [0] * n
    countingSort(A, B, max(max(A), n))
    print(*B)

resolve()

Submission status: Accepted

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

maxlen = max(A)

C1 = [0] * (maxlen + 1)

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

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

C = list(accumulate(C))

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

print(*B)

Submission status: Accepted

Solution code:
# coding: utf-8
# 計数ソート


def countingSort(A, B, k):
    global n

    C = [0] * k

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

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

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


if __name__ == "__main__":
    n = int(input())
    A = [int(i) for i in input().split()]

    B = [0] * n

    countingSort(A, B, max(A) + 1)
    print(' '.join(map(str, B)))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    A = LI()

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

    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]]] = A[j]
            C[A[j]] -= 1

        print(*B[1:])

    CountingSort(A, B, k)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

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

if __name__ == "__main__":
    n = int(input())
    A = [0] + list(map(int,input().split()))
    k = 10000
    B = [0]*(n+1)
    CountingSort(A,B,k)
    print(*B[1:])

Submission status: Accepted

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

def counting_sort(nums,n):
    max_nums=max(nums)
    basket=[0 for i in range(max_nums+1)]
    for i in range(n):
        key=nums[i]
        basket[key]+=1

    answer=[]
    for i in range(len(basket)):
        if basket[i]!=0:
            for j in range(basket[i]):
                answer.append(i)
    return answer

answer=counting_sort(nums,n)
print(' '.join(map(str,answer)))

Submission status: Accepted

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

for num in A:
    c[num] += 1

for i in range(0, max(A)):
    c[i + 1] += c[i]

for j in range(-1, -n-1, -1):
    output[c[A[j]] - 1] = A[j]
    c[A[j]] -= 1

print(*output)

Submission status: Accepted

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

def CountingSort(A):
    MAX = 10000
    B = [0 for e in range(n)]
    C = [0 for e in range(MAX)]
    
    for j in range(n):
        C[A[j]] += 1
    
    for i in range(1,MAX):
        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(e) for e in input().split()]
print(*CountingSort(A))

Submission status: Accepted

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

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

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

j = 0
for i in range(10001):
    for c in range(C[i]):
        B[j] = i
        j += 1

print(' '.join([str(x) for x in B]))

Submission status: Accepted

Solution code:
def countng_sort(a):
  MAX = 10000
  n = len(a)
  b = [None] * n
  c = [0] * MAX
  
  for i in range(n):
      c[a[i]] += 1
  
  for i in range(1, MAX):
      c[i] += c[i - 1]
  
  for i in reversed(range(0, n)):
      b[c[a[i]] - 1] = a[i]
      c[a[i]] -= 1

  return b

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

Submission status: Accepted

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

def countingSort(n,a,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]
    b=[0]*n
    for j in range(n-1,-1,-1):
        b[c[a[j]]-1]=a[j]
        c[a[j]]-=1
    return b

def main(n,a):
    b=countingSort(n,a,10000)
    return b 
    
if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(' '.join(map(str,ans)))

Submission status: Accepted

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

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

A = countingSort(A, max(A))
print(" ".join([str(s) for s in A]))

Submission status: Accepted

Solution code:
def countng_sort(a):
  MAX = 10000
  n = len(a)
  b = [None] * n
  c = [0] * MAX
  
  for i in range(n):
      c[a[i]] += 1
  
  for i in range(1, MAX):
      c[i] += c[i - 1]
  
  for i in reversed(range(0, n)):
      b[c[a[i]] - 1] = a[i]
      c[a[i]] -= 1

  return b

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

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
A = list(map(int, input().split()))
B = [-1]*n
CountingSort(A, B, max(A))
print(*B)

Submission status: Accepted

Solution code:
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:
def counting_sort(n, A, k=10001):
    C = [0 for _ in range(k)]
    B = [0 for _ in range(n)]

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

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

    for j in range(n-1, -1, -1):
        # C[A[j]]はA[j]以下にどれくらいの要素があるかを表している
        # したがって一番大きい数字はnになるので、-1をしてインデックス
        # をずらす必要がある
        B[C[A[j]]-1] = A[j] 
        C[A[j]] -= 1

    return B


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
maxx = 2000001
maxnum = 10010

n=int(input())
A=[int(x) for x in input().split()]  

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

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


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

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

print(*B)

Submission status: Accepted

Solution code:
MAX =20000001
VMAX = 10001
INF = 10 ** 10
cnt = 0

def CountingSort(A, n):
    B = [0 for x in range(n)]
    C = [0 for x in range(VMAX)]
    # C[i] に i の出現数を記録する
    for j in range(n):
        C[A[j]] += 1

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

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


n = int(input())
A =[int(x) for x in input().split()]
CountingSort(A, n)

Submission status: Accepted

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

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

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

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

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

    return B

ans = []
ans = countingsort(sort_list,ans,max(sort_list))
print(' '.join([str(i) for i in ans]))

Submission status: Accepted

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

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

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

counting_sort(A, B, 10000)
print(" ".join(map(str, B)))

Submission status: Accepted

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

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

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

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

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

k = 10000
out = CountingSort(A,k)

print(*out, sep=" ")

Submission status: Accepted

Solution code:
def counting_sort(arr):
    max_value = max(arr) + 1
    counter = [0] * max_value

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

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

    sorted_arr = [0] * len(arr)
    for i in range(len(arr)):
        sorted_arr[counter[arr[i]] - 1] = arr[i]
        counter[arr[i]] -= 1
    
    return sorted_arr

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

print(*counting_sort(arr))

Submission status: Accepted

Solution code:
N =int(input())
A = list(map(int,input().split()))
COUNT = [0]*10000

def cnt_sort(A):
    res = [""] * len(A)
    for a in A:
        COUNT[a]+=1
    for i in range(1,len(COUNT)):
        COUNT[i] = COUNT[i] + COUNT[i-1]
    for a in A:
        res[COUNT[a]-1] = str(a)
        COUNT[a] -=1
    return res

print(" ".join( cnt_sort(A)))

Submission status: Accepted

Solution code:
N=int(input())
num_list=[int(i) for i in input().split()]
B=[None]*N
def counting(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-1]
    for j in range(N-1,-1,-1):
        B[C[A[j]]-1]=A[j]
        C[A[j]]-=1
    return B
ans=counting(num_list,B,10000)
print(*ans)

Submission status: Accepted

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

def counting_sort(A):
    n=len(A)
    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-1]+C[i]

    ans=[0]*n

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

print(*counting_sort(A))

Submission status: Accepted

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

n = int(input())
arr = list(map(int, input().split()))
B = [0]*n
counting_sort(arr, B, 10001)
print(*B)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

K = 10000
C = [0] * K

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

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

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

print(*B)

Submission status: Accepted

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

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


AA = counting_sort(A)
print(*AA)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
C = [0 for _ in range(10000)]


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

    return B


print(*counting_sort(A, n, 10000))

Submission status: Accepted

Solution code:
k = 10**5
c = [0] * k
n = int(input())
A = [int(_) for _ in input().split()]
B = [0] * (n+1)
# print(B)

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

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

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

    # print(c)

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

CountingSort(A, B, k)
print(" ".join(map(str, B[1:])))

Submission status: Accepted

Solution code:
def countingsort(A, n, k):
    B = [None for _ in range(n+1)]
    C = [0 for _ 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 range(n-1, -1, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1

    return B

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

    print(' '.join(map(str, countingsort(A, n, k)[1:])))

Submission status: Accepted

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

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

n = int(input())
a = tuple(map(int,input().split()))

b = [0 for i in range(n)]
CountingSort(a,b,max(a))
print(*b)

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
L_temp=L

A_N=100010
counter=[0]*A_N

for l in L_temp:
    counter[l]+=1
    
for c_idx in range(1,len(counter)):
    counter[c_idx]+=counter[c_idx-1]
# print(counter)
    
L_sort=[0]*len(L_temp)

for l in L_temp[::-1]:
    L_sort[counter[l]-1]=l
    # print(l,counter[l],L_sort)
    counter[l] -= 1
    
print(' '.join(map(str,L_sort)))

Submission status: Accepted

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


if __name__ == '__main__':
    main()