Skip to content

Selection Sort

Selection sort is a simple sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front of the list, and a sublist of the remaining unsorted items that occupy the rest of the list.

Algorithm Overview

Selection sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning of the sorted portion. It's called "selection" sort because it repeatedly selects the smallest remaining element.

Key Features

  • Simple Implementation: Easy to understand and implement
  • Not Stable: Does not preserve relative order of equal elements
  • In-Place: Sorts the array without using extra space
  • Not Adaptive: Performance doesn't improve on partially sorted data
  • Consistent Performance: Always makes the same number of comparisons

Time and Space Complexity

  • Time Complexity: O(n²) in all cases (best, average, and worst)
  • Space Complexity: O(1) - sorts in place
  • Comparisons: Always (n-1) + (n-2) + ... + 1 = n(n-1)/2
  • Swaps: At most n-1 swaps (better than bubble sort)

Algorithm Steps

  1. Find the minimum element in the unsorted portion
  2. Swap it with the first element of the unsorted portion
  3. Move the boundary between sorted and unsorted portions one position right
  4. Repeat until the entire array is sorted

Usage Examples

Basic Usage

from algo.algorithms.sorting.selection_sort import selection_sort

# Sort integers
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = selection_sort(numbers)
print(sorted_numbers)  # [11, 12, 22, 25, 34, 64, 90]

# Sort strings
words = ['banana', 'apple', 'cherry']
sorted_words = selection_sort(words)
print(sorted_words)  # ['apple', 'banana', 'cherry']

# Empty array
result = selection_sort([])
print(result)  # []

Educational/Debugging

from algo.algorithms.sorting.selection_sort import selection_sort_verbose

# See step-by-step process
selection_sort_verbose([64, 34, 25, 12])

Output: 

Starting selection sort on: [64, 34, 25, 12]

Step 1: Finding minimum in unsorted portion [0:4]
  Current array: [64, 34, 25, 12]
  Sorted portion: [] | Unsorted portion: [64, 34, 25, 12]
  Starting with minimum candidate: 64 at index 0
    Comparing 34 with current minimum 64 -> New minimum found: 34 at index 1
    Comparing 25 with current minimum 34 -> New minimum found: 25 at index 2
    Comparing 12 with current minimum 25 -> New minimum found: 12 at index 3
  Swapping 64 at position 0 with 12 at position 3
  After swap: [12, 34, 25, 64]

Step 2: Finding minimum in unsorted portion [1:4]
  Current array: [12, 34, 25, 64]
  Sorted portion: [12] | Unsorted portion: [34, 25, 64]
  Starting with minimum candidate: 34 at index 1
    Comparing 25 with current minimum 34 -> New minimum found: 25 at index 2
    Comparing 64 with current minimum 25 -> No change
  Swapping 34 at position 1 with 25 at position 2
  After swap: [12, 25, 34, 64]

Step 3: Finding minimum in unsorted portion [2:4]
  Current array: [12, 25, 34, 64]
  Sorted portion: [12, 25] | Unsorted portion: [34, 64]
  Starting with minimum candidate: 34 at index 2
    Comparing 64 with current minimum 34 -> No change
  No swap needed - minimum element 34 is already in correct position

Final sorted array: [12, 25, 34, 64]

Edge Cases Handled

# Empty array
result = selection_sort([])  # Returns []

# Single element
result = selection_sort([42])  # Returns [42]

# Already sorted (still O(n²) comparisons)
result = selection_sort([1, 2, 3, 4])  # Returns [1, 2, 3, 4]

# Reverse sorted
result = selection_sort([4, 3, 2, 1])  # Returns [1, 2, 3, 4]

# Duplicates
result = selection_sort([3, 1, 3, 1])  # Returns [1, 1, 3, 3]

API Reference

Selection Sort Algorithm Implementation

Selection sort is a simple sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list, and a sublist of the remaining unsorted items that occupy the rest of the list.

Time Complexity: O(n²) in all cases (best, average, and worst)

Space Complexity: O(1) - sorts in place

Stability: Not stable (may change relative order of equal elements)

selection_sort(arr)

Sort an array using the selection sort algorithm.

The algorithm works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. This builds up a sorted portion from left to right.

Parameters:

Name Type Description Default
arr List[T]

List of comparable elements to sort

 required

Returns:

Type Description
List[T]

The sorted list (sorted in-place, but also returned for convenience)

Examples:

>>> selection_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

>>> selection_sort(['banana', 'apple', 'cherry'])
['apple', 'banana', 'cherry']

>>> selection_sort([])
[]

selection_sort_verbose(arr)

Selection sort with detailed step-by-step output for educational purposes.

This version prints each step of the sorting process to help understand how the algorithm works.

Parameters:

Name Type Description Default
arr List[T]

List of comparable elements to sort

 required

Returns:

Type Description
List[T]

The sorted list