DSA Selection Sort Algorithm

Last modified - 26-04-2025

Author - Krishna Shinde

If you are arranging numbers in ascending or descending order or arranging alphabets in in alphabets in alphabetical order this process of arrangement is known as sorting. There are various sorting algorithms being used, but the Selection Sort algorithm is among the simplest sorting techniques that is easy to understand and a good starting point if you want to explore the sorting algorithms.

What is the Selection Sort?

Selection Sort is a comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest, depending on sorting order) element from the unsorted part of the list and swapping it with the first unsorted element. This process continues until the entire array is sorted.

It is called selection sort because selects the smallest (or largest) during each iteration of the loop and places it in its correct position. It can be performed on various data structures.

How Does Selection Sort Work?

vector<int> arr = {29, 10, 14, 37, 13};

Step-by-step explanation

• 1st round:
• Find the smallest element in the unsorted array [29, 10, 14, 37, 13].
• The smallest is 10.
• Swap it with the first element 29.
• Array becomes - [10, 29, 14, 37, 13]
• 2nd round:
• Find the smallest element from [29, 14, 37, 13].
• The smallest is 13.
• Swap it with the first element 29.
• Array becomes - [10, 13, 14, 37, 29]
• 3rd round:
• Find the smallest element from [14, 37, 29].
• The smallest is 14.
• It is already in its place so no need to swap.
• 4th round
• Find the smallest element from [37, 29].
• The smallest is 29.
• Swap it with the first element 37.
• Array becomes - [10, 13, 14, 29, 37]

Now the array is sorted after 4 rounds.

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }
}

int main() {
    vector<int> arr = {29, 10, 14, 37, 13};
    selectionSort(arr);
    cout << "Sorted Array: ";
    for (int num : arr)
        cout << num << " ";
    return 0;
}

Time and Space Complexity

Why O(n²)?

Because there is a nested for loop, for every element it compares with all other elements in the unsorted part.

Why O(1) space?

No extra memory is used other than the temporary variables.

When to Use Selection Sort?

Due to its time complexity, it is rarely used in real-world projects.

Selection Sort vs Bubble Sort

Both the sorting algorithms are O(n²), and selection sort generally performs fewer swaps, which makes it more efficient than bubble sort in certain cases.

Conclusion

Selection sort is one of the basic sorting algorithms that is rarely used in the real world but it is useful while learning the sorting techniques, Even though it is not fast simplicity makes it easy to understand how sorting is performed.

Once you are comfortable with the Selection sort you can proceed to the more advanced algorithms like Quick sort, merge sort, or heap sort.