Selection Sort Algorithm in DSA C++

Mental Model

Selection sort finds the smallest item and puts it at the start, then repeats for the rest.

Analogy: Imagine sorting books by picking the shortest book from the unsorted pile and placing it on the shelf one by one.

Unsorted array:
[7, 3, 5, 2, 4]
Indexes:
 0  1  2  3  4

Dry Run Walkthrough

Input: array: [7, 3, 5, 2, 4]

Goal: Sort the array in ascending order using selection sort

Step 1: Find smallest from index 0 to end, swap with index 0

[2, 3, 5, 7, 4]

Why: 2 is smallest, put it at start to begin sorted section

Step 2: Find smallest from index 1 to end, swap with index 1

[2, 3, 5, 7, 4]

Why: 3 is already smallest in remaining, no change

Step 3: Find smallest from index 2 to end, swap with index 2

[2, 3, 4, 7, 5]

Why: 4 is smallest from index 2 onwards, swap with 5

Step 4: Find smallest from index 3 to end, swap with index 3

[2, 3, 4, 5, 7]

Why: 5 is smallest from index 3 onwards, swap with 7

Step 5: Last element is sorted by default

[2, 3, 4, 5, 7]

Why: Only one element left, array is sorted

Result:

Final sorted array:
[2, 3, 4, 5, 7]

Annotated Code

DSA C++

#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; // assume current is smallest
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // found smaller element
            }
        }
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]); // place smallest at i
        }
    }
}

int main() {
    vector<int> arr = {7, 3, 5, 2, 4};
    selectionSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

for (int i = 0; i < n - 1; i++) {

iterate over each position to place the smallest element

int minIndex = i; // assume current is smallest

start by assuming current index holds smallest value

for (int j = i + 1; j < n; j++) {

search the rest of the array for a smaller element

if (arr[j] < arr[minIndex]) { minIndex = j; }

update minIndex when a smaller element is found

if (minIndex != i) { swap(arr[i], arr[minIndex]); }

swap smallest found with current position to grow sorted part

Output

2 3 4 5 7 

Complexity Analysis

Time: O(n^2) because for each element we scan the rest to find the smallest

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to bubble sort, selection sort does fewer swaps but same comparisons; simpler but still quadratic time

Edge Cases

empty array

function completes immediately without changes

DSA C++

for (int i = 0; i < n - 1; i++) {

array with one element

no swaps needed, array remains same

DSA C++

for (int i = 0; i < n - 1; i++) {

array with all equal elements

no swaps occur, array stays unchanged

DSA C++

if (minIndex != i) { swap(arr[i], arr[minIndex]); }

When to Use This Pattern

When you need a simple, easy-to-understand sorting method that selects the smallest element repeatedly, use selection sort.

Common Mistakes

Mistake: Swapping elements inside the inner loop instead of after finding the minimum
Fix: Only swap once per outer loop iteration after the minimum is found

Mistake: Not updating minIndex when a smaller element is found
Fix: Update minIndex inside the inner loop when a smaller element is detected

Summary

Selection sort repeatedly finds the smallest element and places it at the front.

Use it for small arrays or when simplicity is more important than speed.

The key is to find the minimum in the unsorted part and swap once per step.