bhylu.com

Advertisements

Quick Sort

Quicksort partitions values around a pivot, then sorts the smaller partitions. Its expected efficiency depends on partitioning and pivot choices.

Understand the idea

This readable educational version allocates separate lists for lower, equal, and higher values. It preserves duplicates explicitly, but is not the space-efficient in-place partition version. Average behaviour can be O(n log n), while poor partitions can lead to quadratic work and deep recursion. Python's built-in sort avoids needing a hand-written quicksort in ordinary applications.

Where to try it

Open this example with Try in playground. The code loads as editable text and does not run until you select Run. The first run downloads Python. Each run starts fresh; temporary files created by a script are not files on your PC.

A worked example

Python
Try in playground

def quick_sort(values):
    if len(values) < 2:
        return list(values)
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

print(quick_sort([8, 3, 5, 3]))

Read the result

The result is [3, 3, 5, 8]. The equality partition keeps repeated pivot values.

Try one change

Test all-equal input and explain why the equal partition prevents endless repartitioning.