Well, as usual, we start with the overview of this algorithm.
The algorithm is comparison based,
meaning that it sorts the n given elements by comparing pairs of them.
Its running time is also asymptotically n log n, but not in the worst case,
as was with the merge sort algorithm, for example, but on the average case.
This is because this algorithm is randomized,
so it uses random numbers to sort the given n objects.
Well, we will explain later in this lesson what this means.
Finally, as I said before, this algorithm is very efficient in practice and,
at the same time, not so difficult to implement.
This is a toy example explaining the main idea of the quick sort algorithm.
So given an array, in this case of size 11, let's take its first element.
In this case it is 6.
And let's do the following.
Let's rearrange all the elements in this array such
that the element 6 stays in its final position.
All the elements that go before it are actually at most 6.
And all the elements that go after 6, after this element, are greater than 6.
Well, we will show that this can be done by a single scan of the initial array.
This is how the resulting array looks like.
So once again, 6 stays in its final position.
All the elements before it are at most 6.
All the elements after it are greater than 6.
So we do not need to move 6 anymore.
It is already in its final position.
So what remains to be done is to sort all the elements that go before 6 and
all the elements that go after 6.
And this can be done just with two recursive calls to the same algorithm,
to the quick sort algorithm.
So we do this,
and immediately after these two recursive calls, we have a sorted array.
Well, in the next video we will explain all the details of this algorithm.
