11.1.3. Illustration of 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. 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.

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. So, it is much easier to find how many copies of each value are there.

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. So, there are very many different reasons why one may want to sort an array to make further computation on the array much easier.

The motivation for sorting is rooted in the need for efficient searching. When an array is unsorted, searching for an element requires checking each item one by one, resulting in linear time complexity (O(n)). In contrast, a sorted array allows for the use of binary search, reducing the search time to logarithmic complexity (O(log n)). Sorting also facilitates finding statistics like the median, building frequency tables, and removing duplicates—tasks that become trivial in a sorted list.

Imagine you are looking for a specific book in a library. If the books are arranged randomly on the shelves, you would have to check each one until you find the right title. This is like searching in an unsorted array. However, if the books are sorted by title or author, you can quickly look up the location of the book you need, just like using binary search in a sorted array.

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 object. So, say, you are teaching assistant for a course and the instructor, the teacher who is teaching the course 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?

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 smallest mark among the marks allotted to all the students. So, you move this to a new pile, then you repeat the process. You go through the remaining papers after having discarded the smallest one into the new pile and look for the next smallest one, move that on top of the new pile and so on. So, after the second pass you have second smallest mark on the pile.

In the selection sort strategy, you begin by examining all elements to find the smallest one, which you then move to its correct position in the sorted order. After placing the smallest element aside, you disregard it and repeat the process for the remaining elements, continually finding and moving the next smallest element to the correct order. This method ensures that you systematically build a sorted list.

Think of it as sorting a stack of exam papers graded from a course. You check each paper to find the one with the lowest grade and move it to a new stack. Next, you find the lowest grade among the remaining papers and place it above the first in the new stack. You keep doing this until all papers are arranged in descending order of grades.

So, this particular strategy can be illustrated as follows. So, supposing we have this list or array of six elements. So, in the first pass we look for the smallest value. So, the smallest value in this case is 21. So, we move 21 to a new list and remove it from the original list.

Now, we repeat the scan among the remaining values. The value 32 is the smallest one, so we remove that and move it to new list. We keep doing this. So, at the next step, we move 55 and then we move 64 and then we move 74 and then we move 89, right.

The selection sort process is visualized through an example with six elements, where the smallest element (in this case, 21) is identified and moved to a new list. The task continues for each of the remaining elements, ensuring that at the end of the sorting process, the original elements are rearranged in order. Each step illustrates the reduction of the unsorted section until all items are sorted.

Consider sorting a collection of colored balls; you pick the smallest ball (in terms of size) from a pile and place it at the start of a new collection. You then look among the remaining balls for the next smallest and add that to your sorted collection. By continuing this way, you progressively build an entirely sorted collection.

Now, this 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. 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.

In the in-place variant of selection sort, instead of creating a new list to store the sorted elements, the algorithm directly swaps the smallest identified element with the current first element in the original list. This method optimizes memory use, allowing sorting to occur within the original structure without needing additional storage.

If you need to arrange books on a shelf, you wouldn't create a new shelf just for the sorted books. Instead, you would find the lightest book, put it at the front, pushing the others aside as necessary, and continue doing this until all books are in order. This method saves space and is quicker.

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 and in each iteration the segment to be scanned reduces by 1. So, we have over all the number of steps is n plus n minus 1 plus n minus 2 down to 1, which is just the usual summation i is equal to 1 to n of i. And this we know is n into n plus 1 by 2 which is order n square, right.

To determine the time complexity for selection sort, we analyze how many steps it takes to find the minimum in an unsorted segment of size k. On every iteration, we reduce the number of elements we need to consider by one, summing the steps taken until we reach 1. The total steps lead to a quadratic time complexity, expressed as O(n^2), which indicates that performance degrades significantly with larger lists.

Imagine you have a team of 10 people, and you want to find the quickest runner. You would have each person race one after another, making comparisons until only one is left. This means you have to go through many races, giving us a sense of how as teams get bigger (like lists), the effort needed grows more and more.

--