forked from OmkarPathak/pygorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcounting_sort.py
More file actions
37 lines (28 loc) · 884 Bytes
/
counting_sort.py
File metadata and controls
37 lines (28 loc) · 884 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
33
34
35
36
37
# Author: OMKAR PATHAK
# Created On: 31st July 2017
# Best = Average = Worst = O(n + k)
# counting sort algorithm
def sort(myList):
try:
maxValue = 0
for i in range(len(myList)):
if myList[i] > maxValue:
maxValue = myList[i]
buckets = [0] * (maxValue + 1)
for i in myList:
buckets[i] += 1
i = 0
for j in range(maxValue + 1):
for a in range(buckets[j]):
myList[i] = j
i += 1
return myList
except TypeError:
print('Counting Sort can only be applied to integers')
# time complexities
def time_complexities():
return '''Best Case: O(n + k), Average Case: O(n + k), Worst Case: O(n + k)'''
# easily retrieve the source code of the sort function
def get_code():
import inspect
return inspect.getsource(sort)