Now that you have through an example how QuickSort works, let us take a look the pseudocode for QuickSort and later on see a working Java implementation of QuickSort.

$$/$$

How that we have successfuly written the pesudocode for the Partition function of Quick Sort, we will now complete our Quick Sort operation by using the above defined Partition function and using it to sort a given array.

Video Transcript

Now let us take a look at a pseudocode for the partition function. Now recall what the partition function was doing. So basically, partition function would if given a pivot, it would partition the entire array into two subarrays such that all the elements lesser than the pivot will be on one side and all the elements greater than the pivot would be on the other side. Moreover, the partition function also places the pivot element at its correct position in the final sorted array. So, these are the three functions of the partition function. Dividing the array into two halves such that one half consists of all elements lesser than the pivot, the other half will have all the elements greater than the pivot and also the pivot itself will reach its correct position. So let us now see how this works. For that, the partition function is going to take an input array A and start and ending index of that particular array. Suppose I am given that array which we took in our example. So here my A would be my input array and my start index would be here and my ending index would be here.

Now, what I'm going to do is that I'm going to define my pivot as the last element that is A of end. So here my pivot is going to be this four. Next, I'm defining another variable p, which I will call as my partition index. So basically I'm going to initialize my p from start itself. So here my p is going to point to index zero. So now what I'm going to do is that I'll define a new iterator I and I'm going to take it from start till end minus one. And what I'm going to do is that if I encounter any element which is lesser than the pivot, I'm going to swap it with the partition index, that is the element placed at the partition index. So there's no need to be confused. Let us look at the example here and see how this works. So, I'm going to start my iterator from the starting position. Start here now points to index zero. So what I'm going to do, that if A of I is less than equal to pivot, that is, if any element here is less than equal to pivot, I'm going to swap it. So, let us take an example of seven here. Right now my start index is here and I also points to here. So here is my I. Now, is A of I less than pivot. No, A of I is not less than pivot because seven is not less than four. So this if condition is not going to get executed. But as soon as I move on and increase my I, I would find that I now points to index one. Now I would see on comparing A of I with pivot, a of I is two and my pivot is four. So is A of I less than equal to pivot. Yes, since two is less than equal to four, this if condition is now going to get executed. And what will I do here? I'm going to swap A of I with A of P. So my P is now here, pointing towards index zero, and I is pointing towards index one. So basically in this step, I'm going to exchange both these two elements. So this is going to come here and seven is going to go there. So two will be here and seven will be here. And in the next step, I'm going to increment my P counter. That is, P will now point here.

Now in the next step, my I is going to get incremented. Since this is a for loop, at each execution, my I is always going to increase. So now my I is going to point here again. On repeating the same procedure, I would find that A of I that is A of index two here is one. On comparing it with the pivot, which is four, I find that since one is less than four again, this if condition holds true. So I'm going to execute the thing inside this curly braces. That is I'm going to swap a of I with a of P. That is a of I. Right now, I is on index two and P is on index one. So I'm going to swap a of P and a of I. That is, my seven is going to replace by one. And in place of one, I'm going to have a seven here. And what I'm going to do, I'm going to move my P counter. So now my P is going to point here on index number two. And since this is a for loop, my I will come here on index number three. So in this position, you notice I has now reached three and P has now reached two. So have we observed anything?

If we observe carefully, all the elements towards the left of this partition index are lesser than the pivot. That is, the elements to the left of P are two and one, which are lesser than four. So basically, partition index ensures that all the elements towards the left of the partition index are always less than the pivot. What is the functional role of the partition index that we are going to come about after a little while? So let us move to the next step. In the next step again, I'm going to compare A of I with my pivot. So my A of I is six and my pivot is four. Since my A of I is not less than four, that is, six is non less than four. This if condition is not valid and this curly braces thing does not get executed. And what do I do? My p remains here. But since this is a part of for loop, that is my iterator I is inside this for loop. So it is anyway going to go one step ahead. So now my I will point here. I'm going to repeat the same process again. Compare A of I, which is five, with the pivot, which is four, since A of I is not less than the pivot. Again, this if condition does not hold and this thing within the brackets does not get executed. So my P remains here as it is, but my I moves one step forward, so I is going to come here. Now a of I is three and Pivot is four. So on comparing both of these two, I find that since A of I is less than the pivot, so this if condition is true this time. So in the next step, I'm going to swap A of I with A of P. Now, notice that P is still here on index number two, while I has moved to index number five. So basically in this step I'm going to swap A of two and A of five. That is, I'm going to swap seven with three. In place of three, I'm going to place a seven, and in place of a seven, I'm going to place three. And moreover, P is equal to P plus one. That is, my P will move one step ahead and come here. And since I is a part of the for loop, so it is always going to increment after one iteration. And I will now come here. Now again, my I will check whether A of I is less than the pivot. A of I is now eight, which is not less than the pivot. So nothing is going to happen. This condition within the curly braces is not going to get executed. Now notice here that I in the next step will reach end, but my for loop is going to get executed till only I less than N minus one. So I would come to know that this particular iteration is now over. Now notice that my P index here points towards index three. Now, if you notice carefully all the elements towards the left of index number three. That is, all the elements towards the left of the partition index are smaller than the pivot, that is four. Because here I have elements two, one, and three on indices zero, one and two. And all these three elements are lesser than the pivot.

Video Recap

The partition function ensures that all elements lesser than the pivot are on one side, and all elements greater than the pivot are on the other side while placing the pivot element at its correct position in the final sorted array
The function takes an input array A and start and ending indices of that array
The pivot is defined as the last element of the array, and a partition index is initialized from the start
An iterator i is taken from start till end minus one, and if any element is lesser than or equal to the pivot, it is swapped with the partition index element
The partition index ensures that all elements towards its left are lesser than the pivot, and the function keeps iterating until all elements are sorted accordingly
The partition index has a functional role that will be explained later

$$/$$

Now its time to convert the above pseudocode into a Java code and try to execute and see if it works. Aishwarya will now demonstrate a Java code for Quicksort. Download the file below for your reference.

$$/$$

Now that you've learn how Quick Sort works through a simple code, its time to analyze the time complexity of Quick Sort. Let us learn about it in the next section.