Selection Sort Simplified: Easy Guide

Selection Sort is a simple sorting algorithm that repeatedly finds the smallest (or the largest) element from the unsorted part and moves it to its correct position.

What is Selection Sort?

Selection sort is a comparison sort algorithm. It repeatedly selects the smallest or largest element from the unsorted part of the array and swaps it with the element at the appropriate index. This is why it is named Selection Sort.

How does it work?

Let’s take the following array as an example. We need to sort it in ascending order.

The selection sort algorithm finds the smallest element of the array at every traversal. Here, the smallest element is 1 so it put 1 at the first position (0th index). Hence, it swaps 1 and 9.

Next, in the following pass, the smallest element is 3. Its correct index is 1. Since it is already in the right place, no swap is needed.

Now the next smallest element from the unsorted part of the array is 5. It must be placed in the 3rd position (2nd index). Hence, the algorithm will swap 9 and 5.

In the next pass, the smallest element of the unsorted part of the array is 8. As 8 is already in its appropriate position, no swap is performed. The last element is not checked because if all the other elements are in their correct positions, then the last element must also be in its correct position.

The array is finally sorted 😃!

💡	Similar procedure will be followed if we start with the largest element.

Time Complexity

The algorithm works in two steps:

• Finds the smallest (or the largest) element of the unsorted part of the array

• Swap it!

For finding the smallest (or the largest) element of the array, N - 1 comparisons need to be made where N is the size of the array.

In the first traversal, N - 1 comparisons are made. In the second traversal, N - 2 comparisons are made as one element is already sorted. In the third traversal, N - 3 comparisons are made and so on. In the last traversal, only 1 comparison will be made.

Hence, total number of comparisons is

$$1 + 2+...+(N-1) \\ = \frac {(N-1)(N-1+1)}{2} \\ = \frac {N(N-1)}{2} \\ = \frac {N^2 - N} {2}$$

Therefore, time complexity is O(N²) as constants are cancelled, and less dominating terms are removed.

In both the worst case and the best case, the time complexity is O(N²) as even in the best case, comparisons are made to find the smallest (or the largest) element every time.

Space Complexity

The space complexity of selection sort algorithm is O(1) as no extra space is taken.

Stability

The Selection Sort is not a stable sorting algorithm as it does not maintain the original order of the equal elements (or duplicate elements) in the final sorted array as it was present in the original array.

Example Code

The example code demonstrates two possible implementations of the selection sort algorithm within a single Java file. One method selects the smallest element from the unsorted part of the array during each pass, while the other method selects the largest element.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSortUsingMaxElement(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
        int[] arr2 = {89, 45, 68, 90, 29, 34};
        selectionSortUsingMinElement(arr2);
        System.out.println("Sorted array: " + Arrays.toString(arr2));
    }

    static void selectionSortUsingMaxElement(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // find the maximum element in unsorted part of the array and
            // swap it with correct index
            int lastIndex = arr.length - i - 1;
            int maxIndex = getMaxIndex(arr, 0, lastIndex);
            swap(arr, maxIndex, lastIndex);
        }
    }

    static void selectionSortUsingMinElement(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // find the smallest number in the unsorted part of the array and
            // swap it with the correct index
            int firstIndex = i;
            int minIndex = getMinIndex(arr, firstIndex, arr.length - 1);
            swap(arr, firstIndex, minIndex);
        }
    }

    private static int getMinIndex(int[] arr, int start, int end) {
        int min = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] < arr[min]) {
                min = i;
            }
        }
        return min;
    }

    private static int getMaxIndex(int[] arr, int start, int end) {
        int max = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] > arr[max]) {
                max = i;
            }
        }
        return max;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Conclusion

Selection Sort is a straightforward and intuitive sorting algorithm that is easy to understand and implement. This algorithm is used for small datasets. An advantage of this algorithm over bubble sort is that it requires fewer swaps. It is also an in-place sorting algorithm so can be used where memory usage is a concern.

⭐ Check out the DSA GitHub repo for more code examples.