11.1. Selection Sort

So, having seen how to search for an element in array, now let us turn to sorting. The most basic motivation for sorting comes from searching. If you have an unsorted array, you have to search for it by scanning the entire array from beginning to end, which takes linear time. If you had a sorted array, you can search using binary search and achieve the same result in logarithmic time, which is significantly faster.

Sorting is primarily motivated by the need to efficiently search for elements. In an unsorted array, every search means checking each item one after the other (linear search), which is slow for large datasets. However, if the array is sorted, you can use binary search, which repeatedly halves the search space, allowing for much faster searches. This difference in efficiency between linear time (O(n)) and logarithmic time (O(log n)) illustrates why sorting is valuable.

Think of sorting like organizing books on a shelf. If your books are scattered (unsorted), finding a particular one takes longer since you need to look through each book one by one. However, if they are grouped by categories and then alphabetically ordered (sorted), you can quickly find the book you want.

There are other advantages to having the elements sorted. For instance, if you want to find the median, the median of a sorted array is clearly the midpoint of the array. Sorting also makes it easier to build a frequency table, as equal values will be adjacent. Additionally, if you want to remove duplicates from the array, a sorted array allows for easy scanning to keep just one copy of each value.

Sorting provides several benefits beyond speedier searches. Finding the median (the middle value) becomes simple, as you just look at the center of a sorted array. Creating frequency tables is easier since duplicates are together, making counting straightforward. Lastly, when removing duplicates, a sorted array allows you to simply scan through once and note the changes, instead of having to check each element against every other element.

Imagine sorting colored marbles. If you arrange them by color, it's easy to spot the median color (say, the middle one in a rainbow spectrum). You can also quickly count how many of each color you have since all the same colors will be next to each other. Removing duplicates is as simple as taking one of each colored marble as you go through the list.

Let us imagine you are tasked to sort exam papers in descending order of marks. One strategy is to traverse the stack, keeping track of the smallest mark. At the end of your pass, you move this paper with the smallest mark to a new pile. Repeating this process gives you a sorted pile. This strategy is known as selection sort.

Selection sort works by repeatedly finding the smallest (or largest, depending on ordering) element from the unsorted section and moving it to the sorted section. You start by looking at the entire set. After identifying the minimum, you move that value to the beginning of the sorted portion. You then proceed with the next smallest from the remaining unsorted items until everything is sorted.

Think of it like picking apples from a tree: you want to gather the biggest apples first. Each time you pick one, you look for the next biggest one until all the apples are collected in order of size.

In selection sort, you scan the array, find the minimum element and swap it with the element at the beginning of the array. After placing this minimum value in its correct position, you continue the process for the remaining unsorted part of the array.

In practice, selection sort involves a nested loop: the outer loop runs through each element, while the inner loop finds the minimum in the unsorted section. Once the minimum is found, it is swapped with the first unsorted element, extending the sorted section by one until the entire array is sorted.

Imagine organizing a drawer full of random items. You start by removing each item one by one, but each time you find the smallest item to place in a new, organized section. After each selection, the organized section grows until all items are sorted.

The time complexity of selection sort is O(n²) because you need to scan the remaining unsorted items to find the minimum multiple times. As you proceed, the number of comparisons needed decreases, resulting in a sequence: n + (n-1) + (n-2) + ... + 1.

Selection sort is inherently inefficient for large lists because it involves multiple iterations over the list. As each iteration fixes one element in its final position, the remaining elements to check decrease by one each time. Adding these comparisons leads to a quadratic time complexity of O(n²) because on average, you'll have to look at about half the elements on each pass through the array.

Consider a race where each contestant needs to find the fastest runner. Every contestant first races against all others. The total time taken accumulates since each round eliminates one contestant but many races are needed before everyone is sorted!

We can also view selection sort recursively. At each step, find the minimum element in the unsorted part and recursively sort the smaller section until the base condition is reached where no elements are left to sort.

In a recursive viewpoint, selection sort involves defining a base case where no sorting is needed (like an array with only one element). Then, for each recursive call, you find the minimum in the current segment and move it, adjusting the unsorted section, until the entire array is sorted.

This process resembles a series of class presentations where each student prepares to present only on the topic of the other students who haven't presented yet. As the minimum presenter is found, they go, leaving the rest to continue adjusting their order.

--