How to Implement Selection Sort in Python

You want to learn about Selection Sort—a simple comparison-based sorting algorithm that works by repeatedly finding the minimum (or maximum) element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. It divides the array into two parts: a sorted left portion and an unsorted right portion. Over each iteration, the boundary between these two portions shifts right until the entire array is sorted.

Selection Sort is known for its simplicity (easy to understand and implement) but is inefficient for large datasets due to its O(n²) time complexity. It is ideal for small datasets, embedded systems with limited memory, or scenarios where the number of swaps must be minimized.

Core Principles of Selection Sort

For ascending sorting (finding the minimum element each time), Selection Sort follows these steps:

Initialize the sorted portion: Start with the first element (index 0) as the initial sorted portion (length 1), and the rest of the array as unsorted.
Find the minimum in the unsorted portion: Iterate through the unsorted portion to locate the index of the smallest element.
Swap with the first element of the unsorted portion: Exchange the minimum element with the leftmost element of the unsorted portion—this expands the sorted portion by 1.
Repeat: Move the boundary of the sorted portion one position to the right and repeat steps 2–3 until the entire array is sorted.

Example Walkthrough (Sorting `[64, 25, 12, 22, 11]` Ascending)

Iteration	Sorted Portion	Unsorted Portion	Min Element (Unsorted)	Swap Result
1	`[]`	`[64, 25, 12, 22, 11]`	11 (index 4)	Swap 64 and 11 → `[11, 25, 12, 22, 64]`
2	`[11]`	`[25, 12, 22, 64]`	12 (index 2)	Swap 25 and 12 → `[11, 12, 25, 22, 64]`
3	`[11, 12]`	`[25, 22, 64]`	22 (index 3)	Swap 25 and 22 → `[11, 12, 22, 25, 64]`
4	`[11, 12, 22]`	`[25, 64]`	25 (index 3)	No swap needed → `[11, 12, 22, 25, 64]`
5	`[11, 12, 22, 25]`	`[64]`	64 (index 4)	No swap needed → Sorted array

Selection Sort Implementations (Python)

1. Basic Implementation (Ascending Sort)

Finds the minimum element in the unsorted portion and swaps it to the left:

python

运行

def selection_sort_ascending(arr):
    n = len(arr)
    # Iterate through each position (boundary of sorted/unsorted portions)
    for i in range(n):
        # Step 1: Find the index of the minimum element in unsorted portion [i, n-1]
        min_index = i  # Assume first element of unsorted portion is the minimum
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j  # Update min_index if a smaller element is found
        
        # Step 2: Swap the minimum element with the first element of the unsorted portion
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr

# Test code
if __name__ == "__main__":
    unsorted_arr = [64, 25, 12, 22, 11]
    sorted_arr = selection_sort_ascending(unsorted_arr.copy())  # Use copy to preserve original
    print("Original array:", unsorted_arr)
    print("Ascending sorted array:", sorted_arr)  # Output: [11, 12, 22, 25, 64]

2. Descending Sort (Finding Maximum Element)

To sort in descending order, find the maximum element in the unsorted portion instead:

python

运行

def selection_sort_descending(arr):
    n = len(arr)
    for i in range(n):
        # Find the index of the maximum element in unsorted portion [i, n-1]
        max_index = i
        for j in range(i + 1, n):
            if arr[j] > arr[max_index]:
                max_index = j
        
        # Swap the maximum element with the first element of the unsorted portion
        arr[i], arr[max_index] = arr[max_index], arr[i]
    
    return arr

# Test
unsorted_arr = [64, 25, 12, 22, 11]
sorted_desc = selection_sort_descending(unsorted_arr.copy())
print("Descending sorted array:", sorted_desc)  # Output: [64, 25, 22, 12, 11]

3. Optimized Implementation (Min-Max in One Pass)

Reduce the number of iterations by finding both the minimum and maximum elements in each pass—this sorts the array from both ends (left for min, right for max):

python

运行

def selection_sort_optimized(arr):
    n = len(arr)
    left = 0  # Start of unsorted portion
    right = n - 1  # End of unsorted portion
    
    while left < right:
        # Find min and max indices in [left, right]
        min_index = left
        max_index = left
        for j in range(left + 1, right + 1):
            if arr[j] < arr[min_index]:
                min_index = j
            if arr[j] > arr[max_index]:
                max_index = j
        
        # Swap min element to the left boundary
        arr[left], arr[min_index] = arr[min_index], arr[left]
        
        # Edge case: if max element was at the left boundary (now swapped to min_index)
        if max_index == left:
            max_index = min_index
        
        # Swap max element to the right boundary
        arr[right], arr[max_index] = arr[max_index], arr[right]
        
        # Shrink the unsorted portion
        left += 1
        right -= 1
    
    return arr

# Test
unsorted_arr = [64, 25, 12, 22, 11]
optimized_sorted = selection_sort_optimized(unsorted_arr.copy())
print("Optimized sorted array:", optimized_sorted)  # Output: [11, 12, 22, 25, 64]

Time and Space Complexity

Metric	Value	Explanation
Time Complexity (Best)	O(n²)	Even if the array is already sorted, the algorithm still scans the entire unsorted portion to find min/max
Time Complexity (Worst)	O(n²)	Same as best case—no improvement for reverse-sorted arrays
Time Complexity (Average)	O(n²)	Requires nested loops: outer loop runs n times, inner loop runs ~n/2 times on average
Space Complexity	O(1)	In-place sorting—only constant auxiliary space is used (no extra arrays)
Stability	Unstable	Swapping can change the relative order of equal elements (e.g., `[2a, 2b, 1]` → `[1, 2b, 2a]`)

Pros and Cons of Selection Sort

Pros

Simplicity: Extremely easy to understand and implement—ideal for learning basic sorting concepts.
Minimal Swaps: Only performs O(n) swaps (one per iteration), which is better than Bubble Sort (O(n²) swaps) for datasets where swaps are expensive (e.g., large objects, disk-based data).
In-Place Sorting: Uses O(1) auxiliary space—suitable for memory-constrained systems (e.g., embedded devices).
Predictable Performance: Time complexity is always O(n²), with no variation based on input data (useful for systems requiring consistent execution time).

Cons

Inefficiency for Large Datasets: O(n²) time complexity makes it impractical for large arrays (n > 1,000) — Merge Sort or Quick Sort (O(n log n)) are far faster.
Unstable Sorting: Equal elements may lose their relative order, which is problematic for data with dependent order (e.g., sorted by ID then by name).
Poor Cache Performance: Accesses non-consecutive elements in the inner loop, leading to more cache misses compared to algorithms like Insertion Sort (which accesses contiguous elements).

Real-World Applications of Selection Sort

Small Datasets: Sorting small lists (e.g., sorting a few configuration values in embedded systems).
Embedded Systems: Ideal for systems with limited memory (no extra array needed) and simple processing requirements.
Low-Swap Scenarios: Datasets where swaps are costly (e.g., sorting large structs or objects where copying is expensive).
Educational Purposes: Frequently taught in introductory programming courses to explain basic sorting logic (comparisons, swaps, nested loops).
Legacy Systems: Still used in older codebases where simplicity was prioritized over efficiency, and the dataset size is small.