Sorting Algorithms Studies: Selection Sort

After some hiatus, let’s continue with the Sorting Algorithms Studies series. Let’s talk about Selection Sort.

This algorithm showcases a very natural way to order things, one that you probably already used yourself: repeatedly finding the lowest value, and putting it at the start of the list.

Explanation

This algorithm works by, starting at the first element of the list, repeatedly comparing the current value with the next value, searching for the lowest value - or the highest, if the order is decrescent -, until the end of the elements of the current iteration. When the inner loop ends, the value that was identified as being the lowest - or the highest, if the order is decrescent -, is placed at the start of the list. Having provided the clarifications, from now on this article will focus on the crescent order implementation. After the end of the last inner loop, the algorithm starts a new inner loop, excluding the value that was just swapped, and repeats the same procedure above.

Structure

It is comprised by two nested loops:

  • The outer one loops amongst the numbers that comprise the range between 0 and the size of the array, minus 1. Example: if the array has size 5, the outer loop will loop from 0 to 4. Let’s call the number of the outer loop x.
  • The inner loop is the one that actually makes the comparisons and swaps. It loops amongst the numbers that comprise the range between 0 plus the number of the outer loop (x) and the length of the array, minus 1. Example: if the array has size 5, the inner loop will loop from 0 to 4 on the first outer loop, 1 to 4 in the second outer loop, and so on. Let’s call the number of the inner loop y.
  • For each y in the inner loop, it compares the element on the index y with the element on the index y + 1, searching for the element with the lowest value, placing its index in an auxiliary value. Let’s call it swap_index.
  • At the end of the inner loop, it swaps the element on the index x with the element in the index swap_index.

Also, there is an Selection Sort implementation with a minor optimization. Instead of just looking for the lowest value at each loop, it also looks for the highest value, making two swaps per loop. And, as each loop progresses, the range of elements to be compared by the next loop diminishes by two.

Code

This is the implementation of Selection Sort in Python. It may look slighter more complex than the usual Selection Sort implementation, but that’s because I’ll to provide codes that work both for the crescent and decrescent sorting.

And this is the implementation of optimized Selection Sort in Python. Again, this codes works both for the crescent and decrescent sorting.

Step By Step Execution

The execution below will illustrate the steps of a crescent ordering insertion sort execution.

The input data is:

a = [3, 1, 5, 4, 2]
a_size = 5

Array - Initial

Array - Initial. Image extracted from https://algorithm-visualizer.org/

The outer loop will define the x range. From the input data, we can assume that x will range from 0 to (a_size - 1) => 1 to (5 - 1) => 0 to 4.

With the first outer loop, having x = 0, we store this value, which is the current lowest element index, in swap_index. For this iteration, swap_index = 0. Also, we know that y will range from (x + 1) to (a_size - 1) => (0 + 1) to (5 - 1) => 1 to 4.

These are the inner loop iterations for the first outer loop iteration:

  • y = 1 => a[y] < a[swap_index] => a[1] < a[0] => 1 < 3 => Set swap_index to y => Set swap_index to 1 => [3, 1, 5, 4, 2]

Identify 1 as being lower than the current lowest element, replacing 3

Identify 1 as being lower than the current lowest element, replacing 3. Images extracted from https://algorithm-visualizer.org/

  • y = 2 => a[y] < a[swap_index] => a[2] < a[1] => 5 < 1 => No changes => [3, 1, 5, 4, 2]
  • y = 3 => a[y] < a[swap_index] => a[3] < a[1] => 4 < 1 => No changes => [3, 1, 5, 4, 2]
  • y = 4 => a[y] < a[swap_index] => a[4] < a[1] => 2 < 1 => No changes => [3, 1, 5, 4, 2]

With the end of the inner loop iterations, the current outer loop iteration is finished by swapping the element in the x position with the element in the swap_index position, which translates as: Swap a[x] with a[swap_index] => Swap a[0] with a[1]> Swap 3 with 1 => [1, 3, 5, 4, 2]

First swap - a[0] for a[1]

First swap - a[0] for a[1]. Images extracted from https://algorithm-visualizer.org/

With the second outer loop, having x = 1, we store this value, which is the current lowest element index, in swap_index. For this iteration, swap_index = 1. Also, we know that y will range from (x + 1) to (a_size - 1) => (1 + 1) to (5 - 1) => 2 to 4.

These are the inner loop iterations for the second outer loop iteration:

  • y = 2 => a[y] < a[swap_index] => a[2] < a[1] => 5 < 3 => No changes => [1, 3, 5, 4, 2]
  • y = 3 => a[y] < a[swap_index] => a[3] < a[1] => 4 < 3 => No changes => [1, 3, 5, 4, 2]
  • y = 4 => a[y] < a[swap_index] => a[4] < a[1] => 2 < 3 => Set swap_index to y => Set swap_index to 4 => [1, 3, 5, 4, 2]

Identify 2 as being lower than the current lowest element, replacing 3

Identify 2 as being lower than the current lowest element, replacing 3. Images extracted from https://algorithm-visualizer.org/

With the end of the inner loop iterations, the current outer loop iteration is finished by swapping the element in the x position with the element in the swap_index position, which translates as: Swap a[x] with a[swap_index] => Swap a[1] with a[4]> Swap 3 with 2 => [1, 2, 5, 4, 3]

Second swap - a[1] for a[4]

Second swap - a[1] for a[4]. Images extracted from https://algorithm-visualizer.org/

With the third outer loop, having x = 2, we store this value, which is the current lowest element index, in swap_index. For this iteration, swap_index = 2. Also, we know that y will range from (x + 1) to (a_size - 1) => (2 + 1) to (5 - 1) => 3 to 4.

These are the inner loop iterations for the third outer loop iteration:

  • y = 3 => a[y] < a[swap_index] => a[3] < a[2] => 4 < 5 => Set swap_index to y => Set swap_index to 3 => [1, 2, 5, 4, 3]

Identify 4 as being lower than the current lowest element, replacing 5

Identify 4 as being lower than the current lowest element, replacing 5. Images extracted from https://algorithm-visualizer.org/

  • y = 4 => a[y] < a[swap_index] => a[4] < a[2] => 3 < 5 => Set swap_index to y => Set swap_index to 4 => [1, 2, 5, 4, 3]

Identify 3 as being lower than the current lowest element, replacing 4

Identify 3 as being lower than the current lowest element, replacing 4. Images extracted from https://algorithm-visualizer.org/

With the end of the inner loop iterations, the current outer loop iteration is finished by swapping the element in the x position with the element in the swap_index position, which translates as: Swap a[x] with a[swap_index] => Swap a[2] with a[4]> Swap 5 with 3 => [1, 2, 3, 4, 5]

Third swap - a[2] for a[4]

Third swap - a[2] for a[4]. Images extracted from https://algorithm-visualizer.org/

With the fourth outer loop, having x = 3, we store this value, which is the current lowest element index, in swap_index. For this iteration, swap_index = 3. Also, we know that y will range from (x + 1) to (a_size - 1) => (3 + 1) to (5 - 1) => 4 to 4.

This is the inner loop iteration for the fourth outer loop iteration:

  • y = 4 => a[y] < a[swap_index] => a[4] < a[3] => 5 < 4 => No changes => [1, 2, 3, 4, 5]

With the end of the inner loop iterations, the current outer loop iteration is finished by swapping the element in the x position with the element in the swap_index position, which translates as: Swap a[x] with a[swap_index] => Swap a[3] with a[3]> Swap 4 with 4 => [1, 2, 3, 4, 5]

At the end of the final outer loop iteration, the array is ordered.

Array - Final

Array - Final. Image extracted from https://algorithm-visualizer.org/

Complexity

Worst-case performance: O(n²)

Best-case performance: O(n²)

Average performance: O(n²)

Space complexity 1: O(n)

Auxiliary space 2: O(1) for the normal implementation; O(2) for the optimized implementation. 3

Benchmark

As the posts from the Sorting Algorithms Studies are posted, I’ll benchmark the algorithms against each other. For now, there’s only Bubble Sort, Insertion Sort and Selection Sort to be shown.

Sorting 1000 different arrays with 1000 randomly sorted elements
Algorithm Average Time Spent (seconds)
Selection Sort Optimized - Crescent 0.0752946375
Selection Sort Optimized - Decrescent 0.0753254230
Insertion Sort Optimized - Decrescent 0.0754734700
Selection Sort - Decrescent 0.0768013875
Selection Sort - Crescent 0.0769227114
Insertion Sort Optimized - Crescent 0.0774509237
Insertion Sort - Decrescent 0.1340322953
Insertion Sort - Crescent 0.1360035590
Bubble Sort - Decrescent 0.1568078588
Bubble Sort - Crescent 0.1597317403
Bubble Sort Optimized - Decrescent 0.1602741867
Bubble Sort Optimized - Crescent 0.1618632810

Sorting 1000 different arrays with 1000 elements in ascending order
Algorithm Average Time Spent (seconds)
Bubble Sort Optimized - Crescent 0.0002221006
Insertion Sort - Crescent 0.0003292135
Insertion Sort Optimized - Crescent 0.0003776510
Selection Sort Optimized - Decrescent 0.0864848356
Selection Sort - Crescent 0.0876183987
Selection Sort - Decrescent 0.0900442983
Selection Sort Optimized - Crescent 0.0924761386
Bubble Sort - Crescent 0.0998125052
Insertion Sort Optimized - Decrescent 0.1702091216
Bubble Sort - Decrescent 0.2626039418
Bubble Sort Optimized - Decrescent 0.2685824222
Insertion Sort - Decrescent 0.3066988004

Sorting 1000 different arrays with 1000 elements in descending order
Algorithm Average Time Spent (seconds)
Bubble Sort Optimized - Decrescent 0.0001869991
Insertion Sort - Decrescent 0.0002643334
Insertion Sort Optimized - Decrescent 0.0004072941
Selection Sort - Decrescent 0.0790777007
Selection Sort Optimized - Crescent 0.0794137814
Selection Sort - Crescent 0.0829683988
Selection Sort Optimized - Decrescent 0.0836715313
Bubble Sort - Decrescent 0.0884681934
Insertion Sort Optimized - Crescent 0.1560818879
Bubble Sort - Crescent 0.2418319963
Bubble Sort Optimized - Crescent 0.2456611876
Insertion Sort - Crescent 0.2854158659

Wrapping Up

Selection Sort is another of those simple algorithm that we use more often than we realize. As the Bubble and Insertion Sort, it doesn’t performs well, but it may be enough for some scenarios, like when you have really small lists.

Stay tuned for the next chapters of this series!

  1. Auxiliary Space + Input space

  2. Extra or temporary space used by the algorithm during it's execution.

  3. Python's way of swapping two values dismisses the need of a temp variable to make the swap of values. Because of that, there normal implementation in Python uses O(1) auxiliary space. The optimized implementation still uses O(2) auxiliary space.