Implementation of Bucket Sort in Python
Below is the implementation of bucket sort in python:
def insertion_sort(bucket):
for i in range(1, len(bucket)):
key = bucket[i]
j = i - 1
while j >= 0 and bucket[j] > key:
bucket[j + 1] = bucket[j]
j -= 1
bucket[j + 1] = key
def bucket_sort(arr):
n = len(arr)
buckets = [[] for _ in range(n)]
# Put array elements in different buckets
for num in arr:
bi = int(n * num)
buckets[bi].append(num)
# Sort individual buckets using insertion sort
for bucket in buckets:
insertion_sort(bucket)
# Concatenate all buckets into arr[]
index = 0
for bucket in buckets:
for num in bucket:
arr[index] = num
index += 1
arr = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
bucket_sort(arr)
print("Sorted array is:")
print(" ".join(map(str, arr)))
Output
Sorted array is: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94
Bucket Sort in Python
Bucket sort is a sorting technique that involves dividing elements into various groups, or buckets. These buckets are formed by uniformly distributing the elements. Once the elements are divided into buckets, they can be sorted using any other sorting algorithm. Finally, the sorted elements are gathered together in an ordered fashion.