C++ Program for Selection Sort with Example and Explanation

A C++ program for selection sort uses nested loops to repeatedly find the smallest element and swap it with the current position, like for (int i = 0; i < n-1; i++) { int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; std::swap(arr[min_idx], arr[i]); }.

Examples

Input5 3 8 4 2

Output2 3 4 5 8

Input10 9 8 7 6

Output6 7 8 9 10

Input1 1 1 1 1

Output1 1 1 1 1

How to Think About It

To sort an array using selection sort, think of dividing the list into two parts: sorted and unsorted. Repeatedly find the smallest item in the unsorted part and swap it with the first unsorted element, moving the boundary forward until the whole list is sorted.

Algorithm

1

Start from the first element as the current position.

2

Find the smallest element in the unsorted part of the array.

3

Swap the smallest element found with the element at the current position.

4

Move to the next position and repeat until the entire array is sorted.

Code

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {5, 3, 8, 4, 2};
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        std::swap(arr[min_idx], arr[i]);
    }

    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Dry Run

Let's trace the array {5, 3, 8, 4, 2} through the selection sort code.

1

Initial array

arr = {5, 3, 8, 4, 2}

2

Find min from index 0 to end

Minimum is 2 at index 4; swap arr[0] and arr[4] -> arr = {2, 3, 8, 4, 5}

3

Find min from index 1 to end

Minimum is 3 at index 1; swap arr[1] and arr[1] (no change) -> arr = {2, 3, 8, 4, 5}

4

Find min from index 2 to end

Minimum is 4 at index 3; swap arr[2] and arr[3] -> arr = {2, 3, 4, 8, 5}

5

Find min from index 3 to end

Minimum is 5 at index 4; swap arr[3] and arr[4] -> arr = {2, 3, 4, 5, 8}

Iteration	Array State
0	5 3 8 4 2
1	2 3 8 4 5
2	2 3 8 4 5
3	2 3 4 8 5
4	2 3 4 5 8

Why This Works

Step 1: Finding the smallest element

The inner loop uses if (arr[j] < arr[min_idx]) to find the smallest element in the unsorted part.

Step 2: Swapping elements

After finding the smallest element, std::swap(arr[min_idx], arr[i]) places it at the current sorted position.

Step 3: Progressing through the array

The outer loop moves the boundary of the sorted part forward until the entire array is sorted.

Alternative Approaches

Using a function to encapsulate selection sort

cpp

#include <iostream>
#include <vector>

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

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

This approach improves code reuse and readability by separating sorting logic.

Using pointers instead of vector

cpp

#include <iostream>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    std::cout << std::endl;
    return 0;
}

This uses raw arrays and manual swapping, which is closer to C style but less safe than vectors.

Complexity: O(n^2) time, O(1) space

Time Complexity

Selection sort uses two nested loops each running up to n times, resulting in O(n^2) time complexity regardless of input order.

Space Complexity

It sorts the array in place using only a few extra variables, so space complexity is O(1).

Which Approach is Fastest?

Selection sort is simple but slower than algorithms like quicksort or mergesort for large data sets.

Approach	Time	Space	Best For
Selection Sort	O(n^2)	O(1)	Small or nearly sorted arrays
Quicksort	O(n log n) average	O(log n)	Large datasets, faster sorting
Mergesort	O(n log n)	O(n)	Stable sorting, large datasets