JavaScript Sorting Algorithms Explained: Selection Sort -

We are continuing our JavaScript Sorting Algorithms journey with Selection Sort.

Introduction to Selection Sort

As already mentioned – JavaScript Sorting Algorithms series will try to explain and implement different sorting algorithms using JS. After finishing Bubble Sort we are moving onto the next Javascript sorting algorithm – Selection Sort.

Selection Sort is somewhat similar to bubble sort, but instead of first sorting higher values by placing them into correct positions, we first place smaller values into the correct positions. We still iterate through the whole array in (mostly) the same way, but instead of sorting bigger values, we sort smaller ones.

So, how we do this? We need to store the currently smallest value in some kind of a container variable. Then that value can be redeclared depending on the value of other elements (if some element is smaller than the already smallest element in the array).

Pseudocode

Store the first element in the array inside the ‘smallest container variable’
The algorithm will iterate through the array comparing the current element and the current smallest variable on each iteration
The algorithm will update the value of the smallest variable if the current element is smaller than the smallest container variable
If not the algorithm just continues until it reaches the end of the array
The algorithm will then swap the current element and the smallest variable
The algorithm will repeat the process going from step 1. to 5.

Visualization

Let us visualize this algorithm using the inputs [11, 17, 5, 28, 3, 6, 15].

Initially, the smallest value is assigned to the first value in the array (red element). Then the algorithm iterates through elements and compares the smallest value and the current element (green), and if it finds a smaller value it redeclares the smallest value. At the end of each iteration the algorithm swaps the current smallest element with the first element in the iteration, and thus the element is sorted at the appropriate place (changing color to orange).

Implementation

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let smallest = i;
    let j = i + 1;
    for (; j < arr.length; j++) {
      if (arr[j] < arr[smallest]) {
        smallest = j;
      }
    }
    if (i !== smallest) {
      [arr[smallest], arr[i]] = [arr[i], arr[smallest]];
    }
  }
  return arr;
}

selectionSort([11, 17, 5, 28, 3, 6, 15]);

At the start of each outer iteration we set the smallest value to the first value in the array. In the same block (because we use ES6 let declaration) we declare the value j to be i + 1. Then we just go through every element in the array. if we find a smaller value than the current smallest value, then we redeclare the smallest index to be j. In the end of each iteration we just swap the values if there is a smaller value AND it is not equal to the value we started with using – [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]].

Big O complexity

Similar to bubble sort, the average Big O of selection sort is O(n²) because again we compare every element to every other element in the array. If the number of elements grow, the runtime will grow exponentially. Selection sort might be more useful than bubble sort when we want to use an algorithm that reduces swapping, because the algorithm only makes one swap, at the end of each loop, compared to bubble sort which can have more swaps.

Conclusion

We will conclude this part of JavaScript Sorting Algorithms with Selection Sort here! Please check the blog for more tech articles.

Additionally, if you want to check up on other sorting algorithms you can do it here:

Facebook Tweet Pin LinkedIn

JavaScript Sorting Algorithms Explained: Selection Sort