0:06

So it's main idea is quite simple, we just keep growing the sorted part of our rate.

Â So let me illustrate it on a toy example, assume we're given a sequence of links.

Â Five consistent of five integers, eight four two five and two.

Â So we start just by finding one of the minimum elements in this array,

Â in this case it is two.

Â Now lets just do the following,

Â lets just swap it with the first element of our array.

Â 0:37

After swapping, two stays in its final position, so

Â two is the minimum value of our array and it is already in its first position.

Â Now let's do the fun one, let's just forget about this element.

Â It is already in its final position and

Â let's repeat the same procedure was the remaining part of our array.

Â Namely, we began first find the minimum value, it is again two.

Â We'll swap it with the first element of the remaining part and

Â then we'll just forget about this element.

Â So again, we find the minimum value which is now four with what was the first

Â element of the remaining part which is now the sole element of our array.

Â And then, we just forget about first three elements and

Â we continue with only remaining parts.

Â So once again, we just keep growing the sorted part of our array.

Â In the end, what we have, is that the whole array is sorted.

Â The pseudocode shown here on the slide, directly

Â implements the idea of the selection sort algorithm that we just discussed.

Â 1:40

So here we have a loop where i ranges from 1 to n.

Â Initially, i is equal to 1.

Â Inside this loop, we compute the index of a minimal value in the array,

Â from, within the list from i to n.

Â We do this as follows, so we create a variable,

Â minlndex which is initially equal to i.

Â And then we go through all the remaining elements inside this part,

Â I mean through elements from i + 1 to n.

Â And if we find a smaller element we update the variable minlndex.

Â So in the end of this for loop, what we have is that minindex is

Â a position of a minimal element inside the array from i to m.

Â 2:30

Namely, when i is equal to one, what we've done, we've found

Â the minimal element in the well array and we've swapped it with the first element.

Â So now, the first element of our array is in its final position.

Â Then under second iteration of our loop, we do the same actually.

Â We find the minimum value, the position of a minimum

Â value inside the remaining part of our array and put it on the second place.

Â On the sort loop we find the minimum value in this remaining part and

Â put it on the place and so on.

Â So we keep growing the sorted part of our array.

Â So when it would be useful to check the online visualization to see how it goes,

Â so let's do this.

Â 3:15

This visualization shows how selection sort algorithm performs on

Â a few different datasets.

Â Namely on the random datasets, on a sequence which is nearly sorted.

Â Also on a sequence which is sorted in reversed order.

Â And on a sequence which contains just a few unique elements.

Â So let's run this algorithm and see what happens.

Â 3:44

So you can see that indeed this algorithm just grows the sorted region,

Â the sorted initial region of our array.

Â So another interesting property is it is revealed by this visualization

Â is the following.

Â So the running time of this algorithm actually does not depend on input data.

Â So it only depends on the size of our initial sequence.

Â 4:11

The other [INAUDIBLE] time of how algorithm is quadratic and

Â this is not difficult to see right?

Â So what we have is two nested loops.

Â In the outer loop, i ranges from 1 to n.

Â In the inner loop, j ranges from i plus 1 to n,

Â to find a minimum inside the remaining part of our array.

Â So in total we have quadratic number of iterations.

Â At this point however, we should ask ourselves whether our estimate was right

Â in time of the selection, so our algorithm was too pessimistic.

Â And this is whar I mean by this.

Â So recall that we have two nested loops.

Â In the outer loop, i ranges from 1 to n.

Â In the inner loop, g ranges from i + 1 to n.

Â So when i is equal to 1, the number of iterations of the inner loop is n- 1.

Â However, when i is equal to 2, the number of iterations of the inner loop is n- 2,

Â and so on.

Â So when i increases, the number of iterations of the inner loop decreases.

Â So a more accurate estimate for the total number of iterations of the inner loop

Â would be the following, (n- 1) + (n- 2) + (n- 3) and so on.

Â 5:33

The sum is that we need to estimate is called an Arithmetic Series, and

Â there is a known formula for this for this sum.

Â Namely 1 + 2 + 3 +, and so on, n,

Â is equal to n(n+1)/2.

Â And this is how we can prove this formula.

Â 5:52

Let's just try it, all our n integers in a row, 1, 2, and so on, n.

Â Below them let's write the same set of integers, but in the reverse order.

Â So, n, then n minus 1, and so on, 2, and 1.

Â Then what we get is a row of size 2 by n.

Â Having n columns, and in each column,

Â the sum of the corresponding two integers is equal to n plus 1.

Â Great, so in the first column we have n and one, and in the second column we have

Â two and minus one and so on and in the last column we have n and one.

Â So the sum in each column is equal to n plus one and zero n columns.

Â Which means that the sum of all the numbers in our table is equal to n,

Â when supplied by n plus one.

Â So since this table contains our sum, the sum of the integers from 1 to n twice,

Â we conclude that the sum of all the numbers from 1 to n is equal to n(n+1)/2.

Â Another possibility to find this formula, to see why this formula is correct

Â is to take a rectangle of size n, of dimensions n multiplied by n plus 1.

Â So it's area is equal to n multiplied by n plus one.

Â And to cut it into two parts such as it's shown in the slide,

Â such as the area of each of these two parts is equal to 1 + 2 + and so on n.

Â We're all ready to conclude.

Â So we've just discussed the selection sort algorithm.

Â This algorithm is easy to implement, easy to analyze, and

Â it's running time is n squared, where n is the size of the input sequence.

Â So it sorts the input sequence and array in place.

Â Meaning that it requires almost no extra memory.

Â I mean, all extra memory which is required by this algorithm is only for

Â storing indices, like i, j and m index.

Â There are many other quadratic algorithms, like insertion sort and bubble sort.

Â We're not going to cover them here, and instead,

Â in the next video we will proceed, to do a faster, a faster sort algorithm.

Â