11.1.6. Time Complexity of Selection Sort

Selection sort involves iteratively picking the smallest element from the unsorted portion of the array and moving it to the front. Specifically, the algorithm works by scanning the entire array to find the minimum element and placing it in the first position. After this, it continues to the next position, repeating the process until the entire array is sorted.

Selection sort is a simple sorting algorithm. It operates by repeatedly selecting the smallest (or largest, depending on the order) element from the unsorted sub-array and swapping it with the first unsorted element. In the first pass, you select the smallest number in the entire array, swap it with the first position, and in each subsequent pass, you ignore the sorted portion and repeat the process for the rest of the array until all elements are sorted.

Imagine you have a stack of cards that you want to arrange in ascending order. You would first look at every card to find the one with the lowest number and move it to the top of the stack. Next, you would look at the remaining cards and do the same to find the next lowest number, and so forth until all cards are in order.

To understand the time complexity of selection sort, we analyze the number of comparisons it requires. In the first iteration, it scans n elements; in the second, it scans n-1; this continues until it scans just 1 element. The total number of comparisons made is thus n + (n - 1) + (n - 2) + ... + 1, which can be simplified to n(n + 1)/2, leading to a time complexity of O(n²).

The selection sort algorithm's time complexity is derived from the fact that in each iteration, it scans through the unsorted section of the array to find the smallest element. This means that for an array of size n, the first iteration takes n comparisons, the second takes n-1, and this pattern continues down to 1. The total is the sum of the first n natural numbers, which is calculated as n(n + 1)/2. Thus, as the array size increases, the number of comparisons grows quadratically, giving a complexity of O(n²).

Think of sorting 10 different colored blocks. In the first round, you check each block to pick the smallest. For next, you check 9 remaining blocks, then 8, and so on. You notice that the amount of checking you need to do increases quickly as you add more blocks, illustrating why it becomes much slower to sort larger numbers—this helps explain the O(n²) complexity.

The selection sort can also be expressed in a recursive manner, where you sort a segment of the array by finding the minimum value, swapping it, and then recursively sorting the remaining elements. This continues until you reach a base case where the segment to sort is of length 1.

In a recursive implementation of selection sort, you would define a function that sorts an array from a start position to its end. It checks for the minimum value, swaps it to the current position, and then calls itself to sort the remaining part of the array. This continues until there's only one element left in the segment, which is naturally sorted. The efficiency and complexity remain the same as the iterative approach because the fundamental operation hasn't changed.

Imagine a teacher sorting student grades in a recursive manner. They first find the lowest grade, sort it to the front, and then focus on the remaining students. They keep narrowing down their focus until there’s just one student left, who doesn’t need sorting. This ongoing refinement mirrors the recursive sorting process.

--