Editor

Python Program for Quick Sort

Intermediate · Searching and sorting

Quick sort picks one element, called the pivot, and splits the rest of the list into the elements smaller than the pivot and the elements larger than it. The pivot is then in its final place, and the two sides are sorted the same way. This program uses the last element as the pivot and prints each split.

Program

quick_sort.py
def quick_sort(items, depth=0):
if len(items) <= 1:
return items # nothing left to sort
pivot = items[-1] # use the last item as the pivot
smaller = []
larger = []
for x in items[:-1]:
if x <= pivot:
smaller.append(x)
else:
larger.append(x)
print(" " * depth + f"Pivot {pivot}: {smaller} | {pivot} | {larger}")
# The pivot is in its final place; sort each side the same way
return quick_sort(smaller, depth + 1) + [pivot] + quick_sort(larger, depth + 1)
numbers = [33, 10, 55, 71, 29, 3, 18, 42]
print("Original list:", numbers)
sorted_list = quick_sort(numbers)
print("Sorted list:", sorted_list)
Output
Original list: [33, 10, 55, 71, 29, 3, 18, 42]
Pivot 42: [33, 10, 29, 3, 18] | 42 | [55, 71]
  Pivot 18: [10, 3] | 18 | [33, 29]
    Pivot 3: [] | 3 | [10]
    Pivot 29: [] | 29 | [33]
  Pivot 71: [55] | 71 | []
Sorted list: [3, 10, 18, 29, 33, 42, 55, 71]

How it works

  1. The last element, 42, is the first pivot.
  2. Every other element goes into smaller or larger depending on how it compares with the pivot.
  3. Everything in smaller belongs before the pivot and everything in larger after it, so the pivot is already where it belongs in the sorted list.
  4. The function then sorts smaller and larger by calling itself, and joins the pieces: smaller, pivot, larger.
  5. Quick sort usually takes about n x log n steps, but a list that is already sorted gives bad pivots and about n x n steps.

Other ways to write it

In place, with a partition function

In place, with a partition function
def partition(a, low, high):
pivot = a[high]
i = low - 1 # end of the "smaller than pivot" part
for j in range(low, high):
if a[j] <= pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[high] = a[high], a[i + 1] # put the pivot after them
return i + 1
def quick_sort(a, low, high):
if low < high:
p = partition(a, low, high)
quick_sort(a, low, p - 1)
quick_sort(a, p + 1, high)
numbers = [33, 10, 55, 71, 29, 3, 18, 42]
quick_sort(numbers, 0, len(numbers) - 1)
print("Sorted in place:", numbers)
Output
Sorted in place: [3, 10, 18, 29, 33, 42, 55, 71]

This is the textbook version: partition() moves the smaller items to the left by swapping inside the same list, so no new lists are made.

Short version with list comprehensions

Short version with list comprehensions
def quick_sort(items):
if len(items) <= 1:
return items
pivot = items[0]
rest = items[1:]
return (quick_sort([x for x in rest if x < pivot])
+ [pivot]
+ quick_sort([x for x in rest if x >= pivot]))
print("Sorted list:", quick_sort([33, 10, 55, 71, 29, 3, 18, 42]))
Output
Sorted list: [3, 10, 18, 29, 33, 42, 55, 71]

The same idea in a few lines, using the first item as the pivot. It is easy to read, but it builds many new lists.

Try it yourself

Run the main program on [1, 2, 3, 4, 5, 6] and count how many lines it prints, to see why a sorted list is the worst case for this pivot choice.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises