Selection sort

Selection sort is a simple sorting algorithm that performs in-place sorting.

Let's see how the algorithm works for sorting an array in ascending order. First, it finds the smallest element in the whole array and swaps it with the element in the first position. Then it finds the second smallest element and swaps it with the element in the second position. It continues doing that until the whole array is sorted.

If we want to sort the array in descending order, we should find the largest element instead of the smallest one.

If $n$ is the length of the input array, the algorithm has asymptotic time complexity $Ο(n^2)$ in the worst-case and the average cases in terms of the number of comparisons. This makes the algorithm inefficient for sorting large arrays. The algorithm finds the minimum/maximum element $n-1$ times.

The basic implementation of the algorithm is unstable, but we can modify it to be stable.

Example

Suppose we have an unsorted array of integers and we should sort it in ascending order.

This array has six elements, the first element has the index 0, and the last one has the index 5.

The following image illustrates how the sorting algorithm works:

Here are some explanations:

1) We find the min number in the whole array (11) and swap it with the first element (21). Now, the first element belongs to the sorted subarray.

2) We find the min number in the unsorted subarray (19) and swap the number with the second element. Now, the first and the second elements belong to the sorted subarray.

3) We find the min number in the unsorted subarray (21) and swap it with the third element (23). Now, the first three elements belong to the sorted subarray.

4-6) We repeat the same process until the whole array is sorted.

As you can see, the algorithm is quite simple. It never changes the already sorted subarray.

You may also check out a visualization of selection sort to better understand it.

Psuedocode

In this section, we present the pseudocode for the Selection Sort algorithm, a simple yet effective in-place sorting technique. The algorithm works by iteratively finding the minimum or maximum element and swapping it with the first element in the unsorted part of the array. This process continues until the entire array is sorted. We'll provide pseudocode for both ascending and descending order.

// Get the length of the array
n = length(arr)

// Perform Selection Sort for ascending order
function selectionSortAsc(arr):
    for i in [0, n-1]:
        // Find the index of the minimum element in the unsorted part
        minIndex = i
        for j in [i+1, n-1]:
            if arr[j] < arr[minIndex] then:
                minIndex = j

        // Swap the found minimum element with the first element in the unsorted part
        swap(arr, i, minIndex)

// Perform Selection Sort for descending order
function selectionSortDesc(arr):
    for i in [0, n-1]:
        // Find the index of the maximum element in the unsorted part
        maxIndex = i
        for j in [i+1, n-1]:
            if arr[j] > arr[maxIndex] then:
                maxIndex = j

        // Swap the found maximum element with the first element in the unsorted part
        swap(arr, i, maxIndex)

This pseudocode outlines the basic structure of the Selection Sort algorithm for both ascending and descending order. The selectionSortAsc() and selectionSortDesc() functions perform the sorting in the respective orders, and the swap() function is used to interchange elements at given indices.

Double selection sort

The bidirectional variant of selection sort finds both the minimum and the maximum values in the array at every pass. It reduces the number of scans of the array. The algorithm divides the array into three subarrays: 1) sorted minimums; 2) unsorted; 3) sorted maximums. The algorithm has the same time complexity as the basic algorithm: $Ο(n^2)$.