How to implement Quicksort algorithm in Python

By Abhilash Bandla

This Python tutorial helps you to understand what is Quicksort algorithm and how Python implements this algorithm.

Algorithm for Quicksort

This algorithm is a sorting algorithm which follows the divide and conquer algorithm. First, we will learn what is divide and conquer algorithm.

Divide and Conquer:-

Divide and Conquer is an algorithmic paradigm which is same as Greedy and Dynamic Programming. A standard divide and conquer algorithm follows three steps to solve a problem. Those are:-

1.  Divide:  Break the given problem into subproblems which belong to the same type.
2.  Conquer:  Solve the subproblems recursively.
3.  Combine:  Combine all the subproblems at the end to get the answer.

The Quicksort algorithm picks an element as pivot and partition the given array around the selected pivot element. There are many ways the pivot element can be selected. Those are:-

1. Always pick the first element as a pivot.
2. Always pick the last element as pivot.
3. Pick random element as pivot.
4. Pick the middle element or median as a pivot.

After choosing the pivot element, the algorithm rearranges in such a way that all the elements which are smaller than selected pivot element shifts to the left side of pivot element and all the elements which are greater than the selected pivot element shifts to the right side of pivot element. At last, the algorithm recursively sorts the subarrays on the left and right side of pivot element.

             Implementation of Quicksort in Python

Source Code: Quicksort in Python

def quicksort(arr, begin, end):
    
    if end - begin > 1:
        p = partition(arr, begin, end)
        quicksort(arr, begin, p)
        quicksort(arr, p + 1, end)
 
 
def partition(arr, begin, end):
    pivot = arr[begin]
    i = begin + 1
    j = end - 1
 
    while True:
        while (i <= j and arr[i] <= pivot):
            i = i + 1
        while (i <= j and arr[j] >= pivot):
            j = j - 1
 
        if i <= j:
           arr[i], arr[j] = arr[j], arr[i]
        else:
            arr[begin], arr[j] = arr[j], arr[begin]
            return j
 
 
arr = input('Enter the list of numbers to be Sorted: ').split()
arr = [int(x) for x in arr]
quicksort(arr, 0, len(arr))
print('Sorted list: ', end='')
print(arr)

Output :-

Case – 1 :

Enter the list of numbers to be Sorted: 9 8 7 6 5 4 3 2 1 0

Sorted list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Enter the list of numbers to be Sorted: 5 1 10 4 12 6 8 3 15

Sorted list: [1, 3, 4, 5, 6, 8, 10, 12, 15]

• How the Bubble Sorting technique is implemented in Python
• Selection Sort : How to implement it in Python