implement the selection sort algorithm

What Selection Sort Actually Is

Selection sort is one of the simplest sorting algorithms you'll encounter. It works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. That's it. No magic, no complexity.

The algorithm divides the array into two parts: sorted and unsorted. You start with an empty sorted section and grow it one element at a time by grabbing the smallest item from the unsorted section.

It's not fast. It's not clever. But it's easy to understand and implement, which makes it useful for learning and small datasets.

How Selection Sort Works

Here's the step-by-step process:

1. Start at index 0. This is where you'll place the smallest element found.
2. Scan through the entire array to find the minimum value.
3. Swap the minimum value with the element at the current position.
4. Move to the next position (index 1, then 2, etc.).
5. Repeat until you've sorted the entire array.

Think of it like finding the shortest person in a line and moving them to the front, then finding the next shortest and moving them to second place, and so on.

Implementation in Python

Here's a clean, working implementation:

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # Find the minimum element in the remaining unsorted array
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap the found minimum with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

Test it:

numbers = [64, 25, 12, 22, 11]
print(selection_sort(numbers))
# Output: [11, 12, 22, 25, 64]

Implementation in JavaScript

function selectionSort(arr) {
    const n = arr.length;
    
    for (let i = 0; i < n; i++) {
        let minIdx = i;
        
        // Find the minimum in the rest of the array
        for (let j = i + 1; j < j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // Swap
        if (minIdx !== i) {
            [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
        }
    }
    
    return arr;
}

Implementation in C++

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 if minimum is not at current position
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

Time and Space Complexity

Selection sort has a fixed performance profile. It doesn't adapt to input data like quicksort or mergesort do.

The algorithm performs n(n-1)/2 comparisons regardless of the input. That's roughly 500,000 comparisons for an array of 1,000 elements.

When to Use Selection Sort

Selection sort is appropriate when:

• You're working with small datasets (under 1000 elements)
• Memory is extremely constrained (O(1) space)
• You need a simple implementation without recursion
• You're learning sorting algorithms and want to understand the mechanics

Skip selection sort when:

• You're dealing with large datasets where performance matters
• Data is frequently accessed or sorted in real applications
• You need adaptive sorting (where performance improves for nearly-sorted data)

Pros and Cons

Pros:

• Simple to understand and code
• In-place sorting with O(1) space complexity
• Performs well on small arrays
• Number of swaps is at most n-1 (useful when writes are expensive)

Cons:

• O(n²) time makes it impractical for large datasets
• Not stable by default (equal elements may change relative order)
• Doesn't adapt to existing order in the data

Getting Started

To practice selection sort:

1. Copy the Python implementation above into a file
2. Create test arrays with random numbers, sorted arrays, and reverse-sorted arrays
3. Add print statements to see how the array changes after each iteration
4. Count the comparisons and swaps to verify the O(n²) behavior
5. Modify the code to track the minimum element's index

Try these exercises:

• Sort an array of 10, 100, and 1000 elements. Time each operation.
• Modify the code to find the maximum instead of minimum
• Implement a version that sorts in descending order

The Bottom Line

Selection sort isn't winning any performance awards. It's slow by modern standards and other algorithms beat it consistently. But it teaches core concepts—finding minimums, in-place swapping, and divide-and-conquer thinking—that apply everywhere in programming.

Learn it. Practice it. Then move on to quicksort or mergesort for anything serious.