Algorithm - Selection Sort

![](

4g.eyYAWeM_mj9ABc8rQ4JuDh3u2zhwVwxAAyBq01-jf7og.JPEG.cdw0424/SE-f747d7e1-b6ca-4e31-a6c5-90c8cda70807.jpg?type=w966)

The Bubble Sort algorithm from the previous article sorted by comparing and swapping adjacent numbers on each pass.

Selection Sort also moves smaller numbers to one side like Bubble Sort, but differs in that it moves one position at a time while tracking the minimum value, and only swaps once per pass.

Because of this, the worst-case time complexity is O(n^2), the same as Bubble Sort, but in practice Selection Sort is roughly 2x faster.

![](

PudNorDSRrWGoIoUZYg.6NUG8NGz0wmm2PvrhoWnXwNgKioQ1OkJxUP39rx8y28g.PNG.cdw0424/image.png?type=w966)

Refer to the comments in the code. You can understand why it's faster by counting the worst-case operations.

![](

C6bsg.DTWYLg3jiLXZ7YHCCUJSS4TUCiDqY39ZDaa7Q3IGDSUg.JPEG.cdw0424/photo-1475137979732-b349acb6b7e3.jpg?type=w966)

For an array of 5 elements, there are 4 passes.

The number of comparisons decreases by 1 each pass.

So it performs 4, 3, 2, 1 comparisons respectively.

That's 10 total comparisons.

Plus, there's a process of swapping the minimum to the front once per pass, resulting in 4 swaps.

So the total is 14 steps.

![](

IWwig.JsuSUtWAvsHAkzAYm7_i9x0bAxnFkFblpA7ZlZCjF9Ag.JPEG.cdw0424/photo-1567254790685-6b6d6abe4689.jpg?type=w966)

For reference, Bubble Sort with 5 elements takes 20 steps.

With 20 elements each:

Selection Sort: 199 steps
Bubble Sort: 380 steps

You can see roughly a 2x difference.