AI Hints
Home›DSA in Python Tutorial›Quick Sort and Keys
DSA in Python · Lesson 55 of 132

Quick Sort

Pick a pivot.

⏱ 2 min read▶ Video at 1:04:23🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Quick sort is another divide and conquer sort, and one of the fastest in practice. Pick one item, called the pivot. Put everything smaller on its left, and everything bigger on its right. Now the pivot is in its final place. Then quick sort each side.

Quick Sort
From the video: Quick Sort
  • Pick a pivot
  • Smaller left, bigger right
  • Repeat on each side

A simple quick sort

This version is written for clarity. We pick the middle item as the pivot. Three list comprehensions split the items into smaller, equal, and bigger. Then we quick sort the two outer groups, and join everything together. Run it.

quick.pypython
def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]
    smaller = [x for x in nums if x < pivot]
    equal = [x for x in nums if x == pivot]
    bigger = [x for x in nums if x > pivot]
    return quick_sort(smaller) + equal + quick_sort(bigger)

print(quick_sort([33, 10, 55, 71, 29, 3, 18, 42]))
Output
[3, 10, 18, 29, 33, 42, 55, 71]

Quick sort cost

On average, the pivot splits the list roughly in half, so quick sort is O of N log N, and very fast. But if the pivot is always the smallest or biggest item, the splits are lopsided, and it becomes O of N squared. Picking a random pivot, or the middle, makes that very unlikely.

keyvalue
AverageO(n log n)
WorstO(n²), bad pivots
Fixrandom or middle pivot
In practicevery fast

Summary

Quick sort places a pivot, splits around it, and recurses. Average O of N log N. Next, sorting by anything you like, with a key.

Key takeaways
  • Pick a pivot
  • Partition around it
  • Average O(n log n)
Next up: Sorting with key — sort by anything