Selection sort
Tags: algorithms, sorting, javascript, computerscience
Published: 2020-01-15 01:19:12

Selection sort is another comparison-based algorithm like [Bubble Sort](https://dev.to/jamesrweb/bubble-sort-3iid). 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.

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

![Selection Sort Algorithm Visualisation](https://i0.wp.com/algorithms.tutorialhorizon.com/files/2019/01/Selection-Sort-Gif.gif?zoom=1.25&fit=300%2C214&ssl=1)

## Use Case and Performance

[Selection sort depends on the same factors as Bubble Sort](https://dev.to/jamesrweb/bubble-sort-3iid#use-case-and-performance) and like Bubble Sort, it also has a [Big O time complexity](https://en.wikipedia.org/wiki/Big_O_notation) 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](https://en.wikipedia.org/wiki/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.