Selection Sort
Algorithms
Selection sort is a simple sorting algorithm that repeatedly finds the minimum element from the unsorted portion and places it at the beginning.
Algorithm
The algorithm maintains two subarrays: the sorted subarray and the unsorted subarray. In each iteration, it finds the minimum element from the unsorted subarray and swaps it with the first element of the unsorted subarray.
Time Complexity
Selection sort has a time complexity of in all cases, where is the number of elements.
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 element with the first element of the unsorted portion
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Example usage with different numbers
arr = [45, 23, 78, 12, 56, 89, 34]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)Trace it by hand
Round 1: scan positions 0..4, find min = 10 at index 1. Swap arr[0] and arr[1]:
[10, 29, 14, 37, 13]
Round 2: scan positions 1..4, find min = 13 at index 4. Swap arr[1] and arr[4]:
[10, 13, 14, 37, 29]
Selection sort always does exactly swaps — far fewer than insertion sort's worst case of shifts. That's selection sort's one redeeming property: when swap cost dominates comparison cost (large records, expensive moves), it can beat insertion sort despite having the same comparison count.