Selection Sort in C++ – A Friendly Guide with Code & Step-by-Step Example

🌟 Introduction

Sorting is one of those classic problems every coder faces, and Selection Sort is a great place to start! Whether you’re prepping for interviews or just want to brush up on your basics, this post will make selection sort crystal clear.

🤔 What is Selection Sort?

Imagine you’re sorting playing cards on a table. You look for the smallest card and put it at the front, then repeat for the rest. That’s exactly how selection sort works:

1. Find the minimum in the unsorted part.
2. Swap it with the first unsorted element.
3. Repeat until everything’s sorted!

🛠️ The Algorithm in Simple Steps

1. Start from the first element.
2. Assume it’s the minimum.
3. Scan the rest to find the real minimum.
4. Swap the found minimum with the current position.
5. Move to the next position and repeat.

Note: Here, after each iteration, the array becomes sorted up to the first index of the range. That is why the starting index of the range increases by 1 after each iteration. This increment is achieved by the outer loop and the starting index is represented by variable i in the following code. And the inner loop(i.e. j) helps to find the minimum element of the range [i…..n-1].

💻 C++ Implementation

Here’s a neat C++ program to see it in action:

#include <iostream>
using namespace std;

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int mini = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[mini]) {
                mini = j;
            }
        }
        // Swap the found minimum with the current element
        swap(arr[mini], arr[i]);
    }
}

int main() {
    int arr[] = {13, 46, 24, 52, 20, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Before selection sort:\n";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << "\n";

    selection_sort(arr, n);

    cout << "After selection sort:\n";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

🔎 Dry Run: Sorting {13, 46, 24, 52, 20, 9}

Let’s walk through what happens, step by step:

Iteration 1 (i = 0):

• Unsorted: {13, 46, 24, 52, 20, 9}
• Minimum is 9 (index 5)
• Swap 13 and 9
• Result: {9, 46, 24, 52, 20, 13}

Iteration 2 (i = 1):

• Unsorted: {46, 24, 52, 20, 13}
• Minimum is 13 (index 5)
• Swap 46 and 13
• Result: {9, 13, 24, 52, 20, 46}

Iteration 3 (i = 2):

• Unsorted: {24, 52, 20, 46}
• Minimum is 20 (index 4)
• Swap 24 and 20
• Result: {9, 13, 20, 52, 24, 46}

Iteration 4 (i = 3):

• Unsorted: {52, 24, 46}
• Minimum is 24 (index 4)
• Swap 52 and 24
• Result: {9, 13, 20, 24, 52, 46}

Iteration 5 (i = 4):

• Unsorted: {52, 46}
• Minimum is 46 (index 5)
• Swap 52 and 46
• Result: {9, 13, 20, 24, 46, 52}

🎉 Final Sorted Array

{9, 13, 20, 24, 46, 52}

✨ Wrapping Up

Selection sort is simple, easy to code, and great for learning the basics of sorting. While it’s not the fastest for large datasets, it’s a perfect stepping stone to more advanced algorithms.

Happy coding! 🚀