11.1.7. Recursive Selection Sort

So, this strategy is called selection sort. So, we select in each round the next element, which is the smallest, and therefore the next we put out in the sorted order and move it to its correct position, that is to the end of the final sorted list.

Selection sort involves selecting the smallest element from an unsorted section of the array and placing it in its correct position in the sorted section. The process is repeated: after moving the smallest element to the front, the search continues in the remaining unsorted section until the entire array is sorted.

Imagine a teacher organizing student exam papers based on their scores. They go through the entire stack to find the paper with the lowest score and place it in a separate pile. Then, they repeat this process with the remaining papers, each time finding the lowest and putting it in order. This is akin to how selection sort operates.

So, this particular version of selection sort that we just described, builds the second list. In other words, in order to sort one pile we have to create a second pile of the papers.

In the classic implementation of selection sort, a second list or pile is created to hold the sorted elements. The smallest element is found, removed from the original pile, and placed in the new sorted pile. This can be visualized as transferring all elements from one stack to another while sorting them.

Think of a library where books are to be sorted by genre. Initially, books are stacked randomly. A librarian pulls out the book with the least number of pages and sets it aside in a new shelf that will represent the sorted stack, repeating this until all books are sorted into genres.

Now, we can easily eliminate the second pile of papers if we do the following. When we find the minimum element, we know it must go to the beginning of the list. So, instead of creating a new list we move it to the beginning of the current list. Of course, in the beginning of the current list there is another value. So, we have to do something with that value. You just exchange the positions.

Instead of using a second pile, the in-place selection sort algorithm modifies the original list directly. After finding the minimum element in the unsorted segment, it swaps this minimum element with the first element of that segment. This way, the sorted elements stay within the original array instead of moving to a new structure.

Consider a group of friends arranging themselves in order of height. Instead of moving to a new location, each time they find the shortest friend, they swap places with the person at the front of the group. This method keeps everyone in the same space while they get sorted.

So, this procedure can be described by a very simple iterative algorithm. So, what we do is, that we have, if you remember, we start by scanning the entire array, that is, from 0 to n minus 1, we look for the minimum element in that segment.

The iterative version of selection sort continuously scans the unsorted portion of the array. It looks for the minimum element, places it at the front of the current unsorted section, and reduces the span of the unsorted section after each pass. This continues until the entire array is sorted.

Think of it like finding the smallest fruit in a basket. Each time the person scans the whole basket of fruits, finds the smallest, removes it, and repeats the process until no fruits are left unsorted.

So, how much time does this algorithm take? So, clearly in order to find the minimum element in an unsorted segment of length k we have to scan the entire segment and this takes K steps...

The selection sort algorithm is quadratic in nature, meaning its time complexity is O(n^2). For each element in the array, the algorithm scans all remaining elements to find the minimum. This results in a combined total of operations that approximate n^2 as n grows larger.

Imagine you have a long queue of people where each person must find out their age in relation to the others. Each person checks every other person, leading to every combination of checks being performed, which accumulates over time just like how selection sort accumulates its comparisons.

So, there is another way of looking at selection sort. So, remember we said, that we start by finding the minimum element moving into the front...

The recursive implementation of selection sort divides the array into sorted and unsorted segments. It finds the minimum in the unsorted segment, places it in the sorted section, and then calls itself recursively on the sub-array that remains unsorted until all elements are sorted.

Visualize a series of nested boxes where you take out the smallest box first, place it aside, and repeat the process with the remaining boxes until there's only one left. This mirrors how recursion works as it solves one small problem at a time.

--