Python DSALesson 108Free preview

Quick Sort

This lesson is part of Python · All levels

Summary

This lesson is about Quick Sort, a divide and conquer algorithm that selects a pivot and then divides the data into two groups, smaller and larger than the pivot. Each group is then sorted recursively. With a good pivot, quick sort works on average and includes the fastest sequencing algorithm for big data.

Key points

Quick sort step: select the pivot, partition the data, and then sort the two parts recursively.
Average, but worst case scenario if pivot is always the most extreme element.
The pivot selection can be the first, middle, or median of three.
Versions with a simple list comprehension still require additional memory.
Quick sort is generally stable, but very fast in practice because it is cache-friendly.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.