Mastering Algorithms

Selection Sort

Overview

Selection Sort is a simple comparison-based sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist. The algorithm repeatedly finds the minimum (or maximum) element from the unsorted sublist and moves it to the beginning of the sorted sublist.

The algorithm maintains two subarrays: one that is already sorted (initially empty) and one that is unsorted. In each iteration, it selects the smallest element from the unsorted subarray and swaps it with the leftmost element of the unsorted subarray.

How It Works

The algorithm works by:

  1. Finding the minimum element in the unsorted portion of the array
  2. Swapping it with the first element of the unsorted portion
  3. Moving the boundary between sorted and unsorted portions one position to the right
  4. Repeating until the entire array is sorted

Algorithm


SelectionSort(arr):
    n = length of arr
    for i = 0 to n - 1:
        min_index = i
        for j = i + 1 to n - 1:
            if arr[j] < arr[min_index]:
                min_index = j
        swap arr[i] and arr[min_index]

Implementation


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

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n²) - still needs to check all elements
    • Average Case: O(n²)
    • Worst Case: O(n²) - always performs n(n-1)/2 comparisons
  • Space Complexity: O(1) - only uses a constant amount of extra space

Selection Sort always performs O(n²) comparisons regardless of input order, making it inefficient for large datasets. However, it minimizes the number of swaps (only n swaps in worst case).

Characteristics

  • Stable: No - may change relative order of equal elements
  • In-place: Yes - only requires O(1) extra space
  • Adaptive: No - always performs the same number of comparisons
  • Online: No - requires the entire array to be present

When to Use Selection Sort

Selection Sort is rarely used in practice but can be useful:

  • For educational purposes to understand sorting concepts
  • When the cost of writing to memory is high (minimizes swaps)
  • For very small datasets
  • When simplicity is more important than efficiency

Example

Sorting [64, 25, 12, 22, 11]: 

Initial: [64, 25, 12, 22, 11]
Pass 1:  [11, 25, 12, 22, 64]  (11 is minimum, swap with 64)
Pass 2:  [11, 12, 25, 22, 64]  (12 is minimum, swap with 25)
Pass 3:  [11, 12, 22, 25, 64]  (22 is minimum, swap with 25)
Pass 4:  [11, 12, 22, 25, 64]  (25 is already in place)
Sorted:  [11, 12, 22, 25, 64]

Related Algorithms

Explore other sorting algorithms: