Tip:
Highlight text to annotate it
X
In our previous lesson, we tried to understand the importance of sorting as a computational
problem. We have so many sorting algorithms designed over a period of time, mostly to
improve upon the previously designed algorithms. Now we will study and analyze these algorithms
one by one and the first one that we want to talk about, that we will be covering in this lesson
is Selection sort. Selection Sort in my opinion is the simplest sorting algorithm and this
is what one would do most intutively. Ok, so let's get started! Let's think of a simple
sorting scenario. Let's say we have a set of cards, and we want to arrange these cards
in increasing order of rank. One simple thing we can do is initially, we keep all the cards
in our left hand and then first we can select the minimum card out of these cards and move
it to the right hand. Now, once again from whatever card is left in the left hand, we
can select the minimum and move it to the right hand, next to previous card in the right
hand. We can go on repeating this process. So, at any stage during the process, the left
hand will be an unsorted set of cards and the right hand at any stage will be sorted
set of cards. So, after 3 and 4, 6 will go to the right hand and finally 9 will go. So,
in the end, right hand will be a sorted arrangement of cards. Cards will be sorted in increasing
order of rank. Now, let's say we want to write program to sort a list of integers, given
to us in the form of an array something like this. Given an array of 6 integers here, so
we have indices from 0 to 5 and let's name this array A. To sort this list, we can do
soemthing similar to what we were doing in our cards example. We can create another array,
of same size as A. So, we have another array of size 6, let's name this B. Now, we can
start creating B as a sorted list, by selecting the minimum from A. At each step there will
be multiple passes on A. In the first pass, 1 will be the minimum, so 1 will go at 0th
position in B. Now, there should be a way to mark that 1 has already been selected,
so, it is not cosidered the 2nd time. One way to do this can be, we can replace the
selected element by some very large integer, which is guranteed to be the maximum in the
array at any step. We can choose this max to be something like the largest possible
value in a 32 bit integer, and now, we will scan A again for the second largest element
that will go to the 1th index in B. That element will be 2, so 2 again will be replaced by
MAX. And now the minimum is 3, and we will go on doing this until all the positions in B are filled. In the end we can copy the
content of B back to A. So, A itself will be come the sorted arrangement of it's elements.
This logic will work fine, but if you see, there is this extra memory requirement for
this auxiliary array or this temprary array B that we are creating and larger the size
of A, larger is the extra memory requirement for creation of this temporary array B. So,
this is not an inplace sorting algorithm. An inplace sorting algorithm takes constant
amount of extra memory for sorting the collection. In this case, the amount of extra memory will
be proportional to the size of the input array A. We can do something similar where we can
select the minimum element at each step but we will not have to use this extra array,
this extra memory and the algorithm will be in place. I have drawn this unsorted list
again, what we will do now is once again we will look for the minimum element in the array.
So, we will scan the whole array to find the minimum. The minimum in the array is 1. Now
instead of filling up 1 at 0th index in another array B, what we can do is, we can swap 1
with the element at 0th index because that's where 1 belongs, it belongs to 0th index. So, 1 goes
to 0th index and 2 comes to index 3. Now, we need to look for the next minimum and 1
need not be considered and if you see, it's pretty easy now. We can scan all the elements
from 1 to 5 in order to find the second minimum. The minimum in the range 1 to 5 is 2 at index
3. Now, 2 deserves to be at position 1. So, what we can do is we can swap 2 with the element
at position 1, which is 7. This is how things will look after swapping, so second minimum
goes at second position which is index 1. And now, we have to look for the next minimum
in index range 2 to 5. So, as you can see in each pass we are finding out the element
that should go to a particular position and at any point during this whole process, the
array is divided into two parts. Some part of it is sorted. So, the cells in brown here
are sorted. With each pass, we add one more cell to the sorted part.And eventually, the
whole array will be sorted. The minimum in the index 2 to 5 is 3, so, 3 needs to go at
position 2, so it needs to be swapped with 4. Now, we are sorted till position 2, and
we will go on like this. 5 is at its appropriate position, it does not need to be swapped.
If we have n elements, after n-1 passes, we will have only one more cell left, so that
anyway will be at it's appropriate position. So, finally our list is sorted. This particular
n place of logic of selecting the minimum, in each pass and putting it at it's appropriate
position is Selection Sort algorithm. Let's now quickly write pseudo code for this algorithm.
We will write a function named Selection Sort, that will take the array and the number of
elements in the array as argument and the logic will go something like this. We will
run one loop with a variable i starting 0 all the way till n-1, and in each iteration
of this loop, we will set the element at ith position appropriately. So, first we will
put the minimum at 0th position and then we will put the second minimum at 1th position
and so on. In face we only need to run this loop till n-2 because once we are done with
all i's till n-2, the element at position n-1 will anyway be appropriate, at the correct
position. Now, inside this for loop, we will have another variable, that will store the
index of the minimum element. For i-th element, to find the minimum, we will scan the array
from i till n-1. So, what we can do is initially we can say that ith element is the minimum
element and then we can run a loop from i till n-1 and while scanning if we find any
j, which is having an element which is lesser than the current minimum, we will update this
particular variable imin. And when we will come out of this second for loop, imin will
have the index of the minimum element. Now, we will have to swap it with element at i-th
index. We will do so by using a temorary variable and this is how our function will look like.
We will quickly run this logic in a simple C++ program, I have written this function
Selection Sort, In the main method I have created the array of 6 elements. This is the
same array that we had picked up as example and then I am calling the selection sort function
oassing the array and the number of elements and once I sort the array, once I have sorted
the array, I am printing the elements. When I run the program , this is the output. So,
this seems to be working. The time complexity of Selection Sort is big-Oh of n square. We
can quickly see how. The running time is the total running time of all the statements.
Let's say this particular statement will take some constant time c1 to execute. Let's say
these statements will take at max c2 to execute. I am assuming their running time together
in the worst case. And let say these statements will take c3 time in the worst case. This
particular statment will be executed exactly n-1 times. This will also be executed n-1
times. This set of statements, this set of three lines. If we try to calculate how many
times these two lines will be executed, it will be n-1 for i = 0, n-2 for i = 1 n-3 for
i = 2 and this will be an arithmetic progression, we will go till 1 for i = n-2. And this will
only be equal to n into n-1 upon 2. So, overall time taken will be something like this. And
if we will evaluate this, it will be some polynomial like an^2 + bn +c where a, b and
c will be some constants in terms of c1, c2 and c3. And whenever we have a time expression
like this, it belongs to the set big oh of the highest order term in the polynomial.
So, this particular polynomial belongs to the set big oh of n square. If you do not
know about big-oh notation and time complexity analysis, we have one complete series on time
complexity analysis. You can find a link to it in the description of this video. Selection
sort is a slow sorting algorithm. Big oh of n square is not the best running time for
a sorting algorithm. So, this was selection sort algorithm and its time comple
xity analysis. We will discuss more sorting algorithms in the coming lessons. Thanks for
watching.