What is selection sort?

Sorting in general means arranging the elements of an unsorted array either in ascending or descending order. There is a requirement to sort array elements to keep them organized and for quick access. This reduces time complexity, one of the significant constraints while dealing with large data.

Introduction🔊

Selection sort is one such algorithm for sorting, where we find the least valued element in each iteration and swapped with the element at the beginning of every sub-array.

The array will be divided into two sub-arrays:

Sorted sub-array
Unsorted sub-array

We shall append (add) the smallest element from the unsorted sub-array to the end of the sorted sub-array in order to better explain the concept.

Algorithm🔢

Get the array input from the user
Use 2 iterators: one to maintain the sorted sub-array and the other for the unsorted sub-array.
Compare the current element and swap it with the least possible value in the remaining sub-array.
Continue the same approach with the next element until the entire array/segment is sorted.

Implementation⚙️

Let’s begin implementing the above using C++. To be clear the logic remains the same, only the syntax of every programming language changes.

#include <bits/stdc++.h>
using namespace std;

void swapElements(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sort_selection(int sorted[], int arrLen) {
    int i, j, low;

    for (int i = 0; i < arrLen - 1; i++) {
        low = i;
        for (int j = i + 1; j < arrLen; j++) {
            if (sorted[j] < sorted[low]) { low = j; }
        }

        if (low != i) { swapElements(&sorted[low], &sorted[i]); }
    }
}

int main() {
    int inArray[] = { 40, 10, 20, 30, 50 };

    int arrLen = sizeof(inArray)/ sizeof(inArray[0]);

    cout << "Unsorted Array: ";

    for (int i = 0; i < arrLen; i++)
        cout << inArray[i] << " ";

    sort_selection(inArray, arrLen);

    cout << endl << "Sorted Array: ";

    for (int i = 0; i < arrLen; i++)
        cout << inArray[i] << " ";

    return 0;
}

Code language: C++ (cpp)

The above code is the C++ implementation of the selection sort algorithm. Let’s begin with the main function. Initially, we created an integer array named arr and stored five random values. Also, calculate the value of the size of the array and store it in the variable n. Then we call the selectionSort function defined above. We pass two parameters: the array as such and the size of the array.

The selectionSort function has three variables defined namely i, j, and low. i and j are iteration variables. low a variable is used to store the minimum value of the unsorted subarray.

Theoretical Understanding📝

The outer for-loop runs from 0 to one less than the size of the array. The reason we skip one iteration is that the last element will be already in the correct position. In every iteration, we store the value of low to i. Then we run an inner for-loop from i + 1 to n. In every iteration, we check if the current element in the unsorted sub-array is less than the value at the position i. If true we update the value of low. After the inner for-loop completes its iterations we check if the current value of the variable low is the same as the value of i (initialized above). If true then we continue with the next iteration. If not then we swap the value of elements at their position using swap the function. It is based on the concept of the call-by-reference method. Finally, when the outer for-loop completes its iteration we jump back to the main program. Then we display the sorted array.

This is the working of the selection-sort algorithm. The concept behind it lies the same but only the syntax changes in other programming languages.

Visual interpretation of whatever is conveyed in words is available here:

Space and Time Complexity

According to the selection sort algorithm we need to iterate the loop and check the condition of finding the smallest element. Each of them requires O(n) time complexity. Therefore the net time complexity is:

O(n) * O(n) = O(n^2)

🤩Best Case: O(n^2)

😐Average Case: Θ(n^2)

😭Worst Case: O(n^2)

Here we don’t require any extra array while performing the sorting algorithm. Hence, the space complexity is O(1).

Conclusion🔚

Selection sort utilizes two sub-arrays: sorted and unsorted sub-array.
After the end of each iteration, we bring the lowest or highest element in the sorted sub-array.
It requires very less space complexity i.e. O(1) and time-complexity of O(n^2)
Here’s the link to the codedamn playground which contains the code and you could play directly with the integrated terminal and editor.