|
13 | 13 | # Time Complexity of Solution: |
14 | 14 | # Best Case O(n); Average Case O(n); Worst Case O(n) |
15 | 15 |
|
16 | | -from __future__importprint_function |
17 | | -frominsertion_sortimportinsertion_sort |
18 | | -importmath |
19 | | - |
20 | | -DEFAULT_BUCKET_SIZE=5 |
21 | | - |
22 | | -defbucketSort(myList,bucketSize=DEFAULT_BUCKET_SIZE): |
23 | | -if(len(myList)==0): |
24 | | -print('You don\'t have any elements in array!') |
25 | | - |
26 | | -minValue=myList[0] |
27 | | -maxValue=myList[0] |
28 | | - |
29 | | -# For finding minimum and maximum values |
30 | | -foriinrange(0,len(myList)): |
31 | | -ifmyList[i]<minValue: |
32 | | -minValue=myList[i] |
33 | | -elifmyList[i]>maxValue: |
34 | | -maxValue=myList[i] |
35 | | - |
36 | | -# Initialize buckets |
37 | | -bucketCount=math.floor((maxValue-minValue)/bucketSize)+1 |
38 | | -buckets= [] |
39 | | -foriinrange(0,bucketCount): |
| 16 | +DEFAULT_BUCKET_SIZE=5 |
| 17 | +defbucket_sort(my_list,bucket_size=DEFAULT_BUCKET_SIZE): |
| 18 | +if(my_list==0): |
| 19 | +print("you don't have any elements in array!") |
| 20 | + |
| 21 | + |
| 22 | +min_value=min(my_list) |
| 23 | +max_value=max(my_list) |
| 24 | + |
| 25 | +bucket_count=(max_value-min_value)//bucket_size+1 |
| 26 | +buckets=[] |
| 27 | +foriinrange(bucket_count): |
40 | 28 | buckets.append([]) |
| 29 | +foriinrange(len(my_list)): |
| 30 | +buckets[(my_list[i]-min_value)//bucket_size].append(my_list[i]) |
| 31 | + |
| 32 | + |
| 33 | +sorted_array=[] |
| 34 | +foriinrange(len(buckets)): |
| 35 | +buckets[i].sort() |
| 36 | +forjinrange(len(buckets[i])): |
| 37 | +sorted_array.append(buckets[i][j]) |
| 38 | +returnsorted_array |
41 | 39 |
|
42 | | -# For putting values in buckets |
43 | | -foriinrange(0,len(myList)): |
44 | | -buckets[math.floor((myList[i]-minValue)/bucketSize)].append(myList[i]) |
45 | 40 |
|
46 | | -# Sort buckets and place back into input array |
47 | | -sortedArray= [] |
48 | | -foriinrange(0,len(buckets)): |
49 | | -insertion_sort(buckets[i]) |
50 | | -forjinrange(0,len(buckets[i])): |
51 | | -sortedArray.append(buckets[i][j]) |
52 | 41 |
|
53 | | -returnsortedArray |
54 | 42 |
|
55 | | -if__name__=='__main__': |
56 | | -sortedArray=bucketSort([12,23,4,5,3,2,12,81,56,95]) |
57 | | -print(sortedArray) |
| 43 | +#test |
| 44 | +#besd on python 3.7.3 |
| 45 | +user_input=input('Enter numbers separated by a comma:').strip() |
| 46 | +unsorted=[int(item)foriteminuser_input.split(',')] |
| 47 | +print(bucket_sort(unsorted)) |
