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 librarian wants the books sorted from smallest to largest ID so they are easy to find.

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

📋 What You'll Learn

Create a list of integers called book_ids with the exact values: 45, 12, 78, 34, 23

Create an integer variable called min_index to track the position of the smallest value

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

Swap elements in book_ids to sort the list in ascending order

Print the sorted book_ids list in the format: 12 -> 23 -> 34 -> 45 -> 78 -> null

💡 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 analysis, and optimizing programs.

1

Create the list of book IDs

Create a list of integers called book_ids with these exact values: 45, 12, 78, 34, 23

DSA C++

# Create the list book_ids with the given values
# Your code here

Hint

Use std::vector<int> to create the list and initialize it with the given numbers.

2

Create the variable to track the smallest value index

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

DSA C++

std::vector book_ids = {45, 12, 78, 34, 23};
// Create the variable min_index
# Your code here

Hint

Declare min_index as an integer without initializing it yet.

3

Implement the selection sort logic

Use nested for loops with variables i and j to implement selection sort on book_ids. Inside the outer loop, set min_index = i. Inside the inner loop, update min_index if a smaller value is found. After the inner loop, swap book_ids[i] and book_ids[min_index] if needed.

DSA C++

std::vector book_ids = {45, 12, 78, 34, 23};
int min_index;
// Implement selection sort using for loops
# Your code here

Hint

Use two loops: the outer loop picks the current position, the inner loop finds the smallest value's index. Swap after inner loop ends.

4

Print the sorted list

Print the sorted book_ids list in the format: 12 -> 23 -> 34 -> 45 -> 78 -> null. Use a for loop to print each element followed by ->, and print null at the end.

DSA C++

std::vector book_ids = {45, 12, 78, 34, 23};
int min_index;
for (int i = 0; i < (int)book_ids.size() - 1; i++) {
    min_index = i;
    for (int j = i + 1; j < (int)book_ids.size(); 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 the sorted list
# Your code here

Hint

Use a loop to print each number followed by ->, then print null after the loop.

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