11.1.1. Motivation for Sorting

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.

Searching through an unsorted array requires checking each element one by one, which takes linear time, denoted as O(n). In contrast, a sorted array allows you to use a binary search approach, which divides the array in half with each step, drastically reducing the number of comparisons needed. This reduction in time taken from linear (O(n)) to logarithmic (O(log n)) is a key reason why sorting is beneficial.

Imagine looking for a specific book in a crowded library with all the books jumbled together (unsorted). You'd have to check each shelf until you find it—very time-consuming! Now, if the library organizes its books alphabetically (sorted), you can skip directly to the section of your book and find it in seconds, as you'd only need to check a few shelves, just like how binary search efficiently locates an element.

Now, there are other advantages to having the elements sorted. For instance, if you want to find the median, the value for which half the elements are bigger, half the elements are smaller. Well, the median of a sorted array is clearly the midpoint of the array. If you want to do some other kind of statistical things, such as building a frequency table of values, when you sort these values they all come together, right. So, all the equal values will be in a contiguous block.

Sorting an array not only improves search efficiency but also simplifies the process for statistical calculations. For example, finding the median value is straightforward in a sorted array since it resides right in the middle. Additionally, when elements are organized, creating frequency tables to count the occurrences of each distinct value becomes easier since identical values cluster together.

This is similar to organizing a collection of colored marbles in a row. If you want to find the most common color or determine the median color, sorting them first makes it easier—you can quickly see where the clusters of colors are and immediately identify the median based on their arrangement.

And in particular, if you want only one copy of every value, if you want to remove all duplicates of the array, then you scan the sorted array from beginning to end and for each block of values keep just one copy.

When an array is sorted, duplicate values appear next to each other. This allows you to iterate through the array and only keep one occurrence of each value, discarding the rest efficiently. By going in a single pass from the start to the end of the sorted array, you significantly reduce the complexity of removing duplicates compared to doing it in an unsorted array.

Think of this as organizing a box of candies where some candies are the same color. If you line them up in a single row, it’s easy to spot duplicates and take them out. If you plan a party and want to bring only one of each type of candy, sorting them first simplifies your task of knowing which ones to keep and which to remove.

So, let us imagine how you would like to sort an array. So, forget about arrays and think about just sorting something, which is given to you as a physical collection of objects. So, say, you are a teaching assistant for a course and the instructor has corrected the exams, now wants you to sort the exam papers in order of marks. So, say, your task is to arrange them in descending order, how would you go about this task?

The introduction to sorting starts by relating it to a real-life scenario where you might need to arrange exam papers based on their scores. In this practical task, determining how to sort them effectively paves the way for learning about the selection sort algorithm, which is a systematic method for sorting data by selecting the smallest or largest elements iteratively.

Imagine you are sorting a pile of exam papers where you need to stack the highest scores on top. You might go through the entire stack, find the highest score, and place it at the top, repeating this process until all papers are sorted. This method directly reflects the selection sort algorithm.

So, one nice strategy is the following. You would go through the entire stack and keep track of the smallest mark that you have seen. At the end of your pass you have the paper in your hand, which has the smallest mark among the marks allotted to all the students. So, you move this to a new pile, then you repeat the process.

In selection sort, the algorithm repeatedly identifies the smallest (or largest, depending on the desired order) element from the unsorted portion of the array and swaps it with the first unsorted element. This process continues until all elements are sorted. The concept is akin to actively searching for the minimum while sorting the elements as you progress.

Think about how you might sort physical playing cards. You could look for the smallest card in the pile (like finding the lowest score), take it out, and put it on a separate pile. Then you'd continue to look for the smallest card in the remaining pile until all cards are sorted. Each round selects the next lowest item until a fully sorted stack is created.

--