This is a Python program to implement bucket sort.

The program sorts a list by bucket sort.

1. Create a function bucket_sort that takes a list as argument.

2. Inside the function set largest to the maximum element in the list and set length equal to the length of the list.

3. Set size = largest/length.

4. Create a list of empty lists and assign it to buckets.

5. Create a loop with loop variable i that iterates from 0 to the length of the list – 1.

6. In each iteration, determine to which bucket alist[i] belongs. This is done by taking the floor of alist[i]/size and using the answer as the index of the bucket. If the answer equals length, then alist[i] is placed in the last bucket, that is bucket[length -1 ].

7. Perform insertion sort on each bucket.

8. Concatenate the buckets to create the sorted list and return it.

9. Create a function insertion_sort that takes a list as argument.

10. Inside the function create a loop with a loop variable i that counts from 1 to the length of the list – 1.

11. Set temp equal to the element at index i.

12. Set j equal to i – 1.

13. Create a while loop that runs as long as j is non-negative and temp is smaller than the element at index j.

14. Inside the while loop, set the element at index j + 1 equal to the element at index j and decrement j.

15. After the while loop finishes, set the element at index j + 1 equal to temp.

Here is the source code of a Python program to implement bucket sort. The program output is shown below.

def bucket_sort(alist): largest = max(alist) length = len(alist) size = largest/length buckets = [[] for _ in range(length)] for i in range(length): j = int(alist[i]/size) if j != length: buckets[j].append(alist[i]) else: buckets[length - 1].append(alist[i]) for i in range(length): insertion_sort(buckets[i]) result = [] for i in range(length): result = result + buckets[i] return result def insertion_sort(alist): for i in range(1, len(alist)): temp = alist[i] j = i - 1 while (j >= 0 and temp < alist[j]): alist[j + 1] = alist[j] j = j - 1 alist[j + 1] = temp alist = input('Enter the list of (nonnegative) numbers: ').split() alist = [int(x) for x in alist] sorted_list = bucket_sort(alist) print('Sorted list: ', end='') print(sorted_list)

1. The user is prompted to enter a list of numbers.

2. The list is passed to the bucket_sort function and the sorted list is returned.

3. The sorted list is displayed.

Case 1: Enter the list of (nonnegative) numbers: 2 1 5 10 3 5 7 Sorted list: [1, 2, 3, 5, 5, 7, 10] Case 2: Enter the list of (nonnegative) numbers: 8 7 5 3 2 1 Sorted list: [1, 2, 3, 5, 7, 8] Case 3: Enter the list of (nonnegative) numbers: 5 Sorted list: [5]

**Sanfoundry Global Education & Learning Series – Python Programs.**

To practice all Python programs, __here is complete set of 150+ Python Problems and Solutions__.