A Python Tutorial on Partition and QuickSort Algorithm

The sorting algorithms are the fundamentals of data structure, one needs to have an in-depth knowledge of common searching and sorting algorithms like, merge sort, bubble sort, quicksort, selection sort, and more. In-depth knowledge includes the algorithms’ time and space complexity as well. 

 

From competitive exams to software developer interviews, data structure is an integral part of computer science, the knowledge of basic searching and sorting techniques ( such as bubble sort and merge sort) acts as a building block for data structure and algorithms. In this blog, we are going to deal with a quicksort algorithm.

 

 

Quicksort Algorithm

 

Quicksort is one of the most common sorting techniques that uses partition algorithm and divides and conquer method, in order to apply the divide and conquer technique, some of the points are to be remembered;

 

1. It divides the original problem into sub-problems, but all sub-problems have to be the same, for example-: if the problem is to sort, then the sub-problem should also be of sorting.

2. Before applying DAC to a problem, analyze if we can combine all the solutions of all the sub-problems at the end or not.

3. The approach of divide and conquer leads to better time complexity, but there may be approaches that can provide similar time complexity with better space complexity, so choose wisely.

 

Quicksort In Python

 

Quick-sort algorithms place each and every element at its sorted position one by one, what is a sorted place for any number? Let us say we name the element we want to sort like a ‘pivot’, then all the numbers less than the pivot should be at its left, and all the numbers greater than the pivot should be at its right. This approach is partition algorithm.

 

Partition Algorithm

 

Let’s try to understand how we can implement partition algorithm in quicksort with an example-:

As we said that the quicksort algorithm sorts each and every element one by one, which means we can start from either last or from the first to crawl, so let’s start with sorting the first element, i.e ‘9’, let us name this element as pivot. Infinity is added to the last in order to cover every element in the process or to save a few lines of code.

 

Pivot = 9

 

We have taken two variables i and j, ‘i’ will search for elements greater than the pivot element whereas ‘j’ will search for the elements smaller than the pivot element. The intuition is to increment ‘i’ until we find an element greater than the pivot, and to decrement ‘j’ until we find an element smaller or equal to the pivot.

 

Therefore right after we will start, we will check if j>i, because there has to be more than 1 element to perform sorting. Initially, we will increment ‘i’ to the adjacent element, i.e 15, we will compare pivot with 15 and as 15 is greater than the pivot, we will stop there, on the other hand, we will be decrementing ‘j’, and the next element is 8 which is less than the pivot element, therefore we will stop decrementing. Wherever we stop both i and j, we shall swap them.

 

(Also read: Scrapy Tutorial for Web Scraping With Python)

 

We have swapped the ith and the jth element and incremented ‘i’ to the next value and decremented ‘j’ to the next value. Now the pivot is greater than 7, therefore it will continue to move forward, but the next element is 1, pivot is less than 11, therefore ‘i’ will stop here. The other variable ‘j’ will stop at 2 as it is smaller than the pivot and we will swap ‘i’ and ‘j’.

 

 

Similarly the following steps will include-:

 

 

Now i will increment to 14, which is greater than pivot, therefore we will stop at 15, j will be decremented and will move to 5, here, i>j, therefore we will simply swap the pivot element with the ‘jth’ element, this way the pivot element gets to its sorted place.

 

 

In this way, we have to recursively apply partitions in order to perform quicksort for each and every element, that’s how all the elements will be sorted. So we need to make a function or a method that could implement the partition algorithm and then we have to apply recursion to apply quicksort. 

 

Key points for partition algorithm-:

1. If i<j, increment i and stop when the pivot element is less than ith element.

2. For i<j, decrement j and stop when the pivot element is greater than the jth element.

3. After every stop of i and j, while i<j, swap the elements of i and j.

4. When i>j, swap jth element with the pivot.

 

 

Partition Algorithm Using Python

 

In this function, we are going to apply all that we have learned so far about the working of partition algorithm-:

 

def partition(A,l,h):

    pivot = A[l]

    i=l

    j=h-1

    

    while i<j:

        while A[i]<pivot:

            i+=1

        while A[j]>pivot:

            j-=1

        if A[i]>pivot and A[j]<pivot:

            A[i],A[j]=A[j],A[i]

            

    A[l],A[j]=A[j],A[l]

    

    return j

 

Code is nothing but everything that we have discussed above in the partition algorithm. We have taken a function that accepts an array(A), starting index(l), and the highest index(h), so there are three parameters to the function.

 

(Recommended: Data Types in Python)

 

We have taken a pivot element, and i and j variable to increment and decrement in an array. While i<j, we are doing all the swapping, incrementing, decrementing as stated above in the partition algorithm. We can see that at last we are returning j as discussed above.

 

Quicksort python code

 

Now in order to apply quicksort, we need a function that accepts an array, starting index and the ending index. After that we will check if l<h, then we will simply store the result of partition on the variable ‘j’, then we have to apply quicksort from ‘l’ to ‘j’, and ‘j+1’ to h. This will recursively sort each and every element in the list, and the sorted list will appear.

 

 

def qsort(A,l,h):

    

    if l<h:

        j = partition(A,l,h)

        qsort(A,l,j)

        qsort(A,j+1,h)

 

As what we apply to the quicksort is nothing but a method called divide and conquer, i.e, we break the problem into several sub-problem, in this case we want to sort the whole list, we are minimizing the problem into sorting each and every element in the list. The most important step in the divide and conquer method is that we should be able to combine the result as we are doing in the case of quicksort, we are able to merge all the solutions.

 

(Also read: First step towards python)

 

As we break the problem into half, let's consider we have a problem ‘n’, then we are breaking it into the sequence-:

 

n,n/2,n/4,n/8,.......1, therefore the time complexity of quicksort is o(nlogn), whereas the space remains unchanged in the case of quicksort, therefore the space complexity is o(n).

 

 

Conclusion

 

With the brief knowledge about partition algorithm and quicksort algorithm, we can conclude that partition algorithm is the soul of quicksort algorithm, the python code for quicksort includes recursion and the strategy is divide and conquer. 

 

(Suggest blog: Feature Scaling In Machine Learning Using Python)

 

At the end we calculated the time complexity and the space complexity for the quicksort algo.