Sorting Algorithms in Javascript Part 2

#javascript #beginners #algorithms #computerscience

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)

Jon Randy 🎖️ • Oct 5 '20 • Edited

Wouldn't this be simpler?

const swap = (arr, a, b) => { [arr[a], arr[b]] = [arr[b], arr[a]] }

Better still, a version that doesn't mutate the original array:

const swap = (arr, a, b) => {
   let ret = [...arr];
   [ret[a], ret[b]] = [ret[b], ret[a]];
   return ret;
}

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.