0:00

In this video, we'll provide the full outline of the Greek word algorithm.

Â So as you remember that algorithm is recursive, for

Â this reason we pass through this procedure [INAUDIBLE] a and

Â also doing this is l and r in this array for left and right and

Â this procedure saw the sub array inside r within this is form l to r.

Â Well we first check whether l is at least r.

Â And if yes then this means that they can respond in sub array contains at

Â most one element.

Â And this in turn means that nothing needs to be done so we just return.

Â 0:38

Otherwise we call the partition procedure with the same parameters.

Â It returns an index m between l and r.

Â So it rearranges all the elements inside

Â this sub array with the following property.

Â After the call to this procedure, A of m stays in its final position,

Â meaning that all the elements to the left of an element A of m are at most A of m.

Â And all the elements to the right are greater than A of m.

Â Well once again, after the call to the partition procedure,

Â A of m stays in its final position.

Â So what remains to be done is to sort all the elements that are at most A to m.

Â They stay to the left of A of m, and all the elements that stay to the right.

Â So we do this just by making two recursive calls.

Â So this is how the wall algorithm looks pictorially.

Â Again, we are given an array A, with two indices l and r,

Â and we are going to sort the sub array inside from indices L to R.

Â So with first call the participation procedure which parameter A, l and r.

Â And it gives us an index m between l and r was the following property.

Â All elements to the left of them are at most the element A of m.

Â All the elements to the right are great as an A of m.

Â Then we make two recursive calls to sort the left part within this is from

Â l to m- 1 and to solve the right part within this is from m + 1 to r.

Â And immediately after these two recursive call, we have a sorted array.

Â So before showing the actual of the partition procedure,

Â we explain it's main ideas again, on a toy example.

Â So first of all, we will take is the element A[l] and denoted by x.

Â This will be called our pivot element.

Â So what pivot is exactly is the element with respect to which

Â we're going to partition our sub array.

Â So x will be placed in its final position.

Â So our goal now is to rearrange all the elements inside our current sub array so

Â that x stays in its final position and all the elements to the left of x.

Â At most x and all the elements to the right of x are greater than x.

Â So we will do this gradually increasing the region of already discovered elements.

Â So for this we will use a counter i, and we will maintain the following invariant.

Â So I will go from l + 1 to r, and

Â at each point of time when we have already have the i element

Â we will keep to region in sizes these region from l + 1 to i.

Â In the first region from l + y to j, we will keep all elements that are at most x.

Â In the second adjacent region within this is from j +

Â 1 to i we will have all elements that are greater than x.

Â Let's see it for example.

Â 3:48

So I assume that we are somewhere in the middle of this process.

Â In this case, x is equal to 6, and

Â we need to partition all the elements with respect to x.

Â We already have two sub regions so in the red region,

Â we keep all elements that are at most x.

Â There are at most 6 in the blue region we have holds elements that

Â are greater than 6.

Â 4:33

Well the next case is more interesting, we move i to the next position, and

Â we discover the element 4.

Â In this case, we need to somehow move this element to the red region,

Â to the region of elements which at most 6.

Â So to do this we just swoop it to currently

Â first element of the blue region, in this case was 9.

Â So if we do this 4 will be the last element of currently red region and

Â 9 will go to the blue region.

Â So we do this and now, we increase also the just

Â to reflect the fact that our red region had just been extended.

Â Then we will find to the next element so we discover element 7 which is

Â greater than 6 which means that we can just extend the blue region,

Â then we discover another element which is 6.

Â 6 is at most 6 and it is actually equal to 6, so

Â we need to move it to the red region.

Â Again, we swap it with the first element of the blue region and

Â then we extend the red region.

Â We increase g to reflect the fact that the red region has just been extended,

Â then we discover another element, which is at most 6.

Â We move it to the end of the red region.

Â 5:55

And finally, what we also need to do in the very end is to move the pivot

Â element which is 6 in this case to its final position.

Â And its final position actually can easily be found in this case.

Â So we have red region and we have blue region.

Â In red region, all the elements are at most 6, and in blue region,

Â all the elements are greater than 6.

Â So we can just swap 6 with the last element of the red region.

Â In this case it is 1, so if we swap these two elements then you

Â can see that all the elements in the blue region are indeed greater than 6.

Â All the elements in the red region are smaller than 6.

Â So we are done with this partition procedure.

Â Where now ready to present the Soutacot of the petition procedure.

Â We called it what we're going to do is to place some element x,

Â which is called the pivot, into it's final place so that all the elements before

Â x are at most x and all the elements after x is greater than x.

Â So as the pivot element in this procedure, we are going to use just the first

Â element of the correspondence of rate, so x is assigned A of l.

Â 7:14

We're also going to remain the following subregions.

Â So first of all, we will readily increase the region of discovered elements.

Â So i goes from l +1 to r and inside this region of

Â [INAUDIBLE] elements, we will maintain two sub regions.

Â In the first region with indices from l +1 to j,

Â we will keep all of the elements at most x.

Â In the second region with indices from j+1 to i, we will keep all of the elements

Â that are greater than x and we will gradually and freeze the value of i.

Â So when i is increased, so I assumed that i has just been increase so

Â we discovered a new element of A of i.

Â So if A of i is greater than x then just the second

Â of region of elements that are greater than x,

Â is extended automatically and we do not need to do anything in this case.

Â However, if the newly discovered element is at most x,

Â then we need to move it to the first region.

Â So we do this as follows.

Â So we just increase the value of j to indicate the fact that

Â the first region has just been increased, and then swap the elements.

Â A[j] and A[i], so this way,

Â we just maintain our invariant each time when i is increased.

Â So in the very end, when i reaches the value of r,

Â we also need to place our initial element that states that at

Â the beginning our pivot between our two regions.

Â So for this we just swap elements A[l], so this is our pivot with element A[j].

Â And we then return the value j as an index of our pivot element.

Â