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 selection sort code on the array [3, 1, 4, 2]?

DSA C

void selectionSort(int arr[], int n) {
    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;
    }
}

int main() {
    int arr[] = {3, 1, 4, 2};
    int n = 4;
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 1 3 2 4

B 1 2 3 4

C 3 1 2 4

D 4 3 2 1

💡 Hint

Selection sort finds the smallest element and places it at the start, then repeats for the rest.

Selection sort repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted element. After sorting, the array becomes 1 2 3 4.

🧠 Conceptual

intermediate

Number of swaps in selection sort

For an array of size n, how many swaps does selection sort perform in the worst case?

A 0 swaps

B n swaps

C n * (n - 1) / 2 swaps

D n - 1 swaps

💡 Hint

Selection sort swaps only once per outer loop iteration.

Selection sort performs exactly one swap per outer loop iteration, so total swaps are n - 1.

🔧 Debug

advanced

Identify the bug in selection sort implementation

What error will this selection sort code cause when sorting the array [5, 2, 9]?

DSA C

void selectionSort(int arr[], int n) {
    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 Array index out of bounds error

B No error, sorts correctly

C Infinite loop

D Compilation error

💡 Hint

Check the inner loop condition carefully.

The inner loop uses j <= n which accesses arr[n], out of array bounds causing runtime error.

❓ Predict Output

advanced

Output after partial selection sort pass

What is the state of the array after the first pass of selection sort on [7, 3, 5, 1]?

DSA C

void selectionSortPass(int arr[], int n) {
    int i = 0;
    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;
}

int main() {
    int arr[] = {7, 3, 5, 1};
    int n = 4;
    selectionSortPass(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 3 7 5 1

B 7 3 5 1

C 1 7 5 3

D 1 3 5 7

💡 Hint

Only the first smallest element is swapped with the first element.

After the first pass, the smallest element 1 (at index 3) is swapped with 7 (at index 0), resulting in the array 1 3 5 7.

🧠 Conceptual

expert

Time complexity of selection sort in all cases

What is the time complexity of selection sort in best, average, and worst cases?

A O(n) best, O(n^2) average and worst

B O(n^2) best, O(n) average and worst

C O(n^2) for all cases

D O(n log n) average and worst, O(n) best

💡 Hint

Selection sort always scans the entire unsorted part to find minimum.

Selection sort always performs n*(n-1)/2 comparisons regardless of input order, so time complexity is O(n^2) in all cases.

Practice

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

easy

A. Divide the list and merge sorted parts

B. Swap adjacent elements if they are in wrong order

C. Repeatedly find the smallest element and move it to the front

D. Insert elements into their correct position one by one

Solution

1. Step 1: Understand selection sort process

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

2. Step 2: Compare with other sorting methods

   Unlike bubble sort (swapping adjacent) or merge sort (divide and conquer), selection sort selects the minimum each time.

3. Final Answer:

   Repeatedly find the smallest element and move it to the front -> Option C

4. Quick Check:

   Selection sort = find minimum and swap [OK]

Hint: Selection sort picks smallest and swaps front [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it sorts by inserting elements
• Believing it divides and merges lists

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. arr[i], arr[min_idx] = arr[min_idx], arr[i];

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

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

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

Solution

1. Step 1: Understand swapping in C

   C does not have built-in swap; we use a temporary variable to hold one value during swap.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; uses a temp variable correctly. arr[i] = arr[min_idx]; arr[min_idx] = arr[i]; overwrites arr[i] before saving. swap(arr[i], arr[min_idx]); is invalid syntax in C. arr[i], arr[min_idx] = arr[min_idx], arr[i]; is Python syntax, not C.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in C [OK]

Hint: Use temp variable to swap in C [OK]

Common Mistakes:

• Trying to swap without temp variable
• Using Python or other language syntax
• Overwriting values before saving

3. What will be the output array after the first pass of selection sort on arr = {29, 10, 14, 37, 13}?

medium

A. {10, 29, 14, 37, 13}

B. {29, 10, 14, 37, 13}

C. {13, 10, 14, 37, 29}

D. {10, 14, 29, 37, 13}

Solution

1. Step 1: Find minimum in entire array

   Minimum element is 10 at index 1.

2. Step 2: Swap minimum with first element

   Swap 29 (index 0) with 10 (index 1). Array becomes {10, 29, 14, 37, 13}.

3. Final Answer:

   {10, 29, 14, 37, 13} -> Option A

4. Quick Check:

   First pass swaps smallest to front [OK]

Hint: First pass swaps smallest element to front [OK]

Common Mistakes:

• Not swapping after finding minimum
• Swapping with wrong index
• Confusing first pass with full sort

4. Identify the error in this selection sort snippet and choose the fix:

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;
  }
  arr[i] = arr[min_idx];
  arr[min_idx] = arr[i];
}

medium

A. Swap lines overwrite values; use a temp variable to swap

B. Change inner loop to start from j = 0

C. Remove inner loop; selection sort doesn't need it

D. Use arr[min_idx] = arr[j] instead of arr[min_idx] = arr[i]

Solution

1. Step 1: Analyze swap lines

   Lines arr[i] = arr[min_idx]; arr[min_idx] = arr[i]; overwrite arr[min_idx] with arr[i] after first assignment, losing original value.

2. Step 2: Correct swap method

   Use a temporary variable to hold arr[i], then assign arr[i] = arr[min_idx], then arr[min_idx] = temp to swap correctly.

3. Final Answer:

   Swap lines overwrite values; use a temp variable to swap -> Option A

4. Quick Check:

   Swap needs temp variable to avoid overwrite [OK]

Hint: Use temp variable to swap, not direct assignments [OK]

Common Mistakes:

• Swapping without temp variable
• Changing loop start incorrectly
• Removing necessary inner loop

5. Given the array arr = {64, 25, 12, 22, 11}, after fully sorting it using selection sort, what is the final sorted array?

hard

A. {64, 25, 12, 22, 11}

B. {11, 22, 12, 25, 64}

C. {25, 11, 12, 22, 64}

D. {11, 12, 22, 25, 64}

Solution

1. Step 1: Perform selection sort passes

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

2. Step 2: Confirm final sorted array

   After all passes, array is sorted ascending: {11, 12, 22, 25, 64}.

3. Final Answer:

   {11, 12, 22, 25, 64} -> Option D

4. Quick Check:

   Selection sort fully sorts ascending [OK]

Hint: Selection sort sorts ascending by swapping minimum each pass [OK]

Common Mistakes:

• Stopping after first pass
• Not swapping correctly
• Mixing up element positions