QuickSort in Python: A Quick Implementation

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

Divide-and-Conquer

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)