# Selection sort

###
James Robb
*Updated on *
・2 min read

Algorithms (7 Part Series)

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.

Algorithms (7 Part Series)