Python Program to Implement Bucket Sort

This is a Python program to implement bucket sort.

Problem Description

The program sorts a list by bucket sort.

Problem Solution

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.

Program/Source Code

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[length - 1].append(alist[i])
    for i in range(length):
    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='')
Program Explanation

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.

Runtime Test Cases
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.