Previous Topic

What Is Selection Sort?

Selection sort is a straightforward, comparison-based sorting algorithm. It partitions the array into a sorted prefix and an unsorted suffix. On each pass, it finds the smallest (or largest) element in the unsorted portion and swaps it into the next position of the sorted prefix.

How It Works: Step-by-Step

1. Start with the first index i = 0.
2. Scan the unsorted portion (i through end) to find the index of the minimum element.
3. Swap that minimum element with the element at index i.
4. Increment i and repeat until the array is sorted.

Pseudocode

procedure selection_sort(A):
  n = length(A)
  for i from 0 to n - 2:
    min_index = i
    for j from i + 1 to n - 1:
      if A[j] < A[min_index]:
        min_index = j
    if min_index != i:
      swap A[i], A[min_index]
  return A

Example Walkthrough

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

1. i=0: Minimum in [64, 25, 12, 22, 11] is 11 → swap with 64 → [11, 25, 12, 22, 64]
2. i=1: Minimum in [25, 12, 22, 64] is 12 → swap with 25 → [11, 12, 25, 22, 64]
3. i=2: Minimum in [25, 22, 64] is 22 → swap with 25 → [11, 12, 22, 25, 64]
4. i=3: Minimum in [25, 64] is 25 → swap with 25 (no change) → [11, 12, 22, 25, 64]

Now sorted.

Correctness Intuition

• Loop invariant: Before each outer-loop iteration i, the first i elements form the i smallest elements in sorted order.
• Maintenance: We select the smallest element from the remainder and place it at position i.
• Termination: When i reaches n−1, all elements are in place.

Complexity and Properties

• Time complexity (best/average/worst): O(n^2) comparisons; about n(n−1)/2 comparisons in total.
• Swaps: At most n−1, which is fewer than many simple sorts (e.g., bubble sort).
• Space complexity: O(1) extra space (in-place).
• Stability: Not stable by default (equal elements can be reordered). A stable variant can be implemented by inserting the minimum via shifting instead of swapping.
• Adaptivity: Not adaptive; performance does not improve on partially sorted input.

When to Use

• Small arrays where implementation simplicity is valued.
• Situations where minimizing the number of writes/swaps matters (e.g., limited write endurance).
• Educational contexts to illustrate selection and in-place sorting concepts.

Variations and Related Ideas

• Stable selection sort: Instead of swapping, remove the minimum and shift elements right to maintain stability (higher constant factors).
• Bidirectional selection sort: In each pass, select both minimum and maximum and place them at both ends, reducing passes by half but still O(n^2).
• Heapsort: Can be seen as an optimized selection process using a heap to reduce selection from O(n) to O(log n), achieving O(n log n) time.

Common Pitfalls

• Incorrectly updating the minimum index during the inner loop.
• Unnecessary swaps when the minimum is already at position i.
• Assuming stability when using basic swapping.

Practice Ideas

• Implement selection sort for ascending and descending order.
• Write a stable variant using element shifting and compare performance.
• Count comparisons and swaps to empirically verify complexity.
• Compare with insertion sort and bubble sort on various input patterns.

Next Topic