Selection Sort Algorithm in DSA C - Build from Scratch

Selection Sort Algorithm

📖 Scenario: You are helping a librarian organize a small shelf of books by their ID numbers. The IDs are stored in an array, and you want to sort them from smallest to largest so it's easier to find any book.

🎯 Goal: Build a program that sorts an array of book IDs using the selection sort algorithm. You will create the array, set up a variable to track the minimum index, implement the sorting logic, and finally print the sorted array.

📋 What You'll Learn

Create an integer array called book_ids with these exact values: 29, 10, 14, 37, 13

Create an integer variable called min_index to track the index of the smallest value during sorting

Use nested for loops with variables i and j to implement the selection sort algorithm

Swap elements in book_ids to sort the array in ascending order

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Sorting is a common task in organizing data, like arranging books, files, or records in order.

💼 Career

Understanding sorting algorithms like selection sort helps in software development, data processing, and optimizing performance.

1

Create the array of book IDs

Create an integer array called book_ids with these exact values: 29, 10, 14, 37, 13

DSA C

#include 

int main() {
    // Create the array book_ids with values 29, 10, 14, 37, 13
    // Your code here

    return 0;
}

Hint

Use int book_ids[5] = {29, 10, 14, 37, 13}; to create the array.

2

Create the variable to track minimum index

Create an integer variable called min_index inside main to track the index of the smallest value during sorting

DSA C

#include 

int main() {
    int book_ids[5] = {29, 10, 14, 37, 13};
    // Create min_index variable
    // Your code here

    return 0;
}

Hint

Declare int min_index; inside main.

3

Implement the selection sort algorithm

Use nested for loops with variables i and j to implement the selection sort algorithm on book_ids. Use min_index to track the smallest element index and swap elements to sort the array in ascending order.

DSA C

#include 

int main() {
    int book_ids[5] = {29, 10, 14, 37, 13};
    int min_index;

    // Implement selection sort using for loops and min_index
    // Your code here

    return 0;
}

Hint

Use two for loops: outer loop with i from 0 to 3, inner loop with j from i+1 to 4. Update min_index when a smaller element is found. Swap after inner loop.

4

Print the sorted array

Use a for loop with variable i to print all elements of book_ids separated by spaces after sorting

DSA C

#include 

int main() {
    int book_ids[5] = {29, 10, 14, 37, 13};
    int min_index;

    for (int i = 0; i < 4; i++) {
        min_index = i;
        for (int j = i + 1; j < 5; j++) {
            if (book_ids[j] < book_ids[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            int temp = book_ids[i];
            book_ids[i] = book_ids[min_index];
            book_ids[min_index] = temp;
        }
    }

    // Print sorted array elements separated by spaces
    // Your code here

    return 0;
}

Hint

Use a for loop from 0 to 4 and printf("%d ", book_ids[i]); to print each element with a space.

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