Understanding Selection Sort: A Step-by-Step Guide with Examples

Introduction:

Sorting is like tidying up your room, but for computers. They have different ways of doing it, and one basic method is called Selection Sort. This blog post will help you understand Selection Sort from the ground up, with easy explanations and a hands-on example.

Understanding Selection Sort:

Think of Selection Sort as organizing a deck of cards. You go through the deck, find the smallest card, and put it at the beginning. Then, you repeat this process until the whole deck is sorted.

Step-by-Step Guide to Selection Sort:

Getting Started:

Imagine you have a list of numbers, like [4, 8, 1, 19, 3, 6].

Pretend the list has two parts: the sorted part (currently empty) and the unsorted part (the whole list).

Finding the Smallest Number:

Look at the unsorted part and find the smallest number.

Remember where you found it; this is like marking the smallest card in our deck.

Swapping Numbers:

Swap the smallest number you found with the first number in the unsorted part.

It's like putting the smallest card at the beginning of the deck.

Moving On:

Move the imaginary line between the sorted and unsorted parts one step to the right.

Now, the sorted part has one more number, and the unsorted part has one less.

Repeat Until Done:

Keep finding the smallest number, swapping it, and moving the line until the whole list is sorted.

Complexity Check:

Selection Sort has a time complexity of O(n^2) in the worst and average cases.

It has a space complexity of O(1) since it doesn't require additional memory.

Example of Selection Sort:

Let’s use our list [4, 8, 1, 19, 3, 6] to see how Selection Sort works.

Start:

Unsorted: [4, 8, 1, 19, 3, 6]

Sorted: []

Iteration 1:

Find 1 (at index 2), swap with 4.

Unsorted: [1, 8, 4, 19, 3, 6]

Sorted: [ ]

Iteration 2:

Find 3 (at index 4), swap with 1.

Unsorted: [3, 8, 4, 19, 1, 6]

Sorted: [1]

Iterations 3-6:

Repeat until the list is sorted.

Finish:

Sorted List: [1, 3, 4, 6, 8, 19]

#include<iostream>
using namespace std;

// Function to input elements into the array
void scanArray(int arrayToScan[], int size) {
    for (int i = 0; i < size; i++) {
        cin >> arrayToScan[i];
    }
}

// Function to print elements of the array
void printArray(int arrayToPrint[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arrayToPrint[i] << " ";
    }
}

// Function to perform selection sort on the array
void selectionSort(int arrayToSort[], int size) {
    for (int i = 0; i < size - 1; i++) {
        // Assume the current index is the minimum
        int minIndex = i;

        // Loop to find the index of the minimum element in the unsorted part
        for (int j = i + 1; j < size; j++) {
            if (arrayToSort[j] < arrayToSort[minIndex])
                minIndex = j;
        }

        // Swap the found minimum element with the element at the current index
        if (minIndex != i)
            swap(arrayToSort[i], arrayToSort[minIndex]);
    }
}

int main() {
    // Set the size of the array
    int arraySize = 10;

    // Declare an array of size 'arraySize'
    int myArray[arraySize];

    // Input elements into the array
    scanArray(myArray, arraySize);

    // Perform selection sort on the array
    selectionSort(myArray, arraySize);

    // Print the sorted array
    printArray(myArray, arraySize);

    return 0;
}

Conclusion:

Selection Sort might not be the fastest, but it's a simple way to understand how computers sort things.