Selection sort

Selection sort is another comparison-based algorithm like Bubble Sort. The difference is that with bubble sort, each element and its adjacent element are compared and swapped if needed. Selection sort works instead by selecting the element using a forward or backwards lookup (depending on sort direction) and swapping that particular element with the current element.

Implementation

Below we can see an example implementation of selection sort using JavaScript.

function selectionSort(input) {
  const output = [...input];
  const length = output.length;

  for(let outer = 0; outer < length; outer++) {
    let low = outer;

    for (let inner = outer + 1; inner < length; inner++) {
      if (output[inner] < output[low]) {
        low = inner;
      }
    }

    if (output[outer] > output[low]) {
      const tmp = output[outer];
      output[outer] = output[low];
      output[low] = tmp;
    }
  }

  return output;
}

In this implementation we loop the array which is to be sorted into a new array which initially contains the items of the input array, this is assigned to the variable output. On each iteration, we loop from the current elements adjacent element forward and look ahead for a value that is lower than the current one, if we don't find one, the inner loop continues until it is complete. If we do find a value that is less than the current one, we set the low variable equal to that index. Once the inner loop completes we compare the current index to the low indexes value and if the current item is larger, we swap the two.

Use Case and Performance

Selection sort depends on the same factors as Bubble Sort and like Bubble Sort, it also has a Big O time complexity of O(n²) on average. This means that the time it takes to run the algorithm is the square of the size of the input array, otherwise known as Quadratic Time.

Let's look at some example runtimes from given input sizes:

Input size	Time complexity (Big O)
10	O(10²) = O(100)
100	O(100²) = O(10,000)
1000	O(1,000²) = O(1,000,000)

Conclusions

Selection sort suffers and succeeds in similar areas to bubble sort but there are some key differences, namely:

Area of comparison	Bubble sort	Selection sort
What it does?	Adjacent element is compared and swapped	Smallest element is selected and swapped with the current element
Best case performance?	O(n)	O(n²)
Average performance?	O(n²)	O(n²)
Efficiency	Inefficient	Ok when compared to bubble sort
Stable	Yes	No
Method	Exchanging	Selection
Speed	Slow	Fast when compared to bubble sort

Selection sort is a good alternative to bubble sort for sorting small to mid-size arrays as it can be faster and a little more efficient with a linear and predicatable performance signature of O(n²) which bubble sort will also give you on the average, although, bubble sort is more stable with a potentially better time complexity when under the right conditions.