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.

Practice

1. What is the main idea behind the Selection Sort algorithm?

easy

A. Divide the array into halves and sort each half recursively

B. Swap adjacent elements if they are in wrong order

C. Repeatedly find the minimum element and place it at the beginning

D. Use a heap data structure to sort elements

Solution

1. Step 1: Understand Selection Sort process

   Selection Sort works by finding the smallest element in the unsorted part and swapping it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Unlike swapping adjacent elements or dividing arrays, Selection Sort directly selects the minimum element each time.

3. Final Answer:

   Repeatedly find the minimum element and place it at the beginning -> Option C

4. Quick Check:

   Selection Sort = Find minimum and swap [OK]

Hint: Selection Sort picks minimum each pass [OK]

Common Mistakes:

• Confusing with Bubble Sort swapping adjacent elements
• Thinking it divides array like Merge Sort
• Assuming it uses extra data structures like heaps

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[min_idx] in C++ during Selection Sort?

easy

A. swap(arr[i], arr[min_idx]);

B. arr[i] = arr[min_idx]; arr[min_idx] = arr[i];

C. swap(arr[min_idx], arr[j]);

D. arr[i], arr[min_idx] = arr[min_idx], arr[i];

Solution

1. Step 1: Identify correct swap function usage

   In C++, the standard library provides swap(a, b) to exchange values of two variables.

2. Step 2: Check syntax correctness

   swap(arr[i], arr[min_idx]); uses swap(arr[i], arr[min_idx]); which correctly swaps the two elements.

3. Final Answer:

   swap(arr[i], arr[min_idx]); -> Option A

4. Quick Check:

   Use std::swap for swapping [OK]

Hint: Use std::swap(a, b) to swap in C++ [OK]

Common Mistakes:

• Assigning one element twice causing data loss
• Using Python-style tuple swap syntax in C++
• Confusing parameter order in swap function

3. What will be the output array after running Selection Sort on arr = {64, 25, 12, 22, 11}?

medium

A. [11, 22, 12, 25, 64]

B. [64, 25, 12, 22, 11]

C. [25, 11, 12, 22, 64]

D. [11, 12, 22, 25, 64]

Solution

1. Step 1: Perform Selection Sort passes

   Pass 1: Minimum is 11, swap with 64 -> {11, 25, 12, 22, 64}
   Pass 2: Minimum is 12, swap with 25 -> {11, 12, 25, 22, 64}
   Pass 3: Minimum is 22, swap with 25 -> {11, 12, 22, 25, 64}
   Pass 4: Minimum is 25, no swap needed -> {11, 12, 22, 25, 64}

2. Step 2: Final sorted array

   The array after sorting is [11, 12, 22, 25, 64].

3. Final Answer:

   [11, 12, 22, 25, 64] -> Option D

4. Quick Check:

   Selection Sort output = Sorted array ascending [OK]

Hint: Selection Sort outputs sorted ascending array [OK]

Common Mistakes:

• Not swapping minimum element correctly
• Confusing sorting order (descending vs ascending)
• Stopping before full array is sorted

4. Identify the error in the following Selection Sort code snippet:

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;
    }
  }
  swap(arr[i], arr[min_idx]);
}

medium

A. The inner loop condition should be j <= n

B. The comparison operator should be < to find minimum

C. The swap function is used incorrectly

D. The outer loop should run till i < n

Solution

1. Step 1: Analyze comparison logic

   The code uses if (arr[j] > arr[min_idx]) which finds the maximum, not minimum.

2. Step 2: Correct comparison for Selection Sort

   Selection Sort requires finding the minimum element, so the operator should be <.

3. Final Answer:

   The comparison operator should be < to find minimum -> Option B

4. Quick Check:

   Selection Sort finds minimum using < comparison [OK]

Hint: Use < to find minimum in Selection Sort [OK]

Common Mistakes:

• Using > instead of < for minimum search
• Incorrect loop boundaries causing out-of-range errors
• Misusing swap function parameters

5. Given an array arr = {5, 3, 8, 6, 2}, how many swaps will Selection Sort perform to sort it in ascending order?

hard

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Trace swaps during Selection Sort

   Pass 1: Minimum is 2, swap with 5 -> swap count = 1
   Array: {2, 3, 8, 6, 5}
   Pass 2: Minimum is 3, already at position -> no swap
   Pass 3: Minimum is 5, swap with 8 -> swap count = 2
   Array: {2, 3, 5, 6, 8}
   Pass 4: Minimum is 6, already at position -> no swap

2. Step 2: Count total swaps

   Total swaps performed = 2

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Count swaps only when minimum differs from current [OK]

Hint: Count swaps only when minimum differs from current [OK]

Common Mistakes:

• Counting all passes as swaps
• Ignoring when minimum is already at current position
• Assuming swaps equal number of passes