Selection Sort

Selection Sort Algorithm in C++ (Complete Implementation)

BeginnerTopic: Sorting & Searching Programs
Back

C++ Selection Sort Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

Try This Code
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        // Find minimum element in unsorted portion
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap found minimum with first element
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array: ";
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    cout << "Sorted array: ";
    printArray(arr, n);
    
    return 0;
}
Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Understanding Selection Sort

This program teaches you how to implement the Selection Sort algorithm in C++. Selection Sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. It's simple to understand and implement, making it a good learning algorithm, though it's not efficient for large datasets.

---

1. What This Program Does

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.

---

2. Header File Used

This header provides:

•cout for displaying output
•cin for taking input from the user

---

#include <iostream>

3. 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...

---

4. 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

---

5. 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...

---

6. 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

---

7. 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

---

8. 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)

---

9. 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)

---

10. 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

---

11. return 0;

This ends the program successfully.

---

Summary

•Selection Sort finds minimum element and places it at beginning of unsorted portion.
•Time complexity: O(n²) in all cases - always performs same number of comparisons.
•Space complexity: O(1) - sorts in-place.
•Not stable - swapping can change relative order of equal elements.
•Simple algorithm - easy to understand and implement.
•Maintains two subarrays: sorted (growing) and unsorted (shrinking).
•Best for small datasets or when minimal swaps are important.
•Understanding Selection Sort helps learn more efficient algorithms.

This program is fundamental for beginners learning sorting algorithms, understanding minimum finding, and preparing for more efficient sorting algorithms in C++ programs.

Let us now understand every line and the components of the above program.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Practical Learning Notes for Selection Sort

This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.

A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.

For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.

Next
Merge Sort
Previous
Insertion Sort
Next
Merge Sort

Table of Contents