forked from OmkarPathak/pygorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbucket_sort.py
More file actions
83 lines (66 loc) · 2.02 KB
/
bucket_sort.py
File metadata and controls
83 lines (66 loc) · 2.02 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
"""
Author: OMKAR PATHAK
Created On: 31st July 2017
- Best O(n)
- Average O(n)
- Worst O(n)
"""
import math
from pygorithm.sorting import insertion_sort
import inspect
def sort(_list, bucket_size=5):
"""
bucket sort algorithm
:param _list: list of values to sort
:param bucket_size: Size of the bucket
:return: sorted values
"""
string = False
if len(_list) == 0:
# print("You don\'t have any elements in array!")
raise ValueError("Array can not be empty.")
elif all(isinstance(element, str) for element in _list):
string = True
_list = [ord(element) for element in _list]
min_value = _list[0]
max_value = _list[0]
# For finding minimum and maximum values
for i in range(0, len(_list)):
if _list[i] < min_value:
min_value = _list[i]
elif _list[i] > max_value:
max_value = _list[i]
# Initialize buckets
bucket_count = math.floor((max_value - min_value) / bucket_size) + 1
buckets = []
for i in range(0, int(bucket_count)):
buckets.append([])
# For putting values in buckets
for i in range(0, len(_list)):
# TODO: floor expects floats but could be receiving int or slice
buckets[math.floor(float((_list[i] - min_value) / bucket_size))].append(_list[i])
# Sort buckets and place back into input array
sorted_array = []
for i in range(0, len(buckets)):
insertion_sort.sort(buckets[i])
for j in range(0, len(buckets[i])):
sorted_array.append(buckets[i][j])
if string:
return [chr(element) for element in sorted_array]
else:
return sorted_array
# TODO: Are these necessary?
def time_complexities():
"""
Return information on functions
time complexity
:return: string
"""
return "Best Case: O(n), Average Case: O(n), Worst Case: O(n)"
def get_code():
"""
easily retrieve the source code
of the sort function
:return: source code
"""
return inspect.getsource(sort)