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.

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.

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.

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.

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.