Selection Sort Algorithm 101

Implement the Selection Sort Algorithm in JavaScript

Photo by Greg Jeanneau on Unsplash

Introduction

We are going to review the high level mechanics of a Selection Sort Algorithm (SSA) and then dive into 3 different implementations using JavaScript.

The general idea behind an SSA is to scan through a list of integers, find the smallest element, move it to the front of the list and repeat this process using the next element in the list.

Here is a step-by-step example that highlights how this actually happens:

array --> [4,1,5,2]
index -->  0,1,2,3
1. Is the element at index 0 [4] > than the element at index 1 [1]
2. Yes.
3. Swap the numbers and continue the scan.
4. Updated array [1,4,5,2]
5. Is the element at index 0 [1] > than the element at index 2 [5]
6. No.
7. Continue scan.
8. Is the element at index 0 [1] > than the element at index 3 [2]
9. No.
10. Restart the loop at index 1.
11. Is the element at index 1 [4] > than the element at index 2 [5]
12. No.
13. Continue scan.
14. Is the element at index 1 [4] > than the element at index 3 [2]
15. Yes.
16. Swap the numbers and continue the scan.
17. Updated array [1,2,5,4]
18. Restart the loop at index 2.
19. Is the element at index 2 [5] > than the element at index 3 [4]
20. Yes. 
21. Swap the numbers.
22. Sorted array [1,2,4,5]

Ok, so hopefully you get the idea that this algorithm compares the entire array against a single element for each loop. It seeks to swap elements that are out of order. After a complete scan the array is sorted!

Implementations

We are going to implement 3 solutions to the SSA in JavaScript. The first 2 will show off iterative approaches and the last will use recursion.

Before we get started, let’s are going to build a helper function that will be utilized by all three implementations. This swap function will swap 2 elements found in the array (in-place).

Swap Function

const swap = (array, i, j) => {
  let temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

Iterative Function 1

Our first iterative implementation scans through an input array for the smallest integer compared to the first element and then pushes that element to a new array. It continues this looping cycle until the new array is populated with all the sorted values from the input array. This implementation utilizes a bit more memory than other Selection Sort functions because it creates a new array to hold the sorted values. But it achieves our goal nonetheless.

Here are the details:

1. Create an empty array to hold the final values and an empty variable to keep track of the smallest value in the array.
2. Initiate a while loop that will continue to run until it hits a base case
3. Loop through the array, if the first value in the array is greater than the next element in the array being compared swap those values.
4. After the smallest value is attached to the beginning of the input array remove that element from the array and push it to the result array.
5. Once the input array has no length, return the result array. (base case)

const selectionSort = (array) => {
  let result = [];
  let smallest;
  while (true) {
    for (let i = 0; i < array.length; i++) {
      if (array[0] >= array[i + 1]) {
        swap(array, 0, i + 1);
      }
    }
    
    smallest = array.shift();
    result.push(smallest);
   
    if (!array.length) return result;
  }
};

Iterative Function 2

The second iterative implementation is a little more straight forward in its approach. This function uses a pattern that resembles a more traditional brute-force approach and is easier to understand on first glance. Unlike the previous version, this implementation sorts the array in-place, without pushing values to a newly created array.

Here is a walkthrough of the code:

1. Initiate the outer loop of the entire array.
2. Create a minIndex variable that holds the index of the smallest integer in the array.
3. Initiate an inner loop of which scans the array starting at the index adjacent to the the minIndex(if the outer loop index was 2, the inner loop would be 2 + 1 = 3).
4. We compare the value at the outer loop index to each value scanned in the inner loop. If the outer loop value is greater than the inner loop value we reassign the minIndex to the inner loop index.
5. If the minIndex has changed then we know that the smallest integer in the array is not at the i index. So we swap those values to reorder the array.
6. The outer loop increments forward and we repeat the process until the entire array is sorted.

const selectionSort3 = (array) => {
  for (let i = 0; i < array.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[minIndex] > array[j]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      swap(array, minIndex, i)
    }
  }
  return array;
};

Recursive Function

The recursive implementation works in essentially the same way as the iterative approaches but it uses recursion in place of the outer for loop. This function also takes a second input that keeps track of the current index. The base case that ends the recursive loop is triggered when the current index is equal to the array length.

This is also an interesting implementation because it doesn’t actually return anything. The recursive solution alters the array in place and is more suited to OOP style programming. As a result, it is more efficient with memory usage than its iterative counterparts.

Here is a walkthrough of the code:

1. Create a base case that exits when the startIndex === to the array.length.
2. Initialize a for loop that scans the array starting from the startIndex parameter.
3. if the value at the startIndex is less than another value in the array swap those values in place.
4. When the swaps are finished increment the startIndex and recursively call the the function again with the updated parameters.

const selectionSort2 = (array, startIndex) => {
  
  // Base case
  if (startIndex === array.length) return;
  for (let i = startIndex + 1; i < array.length; i++) {
    if (array[startIndex] > array[i]) {
      swap(array, startIndex, i);
    }
  }
  startIndex++
  selectionSort2(array, startIndex)
};

Conclusion

Bam we did it! Ok, for anyone interested in the time-complexity of the SSA, you might be disappointed... In the best and worst case scenario it has a time-complexity of O(n²). As I mentioned earlier, the recursive approach is slightly better at using memory efficiently but its time-complexity remains the same as the iterative implementations that use nested loops.

For the full code checkout my GitHub —

twjsanderson/selectionSort

Thanks for reading!

Sources

Here are few sources that you can use to solidify your knowledge:

A Great Article on the SSA by Kyle Jenson —

Javascript Algorithms — Selection Sort

A Straight Forward Description on GeeksForGeeks —

Selection Sort - GeeksforGeeks

A note from JavaScript In Plain English

We have launched three new publications! Show some love for our new publications by following them: AI in Plain English, UX in Plain English, Python in Plain English — thank you and keep learning!

We are also always interested in helping to promote quality content. If you have an article that you would like to submit to any of our publications, send us an email at submissions@plainenglish.io with your Medium username and we will get you added as a writer. Also let us know which publication/s you want to be added to.