The sorting is usually done by using an algorithm of a second type…
Yes…you will need to know another type of sorting algorithm. It sounds scary but don't let that deter you away from learning more. Later you will see that I used insertion_sort.
I've learned many different types of sorting algorithms but for me, bucket sort was one of the most interesting. It might be because personally I like buckets or it might be that I have slight OCD where I like to organize large amounts of things into smaller amounts of things and then sort them out.
I find this handy when I'm folding clothes. I usually wait until I have absolutely nothing to wear before I wash clothes. So you can image the large mountain of clothes I need to fold after washing the laundry. (To me, folding clothes is the worst chore to do. Even if I wash small amounts of clothes, I usually wait until the clean pile adds up before folding and putting everything away. It's a really bad habit it break)
I begin the folding by sorting all of the clothes into different piles: shirts to be folded, shirts/sweaters to hang in the closet, socks and under garments, and pants. Then I make my way through the piles and organize them so they are ready to be put in their appropriate place. I'm not entirely sure but I think that is the most time efficient way of doing it.
Anyways, let's go into more detail about what a bucket sort algorithm is and why might it be that we should use it.
As I've mentioned before, a bucket sort algorithm assigns elements into a bucket. We are given an unsorted array of numbers. Given these elements, we want to implement an equation that will help us sort the elements into their respective buckets to await further sorting. The purpose of sorting elements into smaller buckets is to make the sorting part easier, just as in my method for sorting clothes. Which is why this is an important step.The equation we use is to find the size. With the calculated size, we will divide each element by this size to begin sorting the elements into buckets.
Step 1: Calculate Size
To calculate size, we need to find the following: the largest value and the length of the array. Once those are found, divide the largest value by the length.
In this example our largest value is: 0.36
The length of the array is 6
Size = largest_value / length
From our calculations, the size is 0.06
How to implement this into Python code:
Use the built-in python function max() to find the largest value. Store the largest value into a meaningful variable name.
Step 2: Create a List of Empty Buckets
This list of buckets will soon be populated with our values. To find which bucket the values go to, we need to take our element and divide it by the size that we calculated previously.
Once we've created our list of empty buckets, we can continue with dividing the elements by the size. We can see the calculations below. Note: the quotients are floats (also known as integers or numbers with decimal values).
We see that 0.16/0.06 is 2.66. We round the floats up so this will go to bucket #2.
Step 3: Sort Each Bucket
Now all of the elements are sorted into smaller buckets. Our next job is sort each of the buckets that contain elements. As we can see, we only have 3 buckets that have elements. This is where we would use the second sorting algorithm. You can view this link here to find more information about insertion sort. This algorithm is used to move elements into ascending order from left to right.
Once the buckets are in order, we will concatenate all of the sorted buckets together into one sorted list. Here is the implementation of the bucket sort algorithm:
Quick Recap of the bucket sort algorithm:
- Create empty buckets
- Calculate the size to determine where the elements are placed
- Sort the buckets
- Concatenate the sorted buckets together