What is Selection Sort?¶

Selection Sort is a simple and intuitive sorting algorithm. Its core idea is: In each iteration, select the smallest (or largest) element from the unsorted elements and place it at the end of the sorted sequence, until all elements are sorted.

A real-life example: Suppose you need to organize a pile of messy playing cards. Each time, find the smallest card from the remaining ones and place it at the far left, until all cards are sorted.

Basic Idea of Selection Sort¶

1. Outer Loop: Controls the starting position of the current unsorted segment (e.g., the i-th position, starting from 0).
2. Inner Loop: Finds the position of the smallest element in the remaining unsorted elements (from index i to the end of the array).
3. Swap Operation: Swaps the found smallest element with the element at the current starting position to ensure the smallest element is placed in the correct position.
4. Repeat: Continue until the outer loop ends, and all elements are sorted.

Step-by-Step Analysis¶

Take the array arr = {64, 25, 12, 22, 11} as an example:
1. Initial State: The entire array is unsorted, and the sorted segment is empty.
2. First Outer Loop (i=0):
- Inner loop runs from j=1 to 4, finding the minimum value 11 at position 4.
- Swap arr[0] and arr[4], the array becomes {11, 25, 12, 22, 64}. Now the 0-th position is sorted.
3. Second Outer Loop (i=1):
- Inner loop runs from j=2 to 4, finding the minimum value 12 at position 2.
- Swap arr[1] and arr[2], the array becomes {11, 12, 25, 22, 64}. Now the 1st position is sorted.
4. Third Outer Loop (i=2):
- Inner loop runs from j=3 to 4, finding the minimum value 22 at position 3.
- Swap arr[2] and arr[3], the array becomes {11, 12, 22, 25, 64}. Now the 2nd position is sorted.
5. Fourth Outer Loop (i=3):
- Inner loop runs from j=4 to 4, the minimum value is 25 (position 3), so no swap is needed.
6. Termination: The array is fully sorted.

C++ Code Implementation¶

#include <iostream>
using namespace std;

// Selection Sort function: Sorts the array arr, n is the length of the array
void selectionSort(int arr[], int n) {
    // Outer loop: Controls the position where the minimum value should be placed (i ranges from 0 to n-2, since the last element is already sorted)
    for (int i = 0; i < n - 1; i++) {
        // Initially assume the i-th element is the minimum
        int minIndex = i;

        // Inner loop: Find the position of the minimum element in the remaining elements
        for (int j = i + 1; j < n; j++) {
            // If current element is smaller than the element at minIndex, update minIndex
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the current i-th element with the minimum element
        // No effect if minIndex == i (no swap needed)
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

// Main function: Test selection sort
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the length of the array

    // Output the array before sorting
    cout << "Array before sorting: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Call the selection sort function
    selectionSort(arr, n);

    // Output the array after sorting
    cout << "Array after sorting: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation¶

1. Outer Loop: i ranges from 0 to n-2 (the last element is already sorted by the previous iterations). It controls the current position where the minimum value should be placed.
2. Inner Loop: j starts from i+1 and traverses the remaining unsorted elements to find the index of the minimum element (minIndex).
3. Swap Operation: Use a temporary variable temp to swap arr[i] and arr[minIndex], ensuring the minimum element is placed at position i.
4. Time Complexity: O(n²) (due to two nested loops), where n is the array length. Space Complexity: O(1) (only uses a temporary variable for swapping, no extra space).

Sample Output¶

Array before sorting: 64 25 12 22 11 
Array after sorting: 11 12 22 25 64 

Summary¶

The core of Selection Sort is finding the minimum value in each iteration and swapping it. It is suitable for sorting small datasets. Although the time complexity is high, it is simple to implement and requires no additional space, making it a fundamental algorithm for understanding sorting logic. Beginners can enhance their comprehension by manually simulating the sorting process (e.g., the example above).