11.1.4. In-Place Selection Sort

So, the most basic motivation for sorting comes from searching. As we have seen, if you have an unsorted array, you have to search for it by scanning the entire array from beginning to end. So, you spend linear time searching for the element, whereas if you had sorted array, you can probe it at the midpoint and use binary search and achieve the same result in logarithmic time, and logarithmic time is considerably faster than linear time.

When working with data, sorting is essential because it enhances search efficiency. If the data is unsorted, you must go through every item one by one (this is linear time). If you sort the data first, you can locate items much quicker by skipping ahead (this is logarithmic time), saving valuable time and effort during searches.

Think of sorting like organizing books on a shelf. If the books are scattered, finding a specific title might take a long time. However, if they are organized alphabetically, you can quickly find the book without checking each one individually.

Now, let us imagine how you would like to sort an array. ... So, this particular 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 works by scanning through the list to find the smallest (or largest) element. It moves that element to the beginning of the list and continues this process with the remaining elements, progressively building a sorted list one item at a time.

Imagine arranging a set of cards by value. You pick the smallest card from the entire deck and place it at the front. Then you pick the smallest card from the remaining cards and place it next to the first, repeating this until all cards are sorted.

So, now, we start from the second element onwards and look for the minimum. ... we keep doing this and without using a second list we are able to do the same sorting that we did before.

In this in-place selection sort method, instead of creating a second list to hold sorted values, you swap the found minimum with the current starting value. This saves space and keeps the sorting process efficient while maintaining order.

Consider sorting fruit in a basket. Instead of transferring fruit to another basket as you sort, you simply take the smallest fruit and place it at the front of the basket and continue until all are in order.

Now, how much time does this algorithm take? ... that we have seen, as the iterative implementation is n square.

The time complexity of the selection sort algorithm is O(n^2). This is because, for each element in the list, you check every other element to find the smallest, which essentially results in a nested loop scenario, slowing down performance as the number of items increases.

If you think of selection sort like a teacher checking each student's exam results one at a time to find the lowest score, you'll soon realize it takes more time to find the lowest score among ten students than just two. This is that quadratic growth as the number of students increases.

Now, there is another way of looking at selection sort. ... So, therefore, you have t n. So, this is the time to find the minimum.

You can also implement selection sort recursively. In this version, after placing the found minimum at its correct position, the sort works on the reduced segment of the list. The base case for this recursion is when only one element remains, which is already sorted.

Imagine sorting a list of names by repeatedly finding the smallest until only one name is left. Each time you sort a smaller batch, it mirrors the recursive method where you keep working with less until sorted.

--