Python · Theory

Quick Sort in Python

Theory

82/268

Quick Sort in Python

Quick Sort orders a list. Say the idea in plain words, then complexity. Bubble/insertion/selection are O(n²) teaching sorts. Merge and heap are O(n log n). Python’s built-in sort is Timsort (O(n log n), very fast in practice).

Dry-run Quick Sort on a tiny list like [4, 1, 3, 2] on the board. Interviewers care that you can trace one pass, not that you recite a textbook page.

For Quick Sort in real code: sorted(a) / a.sort() is what you use. Write the algorithm only when they ask you to implement it.

Quick Sort in Python — output — [1, 2, 3, 4]. Pivot 4, smaller left, bigger right.

Exam tip

Idea + complexity + one tiny trace. Then say when to use built-in sort.

Example

# Quick Sort in Python
def q(a):
    if len(a) <= 1:
        return a
    p = a[0]
    return q([x for x in a[1:] if x <= p]) + [p] + q([x for x in a[1:] if x > p])
print(q([4, 1, 3, 2]))

Quick Sort in Python — output: [1, 2, 3, 4]. Pivot 4, smaller left, bigger right.

Short notes

DefQuick Sort puts items in order.
RuleQuick Sort — know idea + O(...).
RememberQuick Sort — real code uses sorted() / Timsort.
TrapQuick Sort — implementing O(n²) in production when sorted() exists.

Python · Theory

Quick Sort in Python

← All stacks

Theory

82/268

Quick Sort in Python

Dry-run Quick Sort on a tiny list like [4, 1, 3, 2] on the board. Interviewers care that you can trace one pass, not that you recite a textbook page.

For Quick Sort in real code: sorted(a) / a.sort() is what you use. Write the algorithm only when they ask you to implement it.

Quick Sort in Python — output — [1, 2, 3, 4]. Pivot 4, smaller left, bigger right.

Exam tip

Idea + complexity + one tiny trace. Then say when to use built-in sort.

Example

# Quick Sort in Python
def q(a):
    if len(a) <= 1:
        return a
    p = a[0]
    return q([x for x in a[1:] if x <= p]) + [p] + q([x for x in a[1:] if x > p])
print(q([4, 1, 3, 2]))

Quick Sort in Python — output: [1, 2, 3, 4]. Pivot 4, smaller left, bigger right.

Short notes

DefQuick Sort puts items in order.
RuleQuick Sort — know idea + O(...).
RememberQuick Sort — real code uses sorted() / Timsort.
TrapQuick Sort — implementing O(n²) in production when sorted() exists.

Quick Sort in Python

Example

Short notes

Questions

Quick Sort in Python

Example

Short notes

Questions