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 picking the smallest apple from a basket and putting it in a new row, then picking the next smallest from the rest, until all apples are lined up from smallest to biggest.

Index: 0   1   2   3   4
Array: [7] -> [3] -> [5] -> [2] -> [6]

Dry Run Walkthrough

Input: array: [7, 3, 5, 2, 6]

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] -> [6]

Why: We place the smallest element at the start to begin sorting

Step 2: Find smallest from index 1 to end, swap with index 1

[2] -> [3] -> [5] -> [7] -> [6]

Why: Next smallest is already at index 1, no swap needed

Step 3: Find smallest from index 2 to end, swap with index 2

[2] -> [3] -> [5] -> [7] -> [6]

Why: Smallest from index 2 is 5, no swap needed

Step 4: Find smallest from index 3 to end, swap with index 3

[2] -> [3] -> [5] -> [6] -> [7]

Why: Swap 7 with 6 to put next smallest in place

Step 5: Last element is in place, sorting done

[2] -> [3] -> [5] -> [6] -> [7]

Why: All elements are sorted in ascending order

Result:

Final sorted array: [2] -> [3] -> [5] -> [6] -> [7]

Annotated Code

DSA C

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // assume current i is smallest
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // found smaller element
            }
        }
        // swap arr[i] and arr[minIndex]
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int arr[] = {7, 3, 5, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printArray(arr, n);
    return 0;
}

for (int i = 0; i < n - 1; i++) {

iterate over each position to place the smallest element

int minIndex = i; // assume current i is smallest

start by assuming current position holds smallest value

for (int j = i + 1; j < n; j++) {

check remaining elements to find smaller value

if (arr[j] < arr[minIndex]) { minIndex = j; }

update minIndex when smaller element found

int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;

swap smallest found with current position

Output

2 -> 3 -> 5 -> 6 -> 7 -> null

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 still does O(n^2) comparisons

Edge Cases

empty array

function does nothing and exits safely

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 needed, array remains same

DSA C

if (arr[j] < arr[minIndex]) { minIndex = j; }

When to Use This Pattern

When you need a simple sorting method that finds the smallest item repeatedly, selection sort is a good first choice because it clearly shows the sorting process step by step.

Common Mistakes

Mistake: Swapping elements inside the inner loop instead of after finding the minimum
Fix: Only swap after the inner loop finishes and the minimum index is found

Summary

Selection sort repeatedly finds the smallest element and places it at the front.

Use it when you want a simple, easy-to-understand sorting method for small arrays.

The key insight is to select the smallest remaining item and swap it once per outer loop.

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