Selection Sort Algorithm in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Selection Sort on a small array

What is the output of the following C++ code after performing selection sort on the array?

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;
        }
    }
    int temp = arr[min_idx];
    arr[min_idx] = arr[i];
    arr[i] = temp;
}
for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
}

A 64 25 12 22 11

B 25 12 22 11 64

C 11 12 22 25 64

D 11 22 12 25 64

💡 Hint

Selection sort finds the smallest element and swaps it with the first unsorted element.

Selection sort repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted element, resulting in a sorted array.

🧠 Conceptual

intermediate

Number of swaps in Selection Sort

How many swaps does the selection sort algorithm perform on an array of size n in the worst case?

A n * (n - 1) / 2

B n - 1

C n

D n * log n

💡 Hint

Selection sort swaps only once per outer loop iteration.

Selection sort performs exactly one swap per iteration of the outer loop, resulting in n - 1 swaps in total.

🔧 Debug

advanced

Identify the bug in this selection sort code

What error will occur when running this selection sort code snippet?

DSA C++

int arr[] = {3, 1, 4, 2};
int n = 4;
for (int i = 0; i < n; 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;
}

A Runtime error: Array index out of bounds

B No error, sorts correctly

C Compilation error due to missing semicolon

D Logical error: does not sort the array

💡 Hint

Check the inner loop boundary condition carefully.

The inner loop uses j <= n which accesses arr[n], an invalid index causing runtime error.

🚀 Application

advanced

Selection Sort on Linked List

Which of the following statements about applying selection sort on a singly linked list is true?

A Selection sort can be applied by swapping node values without changing links.

B Selection sort requires reversing the linked list first.

C Selection sort cannot be applied to linked lists.

D Selection sort requires converting the list to an array first.

💡 Hint

Think about how swapping values differs from swapping nodes.

Selection sort can be done on linked lists by swapping the data inside nodes, avoiding complex pointer changes.

❓ Predict Output

expert

Output after partial selection sort iterations

Given the array and partial selection sort code below, what is the array state after the second iteration of the outer loop?

DSA C++

int arr[] = {29, 10, 14, 37, 13};
int n = 5;
for (int i = 0; i < 2; 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;
}
// Print array
for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
}

A 13 10 14 37 29

B 10 14 13 37 29

C 29 10 14 37 13

D 10 13 14 37 29

💡 Hint

Trace the first two passes of selection sort carefully.

After first iteration, smallest element 10 is at index 0; after second, next smallest 13 is at index 1.

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