Selection Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Selection Sort Algorithm

Start with unsorted array

↓

Set i = 0 (start index)

↓

Find min element from i to end

↓

Swap min element with element at i

↓

Increment i

↓

Is i < array length - 1?

No→Sorted array, Done

↩Back to find min element

Selection sort repeatedly finds the smallest element in the unsorted part and swaps it to the front, moving the boundary of sorted and unsorted parts forward.

Execution Sample

DSA C++

int arr[] = {64, 25, 12, 22, 11};
int n = 5;
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]);
}

Sorts the array by selecting the minimum element from the unsorted part and swapping it with the first unsorted element.

Execution Table

Step	Operation	i	j	min_idx	Array State	Action
1	Initialize i=0	0	-	0	[64, 25, 12, 22, 11]	Start outer loop
2	Compare arr[j] with arr[min_idx]	0	1	0	[64, 25, 12, 22, 11]	25 < 64? Yes, min_idx=1
3	Compare arr[j] with arr[min_idx]	0	2	1	[64, 25, 12, 22, 11]	12 < 25? Yes, min_idx=2
4	Compare arr[j] with arr[min_idx]	0	3	2	[64, 25, 12, 22, 11]	22 < 12? No, min_idx=2
5	Compare arr[j] with arr[min_idx]	0	4	2	[64, 25, 12, 22, 11]	11 < 12? Yes, min_idx=4
6	Swap arr[min_idx] and arr[i]	0	-	4	[11, 25, 12, 22, 64]	Swap 64 and 11
7	Increment i=1	1	-	1	[11, 25, 12, 22, 64]	Start next outer loop
8	Compare arr[j] with arr[min_idx]	1	2	1	[11, 25, 12, 22, 64]	12 < 25? Yes, min_idx=2
9	Compare arr[j] with arr[min_idx]	1	3	2	[11, 25, 12, 22, 64]	22 < 12? No, min_idx=2
10	Compare arr[j] with arr[min_idx]	1	4	2	[11, 25, 12, 22, 64]	64 < 12? No, min_idx=2
11	Swap arr[min_idx] and arr[i]	1	-	2	[11, 12, 25, 22, 64]	Swap 25 and 12
12	Increment i=2	2	-	2	[11, 12, 25, 22, 64]	Start next outer loop
13	Compare arr[j] with arr[min_idx]	2	3	2	[11, 12, 25, 22, 64]	22 < 25? Yes, min_idx=3
14	Compare arr[j] with arr[min_idx]	2	4	3	[11, 12, 25, 22, 64]	64 < 22? No, min_idx=3
15	Swap arr[min_idx] and arr[i]	2	-	3	[11, 12, 22, 25, 64]	Swap 25 and 22
16	Increment i=3	3	-	3	[11, 12, 22, 25, 64]	Start next outer loop
17	Compare arr[j] with arr[min_idx]	3	4	3	[11, 12, 22, 25, 64]	64 < 25? No, min_idx=3
18	Swap arr[min_idx] and arr[i]	3	-	3	[11, 12, 22, 25, 64]	Swap 25 and 25 (no change)
19	Increment i=4	4	-	4	[11, 12, 22, 25, 64]	Outer loop ends, array sorted

💡 i reaches 4, condition i < n-1 (4 < 4) is False, sorting complete

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 15	After Step 18	Final
i	0	0	1	2	3	4
min_idx	0	4	2	3	3	4
Array	[64, 25, 12, 22, 11]	[11, 25, 12, 22, 64]	[11, 12, 25, 22, 64]	[11, 12, 22, 25, 64]	[11, 12, 22, 25, 64]	[11, 12, 22, 25, 64]

Key Moments - 3 Insights

Why do we swap after finding the minimum element instead of swapping every time we find a smaller element?

We only swap once per outer loop after finding the minimum to reduce unnecessary swaps. See steps 2-5 where min_idx updates but swap happens only at step 6.

Why does the inner loop start from j = i + 1 instead of j = 0?

Because elements before i are already sorted, so we only search for the minimum in the unsorted part. This is shown in the execution_table where j starts from i+1 each time.

What happens when min_idx equals i during swap?

Swapping an element with itself does nothing, but the algorithm still performs the swap step for consistency, as seen in step 18.

Visual Quiz - 3 Questions

Look at the execution table at step 6, what is the array state after the swap?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 6 in the execution_table.

At which step does the outer loop variable i become 2?

A Step 7

B Step 12

C Step 11

D Step 15

💡 Hint

Look at the 'i' column in the execution_table and find when i changes to 2.

If the array was already sorted, how would the number of swaps change?

A Swaps would stay the same

B Swaps would decrease to zero

C Swaps would increase

D Swaps would be random

💡 Hint

Selection sort always swaps once per outer loop even if the minimum is at the current position, see step 18.

Concept Snapshot

Selection Sort Algorithm:
- Repeatedly find the minimum element from unsorted part
- Swap it with the first unsorted element
- Outer loop runs from i=0 to n-2
- Inner loop finds min_idx from i+1 to end
- Swaps happen once per outer loop
- Time complexity: O(n²), in-place sorting

Full Transcript

Selection sort works by dividing the array into sorted and unsorted parts. It starts at the beginning, finds the smallest element in the unsorted part, and swaps it with the first unsorted element. This process repeats, moving the boundary of sorted elements forward until the whole array is sorted. The inner loop finds the minimum element index, and the outer loop swaps it into place. Even if the minimum is already at the current position, a swap is performed for consistency. The algorithm runs in O(n squared) time and sorts the array in place.

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