Algorithms Part 1 - Selection Sort

IMPORTANT : The notes that I took for myself. I hope they will help you too.. Each resource that I used is added as reference at the end of the page.

Selection Sort

The following card game simply explains how the selection sort algorithm works. The game is very simple; we want to sort the scattered cards from smallest to largest by comparing them with each other.

To do this; first we need to start with the element in the first position and compare this element with other elements to find the smallest element. In this situation, our first item will be our reference value, as it will be replaced with the smallest item in the list, if any. Anyway, if we find the smallest element in the part of the list other than the first position, we need to swap it with the first element(of course if this value found is less than the first item!). After placing the smallest item in the list in the first position, we will continue the similar operations starting from position 2. In this case, our reference becomes the 2nd item. After the comparison and, if any, displacement operations are finished, we need to continue the similar operations until the penultimate element of the list, respectively. In summary, this is how the selection sort algorithm works.

An Example of Selection Sort

For example we have an unsorted list like this;

9 - 4 - 3 - 1

Our purpose

Sort numbers from smallest to largest by comparing them with each other.

How to apply selection sort algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SelectionSort {
    public static void main(String[] args) {
        int[] list = {9,4,3,1};
        for(int i=0; i< list.length-1; i++) {
            boolean hasSmallestBeenFounded = false;
            int smallest = i;
            for(int j=i; j< list.length-1; j++){
                if (list[j + 1] < list[smallest]) {
                    smallest = j + 1;
                    hasSmallestBeenFounded = true;
                }
            }
            if(hasSmallestBeenFounded){
                int tempValue = list[i];
                list[i] = list[smallest];
                list[smallest] = tempValue;
            }
        }
//       Arrays.stream(list)
//      .forEach(value -> System.out.print(value + " - "));
    }
}

1. I need two nested for loops to apply the selection sort to my list(of course not necessary to use for loop). My outer loop starts from the beginning of the list, keeping track of the position I want to hold(that is, it becomes our reference value according to the definition above). At the very beginning of the algorithm, this position is of course “0”. On the other hand, my inner for loop checks the other items other than the item in the position that the outer loop holds to find the smallest item.
2. For each new smallest value found, int “smallest” value will be updated throughout the inner for loop.
3. You will notice that the values for “smallest” and “hasSmallestBeenFounded” are updated just before you get inside the inner for loop. Because the purpose of the inner for loop is to find the smallest value and compare it with the reference value. If we go outside of the inner loop, we reset these two values to find the next smallest value, assuming that these values have fulfilled their task.
4. When the inner “for loop” finishes its execution, the boolean value “hasSmallestBeenFounded” is marked as true, even if at least one smallest value is found. Because the value of smallest can change during the inner loop. If the smallest value is not found, the value “hasSmallestBeenFounded” remains false and is not entered into the “if” statement outside the loop.
5. There is an “if” statement inside in the inner loop, if (list[j + 1] < list[smallest]). Here, smallest, which is supposed to represent the smallest value, is compared with the values at position “j + 1” followed by the inner loop. If the value pointing to the “j+1” position is smaller than the current “smallest” value, we update this “smallest” value with the value representing the “j+1” position. You can think of smallest as a temporary smallest value.
6. If the inner loop finds even one smallest value, it enters the if statement outside the inner loop, which replaces the smallest value found with the value in the first position(which is of course the position that I hold via outer loop).
7. After the first position of my outer loop is replaced by the smallest value(if any), we repeat the same process with the 2nd position of my outer loop by increasing the i number by one. Then, the same operations continue until the penultimate position(list.length-1) of my outer loop.

What is the Time Complexity of Selection Sort?

The time efficiency of selection sort is quadratic.

Best Case Time Complexity of Selection Sort

O(n²) comparisons, O(1) swaps.

In best case time complexity, we consider the list already sorted. So O(n) is 1 as there will be no swapping. But to find out whether the list is ordered or not, it would be comparison in any case. This brings a quadratic time complexity with it, that is, O(n²). Because we have 2 nested for loops.

Worst Case Time Complexity of Selection Sort

O(n²) comparisons, O(n) swaps.

Software engineers usually concentrate on finding only the worst-case running time, that is, the longest running time for any input of size “n”. Just like in the best case time complexity, the comparison takes place in quadratic time complexity. But in the worst case scenario, our list of course will not be sorted. Because the worst-case scenario requires it. So the swapping takes place in O(n) time.

Average Case Time Complexity of Selection Sort

O(n²) comparisons, O(n) swaps.

Even if the number of steps in the average time is half of the worst case, the result will still be the same as the worst case since constants will not be taken into account in the formulation.

Reference:

• selection sort pseudocode
• selection sort wiki
• Introduction to Algorithms third edition