I've finished the uni - there is no way in hell I would still need data structures and algorithms, right? (that's what I thought, I forgot almost everything to make more room in my brain for football trivia and stupid memes :)) Until I quite embarrassed myself on one interview, and because of that I spent quite some time re-learning this stuff, which landed me a better job than the one I had. (YEAAH!) Again, check my blog if you wish! This is second part in our (cue the SSSR music) JavaScript Algorithm Series.

Introduction

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.

The question is HOW? 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

1. Store the first element in the array inside the 'smallest container variable'
2. The algorithm will iterate through the array comparing the current element and the current smallest variable on each iteration
3. The algorithm will update the value of the smallest variable if the current element is smaller than the smallest container variable
4. If not the algorithm just continues until it reaches the end of the array
5. The algorithm will then swap the current element and the smallest variable
6. 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]. Vizualization has been done using this amazing free tool called visualgo.

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 that value. At the end of each iteration the algorithm swaps the current smallest element with the first element in the iteration, and thus the currently smallest element is sorted in 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]] - thanks ES6.

Big O Complexity

Similar to bubble sort, the average Big O of selection sort is O(n2) 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 swaps once - at the end of every loop.

Conclusion

That's it! The next one we'll talk about is Insertion Sort, so please stay tuned, and happy coding :).