Home//

QuickSort in Python: A Quick Implementation

# 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:

quicksort.py
``````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)
`````` 