Quicksort is a sorting algorithm that follows the policy of divide and conquer. It works on the concept of choosing a pivot element and then arranging elements around the pivot by performing swaps. It recursively repeats this process until the array is sorted.
In this tutorial we will learn how QuickSort works and how to write python code for its implementation.
Understanding the QuickSort Algorithm
The first step while performing Quicksort on an array is choosing a pivot element. There are various ways of choosing a pivot element.
You can either select a random element or you can select the median of the array. For simplicity, we will be picking the first element of the array as our pivot element.
1. Selecting a Pivot element
As discussed above, the first element is picked as the pivot element.
pivot = array[start]
After selecting a pivot element, we need to rearrange the elements around it. We rearrange the elements in such a way that all the elements smaller than the pivot are on the left and all the elements greater than the pivot are on the right.
How do we do this?
Let’s discuss that next.
2. Rearranging elements around Pivot
To rearrange the elements around the pivot we initialize two variables.
Let’s call these variables low and high.
We initialize low with the second element of the array (one after the pivot) and high with the last element.
low = start + 1
high = end
To rearrange the elements we move the low towards the right and high towards the left. While doing this our motive is to make sure that all the values greater than the pivot should move towards the right and all the values smaller than the pivot should move towards the left.
When we arrange the values in such a manner, we can find out the final position of the pivot element in the sorted array since all the elements smaller than the pivot are on its left and all the elements on the right are greater.
Elements on right and left of the pivot may or may not be arranged in a sorted manner.
3. How to move low and high?
We move high towards left until high points towards a value smaller than pivot or until high is less than low.
while low <= high and array[high] >= pivot:
high = high - 1
Similarly, we move low towards the right until it points to a value that is higher than the pivot or until high is less than low.
while low <= high and array[low] <= pivot:
low = low + 1
After coming out of the loop, we check whether low is less than or equal to high. If that’s the case then we need to swap the values at high and low.
if low <= high:
array[low], array[high] = array[high], array[low]
If low is greater than high we break out of the loop and return high as the position of pivot element. This means that we have successfully arranged the values around the pivot.
4. Implemented Code Until Now
Complete code for the function responsible for selecting a pivot element and then rearranging the elements is given below :
def pivot(array, start, end):
#initializing
pivot = array[start]
low = start + 1
high = end
while True:
#moving high towards left
while low <= high and array[high] >= pivot:
high = high - 1
#moving low towards right
while low <= high and array[low] <= pivot:
low = low + 1
#checking if low and high have crossed
if low <= high:
#swapping values to rearrange
array[low], array[high] = array[high], array[low]
else:
#breaking out of the loop if low > high
break
#swapping pivot with high so that pivot is at its right # #position
array[start], array[high] = array[high], array[start]
#returning pivot position
return high
5. Make recursive calls on two halves of the array
After rearranging the elements around the pivot, we need to make recursive calls on the two halves of the array.
These calls will repeat themselves until we have arrays of size one. The code for function that makes the recursive calls is given below:
def quick_sort(array, start, end):
if start >= end:
return
#call pivot
p = pivot(array, start, end)
#recursive call on left half
quick_sort(array, start, p-1)
#recursive call on right half
quick_sort(array, p+1, end)
The last two statements make the recursive calls on the left and right halves respectively.
The same process of choosing a pivot and rearranging elements around it is repeated for the left and right halves.
When we do this repeatedly we make sure that each element is placed at its correct position.
Here, ‘correct position’ means that all the smaller elements are on the left and all the greater elements are on the right. When all the elements are placed at their correct positions we get a sorted array.
Example of the Quicksort Array
Let’s take an example for testing our code.
[5,1,3,9,8,2,7]
Let’s add some code to print the pivot element, left half and right half of the array for each recursive call.
def quick_sort(array, start, end):
if start >= end:
return
p = pivot(array, start, end)
print("Pivot",array[p])
print("left :", array[start:p])
print("right :",array[p+1:end+1])
print("\n")
quick_sort(array, start, p-1)
quick_sort(array, p+1, end)
Let’s run the code with our sample array above.
array = [5,1,3,9,8,2,7]
quick_sort(array, 0, len(array) - 1)
print(array)
The output comes out as :
Pivot 5
left : [2, 1, 3]
right : [8, 9, 7]
Pivot 2
left : [1]
right : [3]
Pivot 8
left : [7]
right : [9]
[1, 2, 3, 5, 7, 8, 9]
We can see that for each pivot element the left array contains elements smaller than the pivot and the right array contains the elements greater than the pivot.
Visually we can represent the recursive calls as follows :
Complete implementation
The complete implementation for Quicksort is given below :
def pivot(array, start, end):
#initializing
pivot = array[start]
low = start + 1
high = end
while True:
#moving high towards left
while low <= high and array[high] >= pivot:
high = high - 1
#moving low towards right
while low <= high and array[low] <= pivot:
low = low + 1
#checking if low and high have crossed
if low <= high:
#swapping values to rearrange
array[low], array[high] = array[high], array[low]
else:
#breaking out of the loop if low > high
break
#swapping pivot with high so that pivot is at its right # #position
array[start], array[high] = array[high], array[start]
#returning pivot position
return high
def quick_sort(array, start, end):
if start >= end:
return
#call pivot
p = pivot(array, start, end)
#recursive call on left half
quick_sort(array, start, p-1)
#recursive call on right half
quick_sort(array, p+1, end)
array = [5,1,3,9,8,2,7]
quick_sort(array, 0, len(array) - 1)
print(array)
Conclusion
This tutorial was about implementing Quicksort in Python. The worst-case time complexity of Quicksort is O(n2) and average-case time complexity is O(n logn).