QuickSort in Python: A Quick Implementation

QuickSort in Python: A Quick Implementation

Minh Vu

By Minh Vu

Updated Nov 07, 2023

Quicksort, as its name, is one of the fastest sorting algorithms invented by Tony Hoare in 1959.

After this tutorial, I ensure you can achieve 2 things:

  • Understand how the Quicksort algorithm works.
  • Implement the Quicksort algorithm in Python.

Let's begin!

1. How Quicksort Works


Before going to the quicksort algorithm, you need to understand the divide-and-conquer paradigm.

Divide-and-conquer is used to find the optimal solution by breaking down the problem into smaller sub-problems. Then, we solve each sub-problem and combine the results to get the final solution.

The divide-and-conquer paradigm consists of 3 steps:

  1. Divide: Break the problem into smaller sub-problems.
  2. Conquer: Solve each sub-problem recursively.
  3. Combine: Combine the results of each sub-problem to get the final solution.

Quicksort Algorithm

The quicksort algorithm is based on the divide-and-conquer paradigm.

The quicksort algorithm consists of 2 steps:

  1. Divide: Choose a pivot element* and partition the array into 2 sub-arrays: the left sub-array contains elements smaller than the pivot, and the right sub-array contains elements greater than the pivot.
  2. Conquer: Recursively sort the left and right sub-arrays.

*The pivot element is chosen randomly or deterministically. In this tutorial, we choose the middle element as the pivot.

2. QuickSort Implementation in Python

Here is the implementation of the quicksort algorithm in Python:

def quicksort(arr, low, high): if low < high: pivot_index = partition(arr, low, high) quicksort(arr, low, pivot_index) quicksort(arr, pivot_index + 1, high) def partition(arr, low, high): pivot = arr[low] left = low + 1 right = high done = False while not done: while left <= right and arr[left] <= pivot: left = left + 1 while arr[right] >= pivot and right >= left: right = right - 1 if right < left: done = True else: arr[left], arr[right] = arr[right], arr[left] arr[low], arr[right] = arr[right], arr[low] return right # Example usage: arr = [3, 6, 8, 10, 1, 2, 1] quicksort(arr, 0, len(arr) - 1) print(arr)
You can search for other posts at home page.
Minh Vu

Minh Vu

Software Engineer

Hi guys, I'm the author of WiseCode Blog. I mainly work with the Elastic Stack and build AI & Python projects. I also love writing technical articles, hope you guys have good experience reading my blog!