Selection Sort in C++

Selection Sort Algorithm in C++ (Complete Implementation).

BeginnerSorting & Searching ProgramsExample 3 of 13

selection-sort.cpp

1#include <iostream>
2using namespace std;
3
4void selectionSort(int arr[], int n) {
5    for (int i = 0; i < n - 1; i++) {
6        int minIndex = i;
7        
8        // Find minimum element in unsorted portion
9        for (int j = i + 1; j < n; j++) {
10            if (arr[j] < arr[minIndex]) {
11                minIndex = j;
12            }
13        }
14        
15        // Swap found minimum with first element
16        if (minIndex != i) {
17            swap(arr[i], arr[minIndex]);
18        }
19    }
20}
21
22void printArray(int arr[], int n) {
23    for (int i = 0; i < n; i++) {
24        cout << arr[i] << " ";
25    }
26    cout << endl;
27}
28
29int main() {
30    int arr[] = {64, 34, 25, 12, 22, 11, 90};
31    int n = sizeof(arr) / sizeof(arr[0]);
32    
33    cout << "Original array: ";
34    printArray(arr, n);
35    
36    selectionSort(arr, n);
37    
38    cout << "Sorted array: ";
39    printArray(arr, n);
40    
41    return 0;
42}

Output

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

What's going on

The program sorts an array of integers using the Selection Sort algorithm. For example:

Input array: [64, 34, 25, 12, 22, 11, 90]

Output array: [11, 12, 22, 25, 34, 64, 90]

Selection Sort divides the array into two parts: sorted (at the beginning) and unsorted (remaining elements). In each iteration, it finds the minimum from the unsorted part and adds it to the sorted part.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

Understanding Selection Sort

Algorithm Concept

Maintains two subarrays: sorted and unsorted

Finds minimum element in unsorted portion

Swaps it with first element of unsorted portion

Sorted portion grows, unsorted shrinks

Visual Example

Initial: [64, 34, 25, 12, 22, 11, 90]

|sorted| |------unsorted------|

Pass 1: Find min (11) → swap with 64

[11, 34, 25, 12, 22, 64, 90]

|sorted| |----unsorted----|

Pass 2: Find min (12) → swap with 34

[11, 12, 25, 34, 22, 64, 90]

|--sorted--| |--unsorted--|

Continue until all sorted...

Function: selectionSort()

void selectionSort(int arr[], int n) {

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;

}

if (minIndex != i) {

swap(arr[i], arr[minIndex]);

}

How it works

Outer loop (i): iterates from 0 to n-2 (n-1 passes)

minIndex: tracks position of minimum element

Inner loop: finds minimum in unsorted portion (i+1 to n-1)

Swap: places minimum at position i

Step-by-Step Algorithm

Pass 1 (i=0)

Search unsorted portion [34, 25, 12, 22, 11, 90] for minimum

Minimum: 11 at index 5

Swap arr[0] (64) with arr[5] (11)

Result: [11, 34, 25, 12, 22, 64, 90]

Pass 2 (i=1)

Search unsorted portion [34, 25, 12, 22, 64, 90] for minimum

Minimum: 12 at index 3

Swap arr[1] (34) with arr[3] (12)

Result: [11, 12, 25, 34, 22, 64, 90]

Continue for n-1 passes...

Finding Minimum Element

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

if (arr[j] < arr[minIndex]) {

minIndex = j;

}

How it works

j starts at i + 1 (first unsorted element)

Compares each element with current minimum

Updates minIndex when smaller element found

After loop, minIndex points to minimum

Example

(finding min in [34, 25, 12, 22, 64, 90]):

minIndex = 0, arr[0] = 34

j=1: 25 < 34 → minIndex = 1

j=2: 12 < 25 → minIndex = 2

j=3: 22 > 12 → no change

j=4: 64 > 12 → no change

j=5: 90 > 12 → no change

Minimum: 12 at index 2

Swap Operation

if (minIndex != i) {

swap(arr[i], arr[minIndex]);

}

How it works

Only swap if minimum is not already at position i

Places minimum at beginning of unsorted portion

Expands sorted portion by one element

Why Check minIndex != i?

Avoids unnecessary swap

If minimum is already at position i, no swap needed

Slight optimization

Time and Space Complexity

Time Complexity

: O(n²) in all cases

Always performs n(n-1)/2 comparisons

No early termination possible

Same for best, average, and worst case

Space Complexity

: O(1)

Only uses constant extra space

Sorts in-place (modifies original array)

Stability

: Not Stable

Swapping can change relative order of equal elements

Example: [3₁, 3₂, 1] → [1, 3₂, 3₁] (order changed)

When to Use Selection Sort

Best For

Small datasets

When memory writes are expensive (minimal swaps)

Simple implementation needed

Educational purposes

Not Recommended For

Large datasets (use efficient algorithms)

When stability is required

Performance-critical applications

Real-world production code (usually)

Important Considerations

Number of Passes

Exactly n - 1 passes needed

Each pass places one element correctly

Last element is automatically in place

Comparison Count

Always n(n-1)/2 comparisons

No optimization possible

Predictable performance

Swap Count

Maximum n - 1 swaps

Minimum 0 swaps (if already sorted)

Fewer swaps than Bubble Sort

return 0;

This ends the program successfully.

PreviousInsertion Sort NextMerge Sort