It's been a couple of weeks since I wrote my last post on sorting algorithms and I think it's finally time to revisit the topic. In this post I'll be covering additional sorting algorithms that are more uncommon than the ones I covered in my first post.
In this article I'm going to cover:
- Selection Sort
- Bucket Sort
- Counting Sort
Helper Methods
Just like in my first post, we're going to be doing a lot of swapping of elements. It makes sense to create some helper methods that can be used in our sorting methods.
Selection Sort
Selection sort works by dividing the input array into a sorted and unsorted list. The sorted list begins empty and while the unsorted begins as the initial array. We continuously loop through the array to find the smallest element and add that element to the sorted list. This repeats until the entire array is sorted.
Runtime: O(n^2) to O(n^2)
Bucket Sort
Bucket sort works by distributing the elements of the input array into different sections or buckets. The elements are then sorted with a different sorting method, most commonly selection sort. Bucket sort is much faster than solely using selection sort due to the strategic placement of elements into buckets at the cost of additional memory use.
Runtime: O(n+k) to O(n^2)
Counting Sort
Counting sort is unique in that it doesn't do any comparing between it's elements. Instead counting sort counts the number of elements having distinct key values. From there it uses arithmetic to calculate the position of each element. The main caveat of counting sort is that we need to know the min and max elements in the input array.
Runtime: O(n)
Thanks for readying! I intent to also cover heap sorting in a future post but wanted to cover heap data structures before getting to that.
The code for this lesson can be found here.
Top comments (3)
Wouldn't this be simpler?
Better still, a version that doesn't mutate the original array:
Also, your counting sort function both mutates and returns the original array whilst your bucket sort array returns a new array, leaving the original untouched (better). This code is somewhat confused - better to stick with either mutating variables or not, don't mix the two.
These are great suggestions! Thanks for taking the time to reply. Time to make some edits :)
Please excuse me my curiosity, why screenshots, not MD code snippets? See this quite frequently on DEV.to; perhaps I'm missing something.