forked from OmkarPathak/Data-Structures-using-Python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCounting_sort.py
More file actions
32 lines (25 loc) · 955 Bytes
/
Counting_sort.py
File metadata and controls
32 lines (25 loc) · 955 Bytes
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
def countSort(arr):
# The output character array that will have sorted arr
output = [0 for i in range(256)]
# Create a count array to store count of inidividul
# characters and initialize count array as 0
count = [0 for i in range(256)]
# For storing the resulting answer since the
# string is immutable
ans = ["" for _ in arr]
# Store count of each character
for i in arr:
count[ord(i)] += 1
# Change count[i] so that count[i] now contains actual
# position of this character in output array
for i in range(256):
count[i] += count[i-1]
# Build the output character array
for i in range(len(arr)):
output[count[ord(arr[i])]-1] = arr[i]
count[ord(arr[i])] -= 1
# Copy the output array to arr, so that arr now
# contains sorted characters
for i in range(len(arr)):
ans[i] = output[i]
return ans