Practice Selection Sort

Challenge your understanding of Selection Sort with these exercises:

Exercise 1: Manual Trace

Trace through the Selection Sort algorithm step by step with the following array:

[ 29, 10, 14, 37, 5, 24, 8 ]

For each iteration, track:

1. The current partition between sorted and unsorted regions
2. The index and value of the minimum element in the unsorted region
3. Whether a swap is needed, and if so, which elements are swapped
4. The state of the array after each iteration

Exercise 2: Optimization Challenge

Implement a bidirectional Selection Sort that finds both the minimum and maximum elements in each pass. This should reduce the number of passes needed from n to approximately n/2.

Test your implementation with the array below:

[ 8, 4, 1, 56, 3, 7, 22, 12, 9 ]

Exercise 3: Stability Analysis

Selection Sort is not a stable sorting algorithm. Consider the following array with duplicate elements:

[ (4,A), (3,B), (4,C), (2,D), (1,E) ]

Where each pair contains a value and an identifier. Trace through the Selection Sort algorithm and observe how the relative positions of (4,A) and (4,C) change in the final sorted array.

Can you modify the Selection Sort algorithm to make it stable? What would be the impact on its performance?

Exercise 4: Complexity Analysis

For an array of size n:

1. How many comparisons does Selection Sort perform in the best, average, and worst cases?
2. How many swaps does it perform in the best, average, and worst cases?
3. Explain why Selection Sort might be preferred over Bubble Sort or Insertion Sort in certain scenarios.

Interactive practice exercises with step-by-step feedback coming soon!