GoAlgo

Deep Dive

Understanding Selection Sort in Detail

Selection Sort is a simple, comparison-based algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right, and an unsorted sublist that occupies the rest of the list. The algorithm proceeds by finding the smallest (or largest) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element, and moving the sublist boundaries one element to the right.

Imagine arranging a hand of playing cards. You scan your entire hand to find the smallest card—say, the 2 of Hearts—and place it at the very front. Then, you ignore that first card and scan the remaining cards for the next smallest one, placing it second. You repeat this "selection" process until the entire hand is sorted.

The Logic Behind the Selection

The core mechanism involves finding the minimum value.

Search: The algorithm assumes the first element of the unsorted section is the "minimum."
Scan: It iterates through the rest of the unsorted array to see if there is a value smaller than the current minimum.
Update: If a smaller value is found, the "minimum" tracker is updated to this new index.
Swap: At the end of the pass, the true minimum element is swapped with the first element of the unsorted section.

Step-by-Step Algorithm Trace

Let's trace the algorithm on a small array.

Input Array: [64, 25, 12, 22, 11]

Pass 1:

Find the minimum in [64, 25, 12, 22, 11].
The minimum is 11.
Swap 11 with the first element (64).

Result: [11, 25, 12, 22, 64] (11 is now sorted).

Pass 2:

Find the minimum in the remaining unsorted part [25, 12, 22, 64].
The minimum is 12.
Swap 12 with the first unsorted element (25).

Result: [11, 12, 25, 22, 64] (11, 12 are sorted).

Pass 3:

Find the minimum in [25, 22, 64].
The minimum is 22.
Swap 22 with 25.

Result: [11, 12, 22, 25, 64].

Pass 4:

Find the minimum in [25, 64]. Minimum is 25.
No swap needed (it's already in place).

Result: [11, 12, 22, 25, 64]. The array is sorted.

Code Implementation

Below is the implementation of Selection Sort in multiple programming languages. The algorithm finds the minimum element in the unsorted portion and places it at the beginning.

#include <stdio.h>
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        // Swap the found minimum with first element
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    selectionSort(arr, n);
    
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

C • 29 lines.c

Time & Space Complexity Analysis

Selection Sort is generally slow for large datasets, but it has one specific performance characteristic regarding "swaps" that makes it unique.

Time Complexity

O(n²)All Cases

Even if the array is already sorted, Selection Sort will still scan the entire unsorted list to verify that the first element is indeed the smallest. It does not benefit from an "early exit" flag like Bubble Sort.

Space Complexity

O(1)Constant Space

It sorts in-place and requires no extra memory.

Interactive

Challenge Mode: Selection Race

You've learned the theory. Now, can you spot the minimum faster than the code? Test your scanning speed and sorting logic in our new game!

When to Use Selection Sort?

Selection Sort is rarely the fastest option, but it is useful in specific niche scenarios.

Memory Writes are Expensive

The primary advantage of Selection Sort is that it makes the minimum number of swaps (n-1 swaps in total). If you are writing to a memory device where writing data is costly (like old Flash memory or EEPROM) but reading is cheap, Selection Sort is far more efficient than Bubble Sort or Quick Sort, which move data around constantly.

Small Lists

For very small arrays (e.g., less than 20 items), the overhead of recursive algorithms like Merge Sort or Quick Sort is often slower than the simple loop logic of Selection Sort.

Selection Sort