Bucket sort is constructed of two main parts, the hash and sort. The hash is the way that the information in the sorted array can be accessed in O(1) time. This is important because it allows the data to be easily accessed and changed quickly. The sort takes the smaller parts of the hash and sorts them thus allowing for much fewer data to be compared.
THE BUCKET
The bucket is the part that sorts the data and allows for easy access. Using a has is the simplest way to achieve this. Create an array that is the size of the given array and place the data into it based on its info.
def bucketSort(x):
arr = []
slot_num = 10 # 10 means 10 slots, each
# slot's size is 0.1
for i in range(slot_num):
arr.append([])# Put array elements in different buckets
for j in x:
index = int(slot_num * j)
arr[index].append(j)
This function only works for elements that are between 0 and 1. It takes the floating-point and changes it to an int which correlates to the index in the array.
THE SORT
We are going to use a simple insertion sort to sort the different indices of the bucket.
def insertionSort(b):
for i in range(1, len(b)):
up = b[i]
j = i - 1
while j >= 0 and b[j] > up:
b[j + 1] = b[j]
j -= 1 b[j + 1] = up return b
PUTTING IT TOGETHER
Now that we have all the parts connecting it all is simple. All we need to do is take the sort of each section of the bucket and then grab the sorted arrays out in order.
def insertionSort(b):
for i in range(1, len(b)):
up = b[i]
j = i - 1
while j >= 0 and b[j] > up:
b[j + 1] = b[j]
j -= 1 b[j + 1] = up return bdef bucketSort(x):
arr = []
slot_num = 10 # 10 means 10 slots, each
# slot's size is 0.1
for i in range(slot_num):
arr.append([]) # Put array elements in different buckets
for j in x:
index = int(slot_num * j)
arr[index].append(j)
# Sort individual buckets
for i in range(slot_num):
arr[i] = insertionSort(arr[i]) # concatenate the result
k = 0
for i in range(slot_num):
for j in range(len(arr[i])):
x[k] = arr[i][j]
k += 1
return x
