Master Quick Sort in Python: From Simple Code to Optimized Implementation

Quick Sort Overview

Quick sort uses a divide‑and‑conquer strategy: the original problem is split into smaller sub‑problems that have the same structure, each sub‑problem is solved recursively, and the solutions are combined to form the final sorted list.

Divide‑and‑Conquer : Decompose the problem into smaller, similar sub‑problems, solve them recursively, then combine the results.

Basic Idea : Choose a pivot, partition the array so that elements left of the pivot are smaller and elements right are larger, then recursively sort the two partitions.

Python Implementation of Quick Sort

Below is a concise Python version often called a “pseudo‑quick‑sort”:

<code>def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less_than_pivot = [x for x in array if x <= pivot]
        more_than_pivot = [x for x in array if x > pivot]
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(more_than_pivot)</code>

The pivot is taken as the first element, and list comprehensions create two sub‑lists for elements less than or equal to, and greater than the pivot. While easy to understand, this version has several drawbacks:

The pivot choice is arbitrary and may not be near the median.

It uses extra space for the two sub‑lists and repeatedly scans the whole array.

For very small arrays, quick sort can be slower than insertion sort.

Recursive calls add overhead; optimization is advisable.

C‑Style Quick Sort in Python

A more classic implementation that mirrors the textbook algorithm:

<code>def quick_sort(L):
    return q_sort(L, 0, len(L) - 1)

def q_sort(L, left, right):
    if left < right:
        pivot = Partition(L, left, right)
        q_sort(L, left, pivot - 1)
        q_sort(L, pivot + 1, right)
    return L

def Partition(L, left, right):
    pivotkey = L[left]
    while left < right:
        while left < right and L[right] >= pivotkey:
            right -= 1
        L[left] = L[right]
        while left < right and L[left] <= pivotkey:
            left += 1
        L[right] = L[left]
    L[left] = pivotkey
    return left

L = [5, 9, 1, 11, 6, 7, 2, 4]
print(quick_sort(L))</code>

This version requires three parameters: the list to sort, the left index, and the right index. To simplify usage, a wrapper function is provided:

<code>def quick_sort(L):
    return q_sort(L, 0, len(L) - 1)</code>

The core of the algorithm is the Partition function, which selects a pivot (the first element) and rearranges the list so that elements smaller than the pivot move to the left and larger ones to the right. After partitioning, the pivot’s final index is returned, and the process recurses on the two sub‑lists.

Step‑by‑Step Example

Starting with the list [5, 9, 1, 11, 6, 7, 2, 4] :

Initial pivot = 5 (left=0, right=7). The algorithm swaps elements based on comparisons, progressively moving the left and right pointers.

After the first partition the list becomes [4, 2, 1, 5, 6, 7, 11, 9] and the pivot index returned is 3.

The sub‑lists [4, 2, 1] and [6, 7, 11, 9] are then sorted recursively using the same procedure.

Continuing this process eventually yields a fully sorted array.

Optimization Tips

Pivot Selection : Instead of always using the first element, choose a median‑of‑three or a random element to improve performance.

Space Usage : The simple version creates new sub‑lists; an in‑place version (as shown above) reduces memory overhead.

Hybrid Approach : For small sub‑arrays, switch to insertion sort to avoid quick sort’s overhead.

By applying these optimizations, quick sort becomes both faster and more memory‑efficient.

- END -