Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
What is QuickSort in Python?
1.
Quick Sort Algorithm
2.
Coding QuickSort in Python
2.1.
QuickSort in Python 3
2.2.
QuickSort in Python 2
3.
Time and Space complexity of Quicksort
4.
Time Complexities
5.
Space Complexity
Comparison of Quicksort to Other Sorting Algorithms
1.
Quicksort Optimization Techniques
2.
Advantages and Disadvantages of Quicksort in python 
3.
Advantages
4.
Disadvantages 
5.
Frequently Asked Questions
5.1.
Can we make quicksort stable?
6.
What is the memory complexity of quicksort?
7.
What is the best case running time of quicksort?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

How to Implement Quick Sort in Python?

Author Satvik Gupta
1 upvote

Introduction

QuickSort is a sorting algorithm that is widely used in the industry. It is fast, efficient, and powerful. It uses the divide-and-conquer technique to divide the array into sub-arrays, sort them, and then recursively sort the larger arrays.

quicksort python

In this article, we will read quicksort python in detail. We will code it in both Python2 and Python3. Let's get started!

Must Recommended Topic, Floor Division in Python, Swapcase in Python

Also See, Divmod in Python

What is QuickSort in Python?

Quicksort is a widely used sorting algorithm that follows the divide and conquer principle. This sorting algorithm works with large data sets but varies from scenario to scenario. The algorithm takes an array as input, and in the quick sort algorithm, you select a pivot element which is nothing but a random number in an array. This number plays a vital role in the performance of the algorithm. Once you select the pivot elements, the elements smaller than pivot are moved toward the left, and numbers greater than the pivot are moved to the right. This process continues by dividing the array into subarrays. In the last, the array is sorted. 

Also see, Python Operator Precedence

Quick Sort Algorithm

Let's take a look at the quick sort algorithm. 

  1. Choose a pivot element - it can be any element. It is preferable that the element is chosen so that roughly half of the elements are smaller than it, and roughly half are bigger than it. 
     
  2. Rearrange the elements of the array such that all the elements smaller than the pivot are on its left, and all the elements larger than the pivot are on its right. The pivot is now in its correct position in the sorted array. This is called the partition step.
     
  3. Recursively call quick sort on the elements on the left side of the pivot, and do the same for the elements on the right side of the pivot element.

     
Quick sort diagram

You can also read about Multilevel Inheritance in Python, Fibonacci Series in Python

Coding QuickSort in Python

We will code quicksort in Python 3 as well as in Python 2. Coding quicksort in Python, or any other language involves applying the concepts we studied above in the language. 

QuickSort in Python 3

# The partition function, which returns the position of the pivot element.
def partition(nums:list[int],start:int,end:int)->int:
    #the pivot element. We are taking the end element as pivot.
    pivot:int = nums[end];
    
    # i, which will help us find the final position of the pivot element.
    i:int = start-1;
    for j in range(start,end):
        #if the current element is smaller than the pivot
        if (nums[j]<pivot):
# increment i
            i=i+1;
#swap elements at i and j
            nums[j],nums[i]=nums[i],nums[j];

    # finally move the pivot element to its correct position
    i=i+1;
    nums[end],nums[i]=nums[i],nums[end];

    #return the final position of the pivot element
    return i;

#the recursive function that performs quicksort in python 3
#start is the start index of the subarray to sort
#end is the end index of the subarray to sort
def quicksort(nums:list[int],start:int,end:int):
    # if start is not less than end, it means the subarray has 0 or 1 elements, and doesn't need                                                                                     
    # to be sorted.
    if (start<end): 
        # find the position of the pivot element    
        pivot:int = partition(nums,start,end);

        #recursively sort left and right subarrays for pivot    
        quicksort(nums,start,pivot-1);
        quicksort(nums,pivot+1,end);

#utility function to call quick sort
def sortArray(nums:list[int])->list[int]:
    quicksort(nums,0,len(nums)-1)

arr = [5,3,2,6,1,4]
sortArray(arr)
print(arr)
You can also try this code with Online Python Compiler
Run Code

QuickSort in Python 2

# The partition function, which returns the position of the pivot element.
def partition(nums,start,end):
    #the pivot element. We are taking the end element as pivot.
    pivot = nums[end];
    
    # i, which will help us find the final position of the pivot element.
    i = start-1;
    for j in range(start,end):
        #if the current element is smaller than the pivot
        if (nums[j]<pivot):
# increment i
            i=i+1;
#swap elements at i and j
            nums[j],nums[i]=nums[i],nums[j];

    # finally move the pivot element to its correct position
    i=i+1;
    nums[end],nums[i]=nums[i],nums[end];

    #return the final position of the pivot element
    return i;

#the recursive function that performs quicksort in python 2
#start is the start index of the subarray to sort
#end is the end index of the subarray to sort
def quicksort(nums,start,end):
    # if start is not less than end, it means the subarray has 0 or 1 elements, and doesn't need                                                                                     
    # to be sorted.
    if (start<end): 
        # find the position of the pivot element    
        pivot = partition(nums,start,end);

        #recursively sort left and right subarrays for pivot    
        quicksort(nums,start,pivot-1);
        quicksort(nums,pivot+1,end);

#utility function to call quick sort
def sortArray(nums):
    quicksort(nums,0,len(nums)-1)

arr = [5,3,2,6,1,4]
sortArray(arr)
print(arr)
You can also try this code with Online Python Compiler
Run Code

Output:

Sorted output

You can practice by yourself with the help of online python compiler.

Time and Space complexity of Quicksort

Time Complexities

Let's discuss the worst, best, and average time complexities of the quicksort algorithm in Python.

Worst Case Complexity is O(n2)

Base Case Complexity is O(nlogn)

Average Case Complexity O(nlogn) 

Space Complexity

The space complexity for quicksort is O(1) because it is an in-place algorithm. Recursion stack space is not counted here. If we count the stack space, the time complexity will be O(logn) in the average case and O(n) in the worst case.

Also see,  Convert String to List Python

Comparison of Quicksort to Other Sorting Algorithms

Quick sort is a sorting algorithm with its own pros and cons. Let's try to better understand this algorithm by comparing it with several other sorting algorithms. When we compare quick sort with insertion sort: 

  • The average time complexity of quicksort is O(nlogn). 
     
  • The average time complexity of insertion sort is O(n2). 
     
  • Quick sort works well with large data sets and unsorted data. 
     
  • Insertion sort works well with small data sets or partially sorted data.

 When we compare quicksort with Merge sort: 

  • Quicksort works on the principle of divide and conquer but does not require additional space. 
     
  • Merge sort also works on the same principle but requires additional space. 

 When we compare quicksort with Bubble sort: 

  • Quicksort is best suited to large data sets and is faster than bubble sort. 
     
  • Bubble sort is an easy-to-understand sorting algorithm but is impractical for large data sets. 

Quicksort Optimization Techniques

There are several techniques to optimize the quicksort algorithm. These techniques help to optimize the performance of the algorithm. The following optimization ways can be used to implement the quicksort technique. 

  1. A tail recursive optimization technique can be chosen for the recursive calls as it helps control the stack overflow error. A tail recursive technique can be used to implement a quick sort algorithm. 
     
  2. Choosing correctly the pivot element. It is important to select the pivot element correctly as it impacts the performance. 
     
  3. A hybrid choice of sorting algorithm can also be implemented. When implemented in small data sets, insertion sort or any other algorithm can be used. 

Advantages and Disadvantages of Quicksort in python 

Advantages

  1. Quiksort algorithm is best suited for large data sets as it works on the principle of divide and conquer. This helps divide the array into smaller subarrays and achieves better performance.
     
  2. The Quicksort algorithm does not use any additional memory consumption to sort the array. 
     
  3. The average time complexity of the quick sort algorithm is O(nlogn), which is better than that of other sorting techniques.

Disadvantages 

  1. The worst-case time complexity of quick sort is O(n2), which happens when pivot selection does not divide the array into the correct partition. 
     
  2. The algorithm is not stable which means it can change the order of the elements. 
     
  3. The algorithm does not work well with partially sorted datasets.

Frequently Asked Questions

Can we make quicksort stable?

One way to do so is by using extra space. We can partition by making lists for elements smaller than, equal to, and greater than the pivot. Then we can concatenate them. However, we should just use merge sort if we are fine with using extra space.

What is the memory complexity of quicksort?

Quick sort does not require any additional memory space to implement the algorithm. The memory complexity of quicksort is O(1). It uses a constant memory space regardless of the size of an array. 

What is the best case running time of quicksort?

The best-case running time of quicksort happens when the correct selection of pivot happens. the best time complexity of quicksort algorithm is O(nlogn), which is their average time complexity. 

Conclusion

In this blog, we have gone through the algorithm for quicksort Python. We have also seen a code for quicksort in Python 3 and in Python2. At the end, we discussed the time complexities.

We hope you leave this article with a broader knowledge of Data Structures, algorithms, and sorting.Recommended Readings:

Recommended Problem -

If you liked our article, do upvote our article and help other ninjas grow.  You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Keep coding, keep reading Ninjas. 

Live masterclass