Selection Sort Explained Step-By-Step

Selection Sort is one of those beginner sorting algorithms which despite not being very efficient, form important foundation concepts.

This article explains it in a very beginner-friendly way and even portrays some comparisons with insertion sort.

ALGORITHM

It works on the basic principle of “select the minimum element and place it at correct position “.
It divides the array into two parts
1. The left sorted part
2. The right unsorted part
The idea is to repeatedly find the minimum element in the unsorted part, and then place it at the beginning of the unsorted part.
Thus increasing the size of the sorted part of the array in each iteration.
The basic working of the algorithm is as follows
1. Assume the first element of the array is the smallest.
2. Scan the remaining unsorted part of the array to find the actual smallest element.
3. If a smaller element is found, update the position of the smallest element.
4. After completing the scan, swap the smallest element with the element at the current position.
5. The element at the current position is now fixed and considered sorted.
6. Move to the next position and repeat the process for the remaining unsorted elements.
7. Continue until the entire array is sorted.

DRY-RUN EXAMPLE

Let us consider an array [13,46,24,52,20,9].

We will be sorting this using selection sort.

The highlighted part represents the sorted part of the array.

Step-0:
- 13 46 24 52 20 9
- The entire array is currently unsorted
Step-1:
- i = 0, curr = 13
- We find the minimum element in the array (9) and swap it with the current element, thus placing it at the beginning of the unsorted part.
- 9 46 24 52 20 13
Step-2:
- i = 1, curr = 46
- We find the minimum element in the unsorted part (13) and swap it with the current element, thus placing it at the beginning of the unsorted part.
- 9 13 24 52 20 46
Step-4:
- i = 2, curr = 24
- We find the minimum element in the unsorted part (20) and swap it with the current element, thus placing it at the beginning of the unsorted part.
- 9 13 20 52 24 46
Step-5:
- i = 3, curr = 52
- We find the minimum element in the unsorted part (24) and swap it with the current element, thus placing it at the beginning of the unsorted part.
- 9 13 20 24 52 46
Step-6:
- i = 4, curr = 52
- We find the minimum element in the unsorted part (46) and swap it with the current element, thus placing it at the beginning of the unsorted part.
- 9 13 20 24 46 52

The array becomes fully sorted after (n−1) passes, where each pass places one element in its correct position.

NOTE: n denotes the number of elements in the array.

CODE IMPLEMENTATION

public static void selectionSort(int[] arr){
    int minIndex, temp;
    for(int i=0;i<arr.length-1;i++){
        minIndex = i;
        for(int j=i+1;j<arr.length;j++){
            if(arr[j] < arr[minIndex])
                minIndex = j;
        }
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

The outer loop runs until the second last element because after placing (n−1) elements, the last one is automatically sorted.
The inner loop begins from (i+1) and goes all the way to the end of array as this is our ‘right unsorted‘ part of the array.
After we find the minimum in each iteration through the inner loop, we swap the found minimum element with the current element using a third temporary variable.

TIME COMPLEXITY

Best Case
- Already sorted array.
- Despite no swaps being made, the number of comparisons remains the same.
- Total number of operations : (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2
- Upon ignoring constants, we get a time complexity of O(n²).
Average Case
- Randomly sorted array.
- Minimum still has to be searched in the unsorted part each time.
- Same number of iterations.
- Hence, Time Complexity : O(n²)
Worst Case
- Reverse sorted array.
- Same number of comparisons are made.
- Swaps do not increase time complexity by a huge margin.
- Upon ignoring constants, we again get a quadratic time complexity —> O(n²).

SPACE COMPLEXITY

Consider the following points:

We use a variable for storing the minimum index, and one temporary variable for swapping.
We do not create any new arrays or perform recursion.
Constant number of variables corresponds to constant space.

Hence, the selection sort has a constant space complexity —> O(1)

CONCLUSION

Selection sort is more about foundational sorting concepts than it is about speed or efficiency. It might not be the best sorting algorithm but it sure is an important one as it develops a base to understand the more more complex ones later on.

It is a clear example of deceptive efficiency. Although it performs fewer swaps than insertion sort, the number of comparisons remains the same, making its overall time complexity no better (and even worse in the Best Case Scenario when the array).

Command Palette