BUCKET SORT

This blog entry is in regards to a kind of sorting Algorithm which is called Bucket sort. In this, I will clarify what Bucket Sort is, the manner by which Bucket Sort is related with Algorithms its time complexity, attempt to explain Bucket Sort bit by bit by giving an example and also about its pro’s and con’s.

What is bucket sort?

1. Bucket Sort is an arranging(sorting) algorithm, which is generally utilized in computer science.
2. It is also called bin sort.
3. It is an illustration of a non-comparison sort(like radix sort and counting sort) so it can sort an array without making any comparison.

How does bucket sort works?

Bucket Sort works by disseminating the components of an array into the various buckets. Each bucket is then arranged independently, either utilizing an alternate arranging(sorting) algorithm or by recursively applying the bucket sorting algorithm.

Source: https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.programiz.com%2Fdsa%2Fbucket-sort&psig=AOvVaw3zA-Blg2DDKCM5zrd811-v&ust=1616491631414000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCPDk_t3Kw-8CFQAAAAAdAAAAABAD

Steps for its working:

1. We have an array ‘A’ with ‘N’ number of elements.
2. Then we will create a new array named ‘B’ with the size ‘N-1'.
3. Then we will create a loop through the original array and put each object in a bucket.
4. Then we will sort each of the non-empty buckets using another sorting algorithm(generally by using insertion sort or quick sort).
5. After that, finally, the buckets are concatenated together in order and we get our sorted array.

Rough code for understanding:

BUCKET SORT [A]

Let B[0…….n-1] be a new array.

n= length[A]

For i=0 to n-1

Make B[i] an empty list

For i=1 to n-1

Do insert A[i] into list B[ |n A[i]| ]

For i=0 to n-1

Do sort list B[i] with Insertion sort

Concatenate list B[0],B[1],…………,B[n-1] together in order.

Example:

Step 1. Let us take an array A which contains the following elements as represented in the above given picture.

Step 2. Since array A has 6 elements in it, we have created an array B from 0 to n-1 about which we have mentioned in the rough code line 2.

Step 3. After that, we have started inserting the elements into the buckets by using B[|nA[i]|] process.

Step 4. Follow the similar procedure for the next element also.

Step 5. Follow the above steps similarly for the rest 4 elements of array A and we will get all the elements into the buckets.

Step 6. Then according to the algorithm using insertion sort on array B to get each bucket sorted.

Step 7. After applying insertion sort concatenate the buckets to get the final sorted array.

Bucket Sort code:

Code:

Reference: https://www.geeksforgeeks.org/bucket-sort-2/

Output:

Bucket sort review:

1. Assumption: input is uniformly distributed across a range.
2. Basic idea: Partition the range into a fixed number of buckets.
3. Toss each element into its appropriate bucket.
4. Sort each bucket.
5. Bucket sort can be exceptionally fast because of the way elements are assigned to buckets, typically using an array where the index is the value.
6. This means that more auxiliary memory is required for the buckets at the cost of running time than more comparison sorts.

The time complexity of Bucket sort:

Source: https://www.google.com/url?sa=i&url=https%3A%2F%2Fsoshace.com%2F10-sorting-algorithms-interview-questions-theory-and-practice-for-2019%2F&psig=AOvVaw0Fb2kpql6rT-LVYYuDhUe5&ust=1616499369221000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCNj02cnnw-8CFQAAAAAdAAAAABAQ

In addition, the Time complexity of bucket sort is affected by various factors. These include algorithms implemented for sorting individual buckets, the number of buckets used, and the distribution of input. It does not depend on the input value. It can be either positive or negative or zero.

This algorithm also has some pros and cons as mentioned below:

PROS:

1. Fast
2. Asymptotically fast (i.e., O(n) when the distribution is uniform).
3. Simple to code and good for a rough sort.

CONS:

1. Doesn’t sort in place (In place: An in-place algorithm is an algorithm that does not need an extra space and produces an output in the same memory that contains the data by transforming the input ‘in-place’. However, a small constant extra space used for variables is allowed.)

For more details regarding In place algorithm please refer to the following mentioned link:

In-Place Algorithm - GeeksforGeeks

Additional information:

1. Bucket sort works by distributing the array elements into a number of buckets. So bucket sort is most efficient in the case when the input is uniformly distributed.
2. Pigeonhole sort is a particular case of bucket sort. Bucket sort is also closely related to MSD radix sort.
3. Bucket sort is not necessarily a stable sorting algorithm. This is because its stability depends on the stability of the algorithm that we have used to sort the individual buckets.

Conclusions:

If you know the range of the elements, the bucket sort is quite effective, with a time complexity of only O(n+k). Simultaneously, there is a significant downside, since it is an absolute necessity to know the greatest elements. It is a distribution sort and a cousin of radix sort.

References:

1. https://www.geeksforgeeks.org/bucket-sort-2/
2. https://www.programiz.com/dsa/bucket-sort
3. https://www.javatpoint.com/daa-bucket-sort
4. https://www.tutorialspoint.com/Bucket-Sort
5. https://web.cse.ohio-state.edu/~crawfis.3/cse680/Slides/CSE680-08LinearSorting.pdf
6. https://www.sanfoundry.com/bucket-sort-uniform-keys-multiple-choice-questions-answers-mcqs/