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.