Comparison Sorting 

Quicksort usually has a running time of $n\times log(n)$, but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat $n\times log(n)$ (worst-case) running time, since $n\times log(n)$ represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF). 

Alternative Sorting 

Another sorting method, the counting sort, does not require comparison.  Instead, you create an integer array whose index range covers the entire range of values in your array to sort.  Each time a value occurs in the original array, you increment the counter at that index.  At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

Example 

$arr=[1,1,3,2,1]$    

All of the values are in the range $[0\ldots3]$, so create an array of zeros, $result=[0,0,0,0]$.  The results of each iteration follow:

i	arr[i]	result
0	1	[0, 1, 0, 0]
1	1	[0, 2, 0, 0]
2	3	[0, 2, 0, 1]
3	2	[0, 2, 1, 1]
4	1	[0, 3, 1, 1]

The frequency array is $[0,3,1,1]$. These values can be used to create the sorted array as well: $sorted=[1,1,1,2,3]$.

Note 

For this exercise, always return a frequency array with 100 elements.  The example above shows only the first 4 elements, the remainder being zeros.  

Challenge 

Given a list of integers, count and return the number of times each value appears as an array of integers.

Function Description  

Complete the countingSort function in the editor below.  

countingSort has the following parameter(s):  

arr[n]: an array of integers  

Returns   

int[100]: a frequency array

Input Format

The first line contains an integer $n$, the number of items in $\textbf{arr}$. 

Each of the next $n$ lines contains an integer $arr\left[i\right]$ where $0\leq i<n$.  

Constraints

$100\leq n\leq10^{6}$ 

$0\leq arr[i]<100$ 

Sample Input
100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33  

Sample Output
0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2 

Explanation

Each of the resulting values $result[i]$ represents the number of times $\boldsymbol{i}$ appeared in $\textbf{arr}$.

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
N = int(input())
arr = list(map(int, input().split()))
freq = [0] * 100
for i in arr:
	freq[i] = freq[i] + 1
print(' '.join(map(str, freq)))


n = int(input())
ar = [int(x) for x in input().strip().split(' ')]
c = [0] * 100
for a in ar:
	c[a] += 1
print(' '.join([str(x) for x in c]))


import sys
n = int(sys.stdin.readline())
ar = [int(x) for x in sys.stdin.readline().split()]
counter = {}
for a in ar:
	counter[a] = counter.get(a, 0) + 1
values = []
for num in range(0, 100):
	values.append(str(counter.get(num, 0)))
print(' '.join(values))


def main():
	size = input()
	arr_str = input()
	arr = list(map(int, arr_str.split()))
	count = [0] * 100
	for item in arr:
		count[item] += 1
	print(' '.join((str(i) for i in count)))
main()


n = int(input())
counts = {i: 0 for i in range(100)}
vals = [int(i) for i in input().split()]
for i in range(n):
	counts[vals[i]] += 1
for i in range(100):
	print(counts[i], end=' ')
print()


n = int(input())
output = dict()
args = [int(elt) for elt in input().split()]
for elt in args:
	try:
		output[elt] += 1
	except KeyError:
		output[elt] = 1
for i in range(100):
	try:
		print(output[i], end=' ')
	except:
		print(0, end=' ')


size = input()
data = [int(x) for x in input().strip().split(' ')]
a = [0 for i in range(100)]
for x in data:
	a[x] += 1
print(' '.join([str(x) for x in a]))


n = int(input())
ar = [int(i) for i in input().strip().split()]
x = [0 for i in range(100)]
for e in ar:
	x[e] += 1
print(*x, sep=' ')


l = [0 for i in range(0, 100)]
n = int(input())
t = list(map(int, input().split()))
for i in t:
	l[i] += 1
for i in range(0, 100):
	print(l[i], end=' ')


n = int(input())
ar = [int(x) for x in input().split()]
res = [0] * 100
for x in ar:
	res[x] += 1
print(' '.join(map(str, res)))


input()
count = [0] * 100
for n in map(int, input().split()):
	count[n] += 1
print(' '.join(map(str, count)))


input()
nums = list(map(int, input().split()))
count = [0] * 100
for num in nums:
	count[num] += 1
print(' '.join((str(count[x]) for x in range(100))))


d = {}
for i in range(100):
	d[i] = 0
n = input('')
s = input('')
s = s.split(' ')
for i in s:
	if i == '':
		break
	x = int(i)
	d[x] += 1
for i in d:
	print(d[i], end=' ')
print()


input()
x = [int(i) for i in input().split()]
for i in range(100):
	print(x.count(i), end=' ')


from sys import stdin, stdout
from math import sqrt
tokens = stdin.read().split()
n = tokens[0]
numbers = tokens[1:]
times = [0 for x in range(0, 100)]
for x in numbers:
	times[int(x)] += 1
for x in range(0, 100):
	times[x] = str(times[x])
print(' '.join(times))


count = [0] * 100
valid = [str(n) for n in range(100)]
n = int(input())
for k in input().split(' '):
	if k in valid:
		m = int(k)
		count[m] = count[m] + 1
out = ''
for z in range(100):
	out = out + str(count[z]) + ' '
print(out[:-1])


SIZE = 100

def count_sort(L, size):
	out = [0] * size
	for i in L:
		out[i] += 1
	return out
n = int(input())
L = [int(s) for s in input().split()]
print(' '.join([str(i) for i in count_sort(L, SIZE)]))


def g(l, l1):
	for i in l:
		l1[i] += 1
	return l1

def f():
	l = []
	for i in range(100):
		l.append(0)
	return l

def h():
	x = str(input())
	y = x.split()
	l = len(y)
	z = []
	for i in y:
		z.append(int(i))
	return z

def listtostr(l):
	x = str(l[0])
	for i in range(1, len(l)):
		x = x + ' ' + str(l[i])
	return x
n = int(input())
print(listtostr(g(h(), f())))


n = int(input())
ar = list(map(int, input().split()))
tot = [0] * 100
for j in range(0, n):
	temp = ar[j]
	tot[temp] += 1
print(*tot, sep=' ')


import sys

def print_list(data):
	for element in data:
		print(element, end=' ')
	print()
sizeOfList = int(sys.stdin.readline())
data = []
raw = sys.stdin.readline().split()
for index in range(sizeOfList):
	data.append(int(raw[index]))
counter = [0] * 100
for element in data:
	counter[element] += 1
print_list(counter)


import sys
length = int(sys.stdin.readline().strip())
L = list(map(int, sys.stdin.readline().strip().split()))
vals = {}
for i in range(100):
	vals[i] = 0
for item in L:
	vals[item] += 1
ans = ''
for item in vals.values():
	item = repr(item)
	ans += item + ' '
sys.stdout.write(ans)


n = int(input())
ar = map(int, input().split())
counts = 100 * [0]
for x in ar:
	counts[x] += 1
print(' '.join(map(str, counts)))


n = int(input())
ar = [int(v) for v in input().split()]
r = [0] * 100
for item in ar:
	r[item] += 1
print(' '.join([str(v) for v in r]))


size = int(input())
ar = list(map(int, input().split()))

def counter(ar):
	nums = dict(((key, 0) for key in range(0, 100)))
	for num in ar:
		nums[num] += 1
	return nums.values()
print(str(counter(ar)).replace('dict_values', '').replace('(', '').replace('[', '').replace(',', '').replace(']', '').replace(')', ''))


n = int(input())
ar = input().split()
ar = [int(n) for n in ar]
t = [ar.count(n) for n in range(0, 100)]
t = [str(n) for n in t]
print(' '.join(t))


import sys

def mToString(mArray):
	startStr = ''
	for el in mArray:
		startStr = startStr + str(el) + ' '
	if len(startStr) == 0:
		startStr = ' '
	return startStr[:-1]
lines = []
for line in sys.stdin:
	lines.append(line)
n = int(lines[0])
inputArray = list(map(int, lines[1].split()))
outputArray = [0] * 100
for el in inputArray:
	outputArray[el] = outputArray[el] + 1
print(mToString(outputArray))


x = input()
z = input().split()
t = []
for i in range(100):
	if str(i) in z:
		f = z.count(str(i))
		t.append(f)
	else:
		t.append(0)
print(' '.join([str(j) for j in t]))


N = int(input().strip())
ar = list(map(int, input().strip().split()))
count = [0] * 100
for x in ar:
	count[x] += 1
print(' '.join(map(str, count)))


import fileinput

def main():
	lines = []
	for line in fileinput.input():
		lines.append(line)
	numbers = str(lines[1]).split()
	counts = [0] * 100
	for number in numbers:
		counts[int(number)] += 1
	printout = ''
	for count in counts:
		printout += str(count) + ' '
	print(printout)
main()


n = int(input())
ar = list(map(int, str(input()).split()))
counts = [0 for i in range(100)]
for i in range(n):
	counts[ar[i]] += 1
print(' '.join(map(str, counts)))


num = int(input())
A = [0] * 100
ar = [int(c) for c in input().split()]
for i in ar:
	A[i] += 1
for j in A:
	print(j, end=' ')


size = int(input())
assert 100 <= size <= 1000000
numbers = [int(x) for x in input().split()]
counters = {}
counts = ''
for x in range(0, 100):
	counters[x] = 0
for e in numbers:
	counters[e] += 1
for y in counters:
	counts += str(counters[y]) + ' '
print(counts.strip())


import random
n = int(input())
ar = [int(x) for x in input().split()]

def countsort(ar):
	counts = [0] * 100
	for x in ar:
		counts[x] += 1
	return counts
res = countsort(ar)
print(' '.join(map(str, res)))


import sys

def counting(arr, s):
	appearences = {}
	for x in range(100):
		appearences[x] = 0
	for value in arr:
		appearences[value] += 1
	return appearences
size = int(sys.stdin.readline().strip())
array = sys.stdin.readline().strip().split()
array = [int(i) for i in array]
answer = counting(array, len(array))
result = []
for x in range(100):
	result.append(str(answer[x]))
print(' '.join(result))


import sys
N = int(sys.stdin.readline())
occ = [0] * 100
for line in sys.stdin:
	for i in line.split():
		occ[int(i)] += 1
for n in occ:
	print(n, end=' ')


from collections import defaultdict
input()
ar = [int(i) for i in input().split()]

def csort(ar):
	hist = defaultdict(int)
	for i in ar:
		hist[i] += 1
	print(' '.join((str(hist[i]) for i in range(100))))
	sar = []
	for k in hist:
		sar.extend([k] * hist[k])
	return sar
csort(ar)


T = int(input())
array = input().split()
output = []
for i in range(100):
	output.append(array.count(str(i)))
print(' '.join((str(x) for x in output)))


n = int(input())
ar = [int(i) for i in str(input()).split()]
freq = [0] * 100
for i in ar:
	freq[i] += 1
print(' '.join([str(e) for e in freq]))


import sys
N = sys.stdin.readline()
ar = sys.stdin.readline().strip().split()
counts = {}
for r in range(0, 100):
	counts[r] = 0
for a in ar:
	counts[int(a)] += 1
print(' '.join([str(counts[r]) for r in range(0, 100)]))


n = int(input())
count = {}
intList = input().split(' ')
for item in intList:
	count[item] = count.get(item, 0) + 1
for number in range(100):
	print(str(count.get(str(number), 0)) + ' ', end='')


N = int(input())
arr = input().split()
count = dict()
for i in arr:
	if i in count:
		count[i] += 1
	else:
		count[i] = 1
out = ''
for i in range(100):
	if str(i) in count:
		out += str(count[str(i)]) + ' '
	else:
		out += str(0) + ' '
print(out)


n = int(input())
input_list = input().split(' ')
num_list = {}
for i in input_list:
	if i in num_list:
		num_list[i] += 1
	else:
		num_list[i] = 1
for i in range(0, 100):
	i = str(i)
	if i in num_list:
		print(num_list[i], end=' ')
	else:
		print(0, end=' ')


def print_array(a):
	for elem in a:
		print(elem, end=' ')
	print('')
n = int(input())
array = list(map(int, input().split()))
counts = [0] * 100
for elem in array:
	counts[elem] += 1
print_array(counts)


import sys, math, copy
data = sys.stdin.readlines()
a = [int(n) for n in data[1].split()]
c = [a.count(n) for n in range(100)]
print(' '.join([str(k) for k in c]))


count = [0] * 100
n = int(input())
raw_data = input()
data = raw_data.split()
for i in range(0, n):
	count[int(data[i])] = count[int(data[i])] + 1
ans = str(count).strip('[]')
print(ans.replace(',', ''))


N = int(input())
arr = [int(x) for x in input().split()]
base = [0 for i in range(0, 100)]
for i in range(0, N):
	base[arr[i]] = base[arr[i]] + 1
print(' '.join([str(x) for x in base]))


N = int(input())
int_list = [int(x) for x in input().split()]
freq_list = [0 for x in range(100)]
for i in range(N):
	freq_list[int_list[i]] += 1
printstr = str(freq_list[0])
for i in range(1, 100):
	printstr += ' '
	printstr += str(freq_list[i])
print(printstr)


numVals = int(input())
allNums = [0] * 100
allInput = input().split()
for i in range(numVals):
	allNums[int(allInput[i])] += 1
s = ''
for i in allNums:
	s += str(i) + ' '
print(s)


N = int(input())
input_map = list(map(int, input().split()))
counter = [0] * 100
for element in input_map:
	counter[element] += 1
print(' '.join((str(i) for i in counter)))


counter = [int(0) for i in range(100)]
N = int(input())
ar = [int(x) for x in input().split()]
for v in ar:
	counter[v] += 1
print(' '.join((str(x) for x in counter)))


from sys import stdin

def main():
	stdin.readline()
	numbers = list(map(int, stdin.readline().split()))
	frequencies = {}
	for i in numbers:
		if i in frequencies:
			frequencies[i] += 1
		else:
			frequencies[i] = 1
	for i in range(100):
		if i not in frequencies:
			frequencies[i] = 0
		print(frequencies[i], end=' ')
main()


count = input()
nums = list(map(int, input().split()))
counts = [0] * 100
for i in nums:
	counts[i] += 1
for i in counts:
	print(i, end=' ')


counters = [0 for x in range(100)]
n = int(input())
inp = input().split(' ')
for i in range(n):
	index = int(inp[i])
	counters[index] = counters[index] + 1
print(' '.join((str(x) for x in counters)))


n = int(input())
c = [0 for i in range(100)]
l = 0
a = []
while l < n:
	a += input().split()
	l = len(a)
for i in a:
	c[int(i)] += 1
ans = ''
for j in range(len(c)):
	ans += str(c[j]) + ' '
print(ans)


def printList(ar):
	print(' '.join((str(i) for i in ar)))

def countNumbersInList(ar):
	counters = [0 for x in range(100)]
	for i in range(len(ar)):
		num = ar[i]
		counters[num] += 1
	printList(counters)
s = int(input())
ar = [int(i) for i in input().strip().split()]
countNumbersInList(ar)


n = int(input())
a = [int(x) for x in str(input()).split()]
count = [0] * 100
for x in a:
	count[x] += 1
print(' '.join([str(x) for x in count]))


a = int(input())
b = input().split(' ')
c = {}
for i in range(a):
	d = int(b[i])
	if d in c:
		c[d] += 1
	else:
		c[d] = 1
for i in range(100):
	if i in c:
		print(c[i], end=' ')
	else:
		print(0, end=' ')


input()
nums = [int(x) for x in input().split()]
count = [0] * 100
for i in nums:
	count[i] += 1
for i in count:
	print(i, end=' ')


n = int(input())
seq = input().split()
seq = [int(num) for num in seq]
max_number = max(seq)
cnt = [0 for i in range(max_number + 1)]
for num in seq:
	cnt[int(num)] += 1
for num in cnt:
	print(num, end=' ')


l = int(input())
a = list(input())
b = []
for x in range(0, l):
	b.append('')
index = 0
for x in range(0, len(a)):
	if a[x] != ' ':
		b[index] += a[x]
	if a[x] == ' ':
		index += 1
for x in range(0, len(b)):
	b[x] = int(b[x])
ans = [0] * 100
for x in range(l):
	ans[b[x]] += 1
print(' '.join(map(str, ans)))


n = int(input())
ar = list(map(int, input().split()))
c = [0] * 100
for e in ar:
	c[e] += 1
print(' '.join(map(str, c)))


n = int(input())
line = input()
arr = [0] * 100
for x in line.split():
	arr[int(x)] += 1
print(' '.join((str(x) for x in arr)))


from collections import defaultdict
n = int(input())
nbs = [int(i) for i in input().split()]
freq = defaultdict(lambda : 0)
for nb in nbs:
	freq[nb] += 1
print(' '.join([str(freq[i]) for i in range(max(nbs) + 1)]))


def makelistsameline(strnos):
	return list(map(lambda x: int(x), strnos.split()))

def pp(L):
	print(' '.join(map(str, L)))
N = int(input())
ar = makelistsameline(input())
count = dict.fromkeys(range(100), 0)
for x in ar:
	count[x] += 1
pp(list(count.values()))


n = int(input())
counts = [0 for _ in range(100)]
numberList = [int(x) for x in input().split()]
for num in numberList:
	counts[num] += 1
print(' '.join(map(str, counts)))


intlist = [0 for i in range(100)]
n = eval(input())
l = list(map(int, input().split()))
for i in l:
	intlist[i] += 1
print(' '.join(map(str, intlist)))


def sort(l):
	h = {}
	mx = float('-inf')
	for i in l:
		h[i] = h.get(i, 0) + 1
		if i > mx:
			mx = i
	for i in range(mx + 1):
		print(h.get(i, 0), end=' ')
	print('')
n = int(input())
l = [int(x) for x in input().strip().split()]
assert n == len(l)
sort(l)


amount = int(input())
nums = str(input()).split(' ')
count = []
for x in range(0, 100):
	count.append(str(nums.count(str(x))))
print(' '.join(count))


n = int(input())
ar = [int(x) for x in input().split()]
answer = [0] * 100
for x in ar:
	answer[x] += 1
print(' '.join([str(x) for x in answer]))


nombreEntrees = int(input())
ar = [int(i) for i in input().strip().split()]
tableauCompte = [0] * 100
for el in ar:
	tableauCompte[el] += 1
print(' '.join(map(str, tableauCompte)))


size = int(input().strip())
counts = {}
for i in range(100):
	counts[i] = 0
for number in input().strip().split():
	num = int(number)
	counts[num] = counts[num] + 1
countsArr = []
for i in range(100):
	countsArr.append(str(counts[i]))
print(' '.join(countsArr))


N = int(input())
array = [int(i) for i in input().split()]
count = [0] * 100
for num in array:
	count[num] += 1
for j in count:
	print(j, end=' ')


n = int(input())
arr = [int(i) for i in str(input()).split()]
output_arr = [0] * 100
for value in arr:
	output_arr[value] += 1
print(' '.join([str(i) for i in output_arr]))


def CountingSort(ar):
	count_array = [0 for i in range(100)]
	for element in ar:
		count_array[int(element)] = count_array[int(element)] + 1
	return count_array

def PrintArray(ar):
	print_ar = ''
	for i in ar:
		print_ar = print_ar + str(i) + ' '
	print(print_ar)
n = int(input())
ar = [int(i) for i in input().strip().split()]
array = CountingSort(ar)
PrintArray(array)


N = int(input())
ar = [int(i) for i in input().split()]
res = [0] * 100
for val in ar:
	res[val] += 1
print(' '.join([str(i) for i in res]))


(n, ar) = (int(input()), map(int, input().split()))
counts = [0] * 100
for x in ar:
	counts[x] += 1
print(' '.join(map(str, counts)))


def counting_sort(array):
	res_arr = [0 for i in range(100)]
	for a in array:
		res_arr[a] += 1
	print(' '.join(map(str, res_arr)))
N = int(input())
array = [int(i) for i in input().strip().split()]
counting_sort(array)


N = int(input())
ar = list(map(int, input().split()))
count = 0
for i in range(100):
	count = 0
	if i in ar:
		for num in ar:
			if i == num:
				count = count + 1
	print(count, end=' ')


def count(lst):
	out = [0 for _ in range(100)]
	for el in lst:
		out[el] += 1
	return out
n = int(input())
strlst = input()
cc = count([int(el) for el in strlst.split()])
print(' '.join((str(c) for c in cc)))


n = int(input().strip())
ar = [int(i) for i in input().strip().split(' ')]
freq = []
for i in range(100):
	freq.append(0)
for i in ar:
	freq[i] += 1
print(' '.join(map(str, freq)))


input()
import collections
a = map(int, input().split())
ct = collections.Counter(a)
print(*(ct[i] for i in range(100)))


n = int(input())
A = [int(s) for s in input().split()]
m = 100
B = [0 for i in range(m)]
for a in A:
	B[a] += 1
print(' '.join(map(str, B)))


DEV = False
if DEV:
	f = open('test_data.txt', 'r')
	ra_len = int(f.readline().strip())
	ra = [int(i) for i in f.readline().strip().split()]
else:
	ra_len = int(input().strip())
	ra = [int(i) for i in input().strip().split()]
counts = []
for num in range(0, 100, 1):
	counts.append(0)
for num in ra:
	counts[num] += 1
result = ''
for count in counts:
	result += '{0} '.format(count)
print(result)
if DEV:
	f.close()


from collections import Counter
input()
C = Counter(map(int, input().split()))
for i in range(100):
	print(C[i], '', end='')


n = int(input())
ar = [int(number) for number in input().split()]
count = [0] * 100
for number in ar:
	count[number] += 1
print(' '.join(map(str, count)))


t = int(input())
B = [int(x) for x in input().split()]
for i in range(0, 100):
	print(B.count(i), end=' ')


cnt = [0 for i in range(101)]
n = int(input())
l = map(int, input().split())
for i in l:
	cnt[i] += 1
for i in range(100):
	print(cnt[i], end=' ')