Trusted answers to developer questions

How to implement QuickSort in Python

Get Started With Machine Learning

Learn the fundamentals of Machine Learning with this free course. Future-proof your career by adding ML skills to your toolkit — or prepare to land a job in AI or Data Science.

QuickSort is an in-place sorting algorithm with worst-case time complexity of $n^{2}$ .

Implementation

QuickSort can be implemented both iteratively and recursively. We’ll mainly focus on the recursive implementation, as it is far more convenient, intuitive, and simplistic – iterative implementation is generally unrecommended. Arrays are used as an example here, but QuickSort can be implemented on other data structures (like linked lists) as well.

The algorithm can be broken down into three parts:

Partitioning the array about the pivot.
Passing the smaller arrays to the recursive calls.
Joining the sorted arrays that are returned from the recursive call and the pivot.

def QuickSort(arr):
    elements = len(arr)
    
    #Base case
    if elements < 2:
        return arr
    
    current_position = 0 #Position of the partitioning element
    for i in range(1, elements): #Partitioning loop
         if arr[i] <= arr[0]:
              current_position += 1
              temp = arr[i]
              arr[i] = arr[current_position]
              arr[current_position] = temp
    temp = arr[0]
    arr[0] = arr[current_position] 
    arr[current_position] = temp #Brings pivot to it's appropriate position
    
    left = QuickSort(arr[0:current_position]) #Sorts the elements to the left of pivot
    right = QuickSort(arr[current_position+1:elements]) #sorts the elements to the right of pivot
    arr = left + [arr[current_position]] + right #Merging everything together
    
    return arr
array_to_be_sorted = [4,2,7,3,1,6]
print("Original Array: ",array_to_be_sorted)
print("Sorted Array: ",QuickSort(array_to_be_sorted))

RELATED TAGS

quicksort

python

sorting

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to implement QuickSort in Python

Implementation

Code