Quicksort is a divide and conquer algorithm where an array is divided into subarrays by selecting a pivot element (element selected from the array).
Python quicksort: Divide and Conquer
Python quicksort uses the divide and conquer algorithm that breaks down a complex problem into multiple sub-problems. Then, those sub-problems recursively into smaller sub-sub problems until those sub-sub problems become very easy to solve. And at the end, those sub-sub solutions are combined to solve the original complex problem.
Now, let us see how quicksort implements the divide and conquer algorithm.
NOTE: The running time of quicksort depends majorly on how we pick the pivot element.
The worst-case time complexity is O(n2), and the best and average-case complexity is O(n*log(n)).
The general principle of quicksort is to choose a pivot element. This pivot element can be any element of the list to sort, but we will be using the last element in this article.
Divide and Conquer algorithm
- Start
- Choose the pivot element.
- Store elements less than the pivot element in the left subarray.
- Store elements greater than the pivot element in the right subarray.
- Call quicksort recursively on the left subarray until the size of the list is ‘1’.
- Call quicksort recursively on the right subarray until the size of the list is ‘1’.
- Print the sorted array.
- End
Now let us understand the above algorithm with an example.
Let’s say we have an array
| 20 | 10 | 80 | 60 | 50 | 70 | 30 | 40 |
Our initial step is to choose a pivot element.
We will use the last element, i.e., “40,” as a pivot element.
In the first iteration, we want to have elements that are less than ’40’, which should be stored left of this pivot element, and all the other elements that are greater than the pivot element should be stored right of the “40”.
Quicksort uses two indexes, let’s say, “i” and “j,” that iterates through this list.
Now, “i” goes from left to right in the array and “j” goes from right to left in the list.
The “i” looks for an element bigger than the pivot element, and the “j” looks for an element less than the pivot element.
So let’s start with “i”; the “i” looks for an element bigger than 40.
So, “20” is not bigger than “40”.
The “10″ is not bigger than the “40”.
But “80” is bigger than “40”.
Now it is “j” turn to look for an element less than “40”. The “j” in this case does nothing because “30” is already less than “40”.
And now, we will swap the element at index “i” with the element at index “j”.
And now this procedure starts again. Again, the “i” looks for an element bigger than “40”.
So, “i” looks at the “60” next and sees that it is bigger than “40” and stops there.
Now it is the “j” turn, which sees that “80” is bigger than “40,” so it moves left.
The “70″ is bigger than “40,” so “j” moves left.
At the “60”, The “j” moves left and now is found in the element “30”.
Now we have the case that “j” is left of “i,” and when “j” is left of “i”, we are basically done with the sorting for the first step of quicksort, and now we have to swap elements at index “i” with the element at index “p”.
So, we will swap those two numbers,
And now what we can see is that the element “40” is in the right place, and every element left of “40” is less than “40,” and every element right of “40” is greater than “40”.
Now we can recursively call quicksort on both of these sub-arrays.
So, let’s start with the left subarray; when we call quicksort on this,
We will again choose a pivot element as “30,” so the rightmost element of the sub-array at index “i” starts again at the leftmost element index “j” begins at the position left of index “p”.
Now we will follow the same procedure with “i”. Again, we will look for an element that is bigger than the pivot element, so “20” is lesser than “30” and “10” is lesser than “30”.
When “i” reaches the right side of the area, it stops there.
And now, it is “j” ‘s turn. The “j” looks for an element less than “30”. So, it will just stop at the “10,” and we’re done with this step of quicksort now.
NOTE: Remember the condition, when “j” is left of “i,” our quicksort for this sub-array stops, and we switch the element at index “i” with the element at index “p”.
In this case, we would swap the “30” with “30”, so nothing would happen.
We can see that “30” is already in the right place; now, we have an even smaller sub-area to sort.
Left of the “30” is “20” and “10”; this smaller sub-array will also be sorted using quicksort.
We will again choose the rightmost element ‘p’ (our pivot element), and ‘i’ always points at
The first element in this area and ‘j’ points at the left element of the pivot element.
So, according to the condition, we won’t do anything in this case. We will not move our indexes; we will swap the element at index ‘i’ with the element at index “p”.
We will swap those two and see that “10,” our pivot element is in its right place.
Now, quicksort is called on the element “20,” and if quicksort is called on only one element, then it will be automatically sorted. As we can see, those recursive calls of quicksort sorted the left subarray, i.e., left of the “40”.
Similarly, we will do the same with the right sub-array too.
First of all, we will choose “60” as our pivot element because it’s the right one. Then, we will set ‘i’ to the leftmost element and “j” to the element left of “p”.
With “i,” we look for an element that is greater than “60”, we found “70” and will stop here.
Now, it is “j” ‘s turn, and “j” looks for an element that is smaller than “60”.
So, it moves to “50”.
And now our condition is true that “j” is lesser than “p,” and our quicksort step for this sub-array ends with the swapping of the element at index ‘i’ with the element at index “p”.
NOTE: We now have two smaller sub-arrays, one that only consists of “50,” which is left to “60,” and the one that consists of “80” and “70,” which is right to “60”. When we call quicksort on the “50”, nothing will happen because it just returns to “50” and says this is already sorted.
When we call quicksort on the right subarray, then again, “70” will be our pivot element, “i” will be the leftmost element, and “j” will be the element left of “p”.
Since our condition is true that “j” is less or equal to “i”, we will have to check if we need to do a swap.
In this case, we will need to swap because “80” is greater than “70”.
So we swap those two elements to see that “70” is in the right place or not.
At last, we call quicksort on the ’80’, which will return “80”. Now we can see the right subarray, i.e., right to the “40,” is sorted. Those were all-recursive quicksort calls, which leaves us with our whole original list in sorted order.
So now, let us move toward the code.
Python quicksort program
def quicksort(arr, left, right):
if(left < right):
partitionPosition = partition(arr, left, right)
quicksort(arr, left, partitionPosition - 1)
quicksort(arr, partitionPosition + 1, right)
def partition(arr, left, right):
i = left
j = right -1
pivot = arr[right]
while(i < j):
while( i < right and arr[i] < pivot):
i +=1
while( j < left and arr[i] >= pivot):
j -=1
if( i < j):
arr[i], arr[j] = arr[j], arr[i]
if( arr[i] > pivot):
arr[i], arr[right] = arr[right], arr[i]
return i
arr = [20, 10, 80, 60,50, 70, 30, 40]
quicksort(arr, 0, len(arr) -1)
print(arr)
Output
[10, 20, 30, 40, 50, 60, 70, 80]The quicksort() will have three parameters, the array, ‘left’ and ‘right’, which are indexes that determine the part of the array that we want to sort.
In the beginning, we want to sort the whole list so that ‘left’ will be 0 and ‘right’ will be the length of the list. If the length of the subarray is just one, then quicksort does nothing. We have used an if statement that checks if ‘left’ is less than ‘right’, which means that the sub-array contains at least two elements.
Now we call another function which is called ‘partition()’.
partition() will also have three parameters, the array, ‘left’ and ‘right’, which are indexes that determine the part of the array that we want to sort.
This partition function returns the index of the pivot element.
After the first step of quicksort, when we have the index saved in partition, we can call quicksort on the original list from index ‘left’ to index ‘partitionPosition -1’, which means that we call quicksort on all elements that are less than the pivot element. We can call quicksort on the array from ‘partitionPosition + 1’ to the ‘right’.
We called quicksort on the sub-array, which contains all elements greater than the pivot element.
We have our known indexes inside the ‘partition()’ function.
For example, the ‘i’ defines the left point of the area to sort, and ‘j’ defines the point right of the pivot, and the pivot element itself is just the array at the right index.
From the above example, we can say that ‘i’ moves to the right and ‘j’ moves to the left until ‘i’ and ‘j’ cross. The condition that ‘i’ and ‘j’ cross will be checked in the while loop by checking if ‘i’ is less than ‘j’. And inside the while loop, we will move ‘i’ to the right and ‘j’ to the left.
So let’s start by moving ‘i’ to the right, and while ‘i’ is not at the end of the array and the element at index ‘i’ is less than the pivot, we can increase ‘i’, and similarly, we can do this to ‘j’ by checking if ‘j’ is greater than ‘left’. However, if the element at index ‘j’ is greater than the pivot, we must decrease ‘j’ because ‘j’ moves to the left while both loops are over.
We will check whether those two elements have crossed yet, and if they didn’t cross, we need to implement a swap.
We will swap the element at index ‘i’ with the element at index ‘j’, and now we just need to consider what happens after ‘i’ and ‘j’ have crossed.
We also have another case in which the index ‘i’ is greater than the pivot, and in this case, we need to do another swap and swap those two elements.
NOTE: Remember that ‘right’ is the index that points to the pivot element, so we swap the area at index ‘i’ with the array at index ‘right’.
And at last, we must not forget to return ‘i’ because the quicksort function we defined earlier needs’ i’ to determine where to split the array to call quicksort recursively.
Summary
- Quicksort uses Divide and Conquer approach.
- Worst-case time complexity: O(n2)
- Best and average-case time complexity: O(n*log(n))
That’s it for the Python quicksort example.
Related posts
How to Sort 2D Array in Python
How to Sort a List of Lists in Python
Krunal Lathiya is a Software Engineer with over eight years of experience. He has developed a strong foundation in computer science principles and a passion for problem-solving. In addition, Krunal has excellent knowledge of Data Science and Machine Learning, and he is an expert in R Language. Krunal has experience with various programming languages and technologies, including PHP, Python, and JavaScript. He is comfortable working in front-end and back-end development.