loading...

Sorting Algorithms in Javascript Part 2

123jackcole profile image Jack Cole Updated on ・2 min read

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.

Helper 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.

Selection

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.

Bucket

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.

Count

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.

Discussion

pic
Editor guide
Collapse
jonrandy profile image
Jon Randy

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.

Collapse
123jackcole profile image
Jack Cole Author

These are great suggestions! Thanks for taking the time to reply. Time to make some edits :)

Collapse
alekseiberezkin profile image
Aleksei Berezkin

Please excuse me my curiosity, why screenshots, not MD code snippets? See this quite frequently on DEV.to; perhaps I'm missing something.