forked from deutranium/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
countingSort.py
37 lines (23 loc) · 1.07 KB
/
countingSort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
'''COUNTINGSORT
Counting sort is a sorting technique based on keys between a specific range.
It works by counting the number of objects having distinct key values.
Then doing some arithmetic to calculate the position of each object in the
output sequence.'''
def countSort(arr):
output = [0 for i in range(256)]
count = [0 for i in range(256)] # Create a count array initialized with 0
ans = ["" for _ in arr] # as strings are immutable
for i in arr:
count[ord(i)] += 1 # position of character in the output array
for i in range(256):
count[i] += count[i-1] # output character array
for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1 # array of sorted charcters
for i in range(len(arr)):
ans[i] = output[i]
return ans
#TEST
arr = "Algorithms"
ans = countSort(arr)
print ("Sorted character array is "+str("".join(ans)))