Selection Sort

TL;DR

Selection Sort repeatedly selects the smallest (or largest) element from the unsorted portion and swaps it with the first unsorted element. It divides the array into a sorted and an unsorted region and expands the sorted region one element at a time.

1. Algorithm Steps

1. Start from index i = 0.

2. Assume i is the index of the smallest element.

3. Traverse the rest of the array (j = i+1 to n-1) to find the true smallest element.

4. Swap the smallest found with the element at index i.

5. Move i one step to the right and repeat until the array is sorted.

2. Complexity

| Case | Comparisons | Swaps | Notes |

| ------------- | -------------- | --------- | ------------------------------- |

| Worst | O(n²) | O(n) | Every element compared with rest |

| Average | O(n²) | O(n) | No adaptive behavior |

| Best | O(n²) | O(n) | No early exit even if sorted |

| Space | O(1) extra | – | In-place sorting |

| Stability | ❌ Not stable | – | Can disrupt equal elements’ order |

3. Optimizations & Variants

• Minimum swaps: Only one swap per outer loop, making it better than bubble sort in terms of write operations.

• Stable Selection Sort: You can make it stable by shifting instead of swapping (less efficient).

• Reverse Sort: Modify the comparison to > to sort in descending order.

4. Reference Python Implementation

def selectionSort(array):

for i in range(len(array)):

smallestIdx = i

for j in range(i + 1, len(array)):

if array[j] < array[smallestIdx]:

smallestIdx = j

array[i], array[smallestIdx] = array[smallestIdx], array[i]

return array

5. Practice

Prompt: Write a function that sorts an array of integers using Selection Sort.

Sample Input: [8, 5, 2, 9, 5, 6, 3]

Expected Output: [2, 3, 5, 5, 6, 8, 9]

Optimal Time & Space Complexity:

• Time: O(n²) always

• Space: O(1)

6. When (Not) to Use Selection Sort

• ✅ Use when minimizing the number of writes/swaps is critical (e.g., in flash memory).

• ❌ Avoid for large datasets due to quadratic time complexity.

• ❌ Not adaptive — performs equally badly on sorted inputs.

7. Quick Self-Check

1. How does selection sort minimize swaps compared to bubble sort?

2. Why is selection sort not stable by default?

3. Can selection sort be made stable without affecting time complexity?

4. What happens if all elements are already sorted?

8. Further Reading

• Introduction to Algorithms (CLRS), Section 2.2

• Visualgo.net

• CP-Algorithms: Selection Sort

Stay sharp — always pick the right tool for the job, just like Selection Sort picks the smallest item each time! 🧠🔍