Quick Sort as Divide and Conquer in DSA Python - Time & Space Complexity

Time Complexity: Quick Sort as Divide and Conquer

O(n log n)

Understanding Time Complexity

We want to understand how the time to sort a list with Quick Sort changes as the list gets bigger.

How does Quick Sort's work grow when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

This code sorts a list by picking a pivot, splitting the list into smaller parts, and sorting those parts recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Splitting the list into three parts by comparing each element to the pivot.
• How many times: This splitting happens at each recursive call, which happens about log n times in the average case.

How Execution Grows With Input

Each time we split, we look at all elements once, then split into smaller parts to sort again.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons
100	About 700 to 800 comparisons
1000	About 10,000 to 12,000 comparisons

Pattern observation: The work grows a bit faster than just doubling; it grows roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a little faster than the size of the list, but much better than checking every pair.

Common Mistake

[X] Wrong: "Quick Sort always sorts in the same time no matter the input."

[OK] Correct: If the pivot is always the smallest or largest element, Quick Sort can take much longer, up to O(n²) time.

Interview Connect

Understanding Quick Sort's time complexity helps you explain why it is fast on average and what can slow it down, showing you know both the power and limits of this common sorting method.

Self-Check

"What if we always picked the first element as pivot instead of the middle? How would the time complexity change?"

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

easy

A. Divide the list into smaller parts, sort them, and combine results

B. Sort the list by comparing every element with every other element

C. Use extra space to merge sorted lists

D. Sort the list by repeatedly swapping adjacent elements

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort divides the list into smaller parts based on a pivot, sorts each part, then combines them.

2. Step 2: Compare with other sorting ideas

   Unlike bubble sort or merge sort, Quick Sort uses partitioning without extra space for merging.

3. Final Answer:

   Divide the list into smaller parts, sort them, and combine results -> Option A

4. Quick Check:

   Divide and conquer = splitting and sorting parts [OK]

Hint: Quick Sort splits and sorts parts separately [OK]

Common Mistakes:

• Confusing Quick Sort with bubble sort
• Thinking Quick Sort always uses extra space
• Believing Quick Sort compares all pairs

2. Which of the following is the correct way to choose a pivot in a Quick Sort implementation in Python to avoid worst-case scenarios?

easy

A. pivot = arr[0]

B. pivot = arr[len(arr)]

C. pivot = arr[len(arr)//2]

D. pivot = arr[-len(arr)]

Solution

1. Step 1: Identify good pivot strategies

   Pivot choice affects performance; first or equivalent leads to worst case on sorted data.

2. Step 2: Check each option

   A and C (equivalent to first) bad for sorted input. B out of range error. D middle element helps balance partitions.

3. Final Answer:

   pivot = arr[len(arr)//2] -> Option C

4. Quick Check:

   Middle pivot avoids unbalanced partitions [OK]

Hint: Middle pivot balances better than first [OK]

Common Mistakes:

• Using arr[len(arr)] causes IndexError
• Picking first element for all cases
• Using unusual negative indexing

3. What will be the output of the following Python code using Quick Sort?

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

print(quick_sort([3, 6, 2, 7, 5]))

medium

A. [3, 2, 6, 5, 7]

B. [2, 3, 5, 6, 7]

C. [7, 6, 5, 3, 2]

D. [2, 3, 6, 5, 7]

Solution

1. Step 1: Trace the partitioning

   Pivot is 3. less = [2], greater = [6,7,5]. Recursively sort less and greater.

2. Step 2: Recursively sort less and greater

   quick_sort([2]) returns [2]. quick_sort([6,7,5]) picks pivot 6, less=[5], greater=[7]. Sorting less and greater gives [5] and [7].

3. Step 3: Combine results

   quick_sort([6,7,5]) returns [5,6,7]. Final result is [2] + [3] + [5,6,7] = [2,3,5,6,7].

4. Final Answer:

   [2, 3, 5, 6, 7] -> Option B

5. Quick Check:

   Sorted list = [2, 3, 5, 6, 7] [OK]

Hint: Follow pivot splits and recursive calls carefully [OK]

Common Mistakes:

• Not including pivot in final list
• Mixing less and greater lists order
• Forgetting base case for recursion

4. Identify the error in this Quick Sort code snippet:

def quick_sort(arr):
    if len(arr) == 0:
        return arr
    pivot = arr[0]
    less = [x for x in arr if x < pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

medium

A. Greater list should include elements equal to pivot

B. Pivot should be last element, not first

C. Less list includes pivot causing infinite recursion

D. Base case should be len(arr) <= 1, not == 0

Solution

1. Step 1: Check base case

   len(arr) == 0 handles empty lists fine; len(arr) <= 1 is more conventional but not required here.

2. Step 2: Analyze less and greater lists

   less takes x < pivot, greater x > pivot from entire arr. Pivot excluded correctly, but elements equal to pivot (duplicates) excluded from both.

3. Step 3: Identify the cause of incorrect output

   Duplicates equal to pivot are lost; should partition equals into less (<=) or greater (>=).

4. Final Answer:

   Greater list should include elements equal to pivot -> Option A

5. Quick Check:

   Strict < and > lose duplicates [OK]

Hint: Handle equals in one partition to avoid losing duplicates [OK]

Common Mistakes:

• Using wrong base case length
• Including pivot in less or greater lists
• Not handling equal elements properly

5. Given the list [4, 2, 5, 2, 3, 4], how many recursive calls will the following Quick Sort function make until fully sorted?

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

quick_sort([4, 2, 5, 2, 3, 4])

hard

A. 6

B. 9

C. 5

D. 7

Solution

1. Step 1: Trace recursive calls

   Initial call with [4,2,5,2,3,4]. Pivot=4. less=[2,2,3,4], greater=[5].

2. Step 2: Recursive call on less=[2,2,3,4]

   Pivot=2. less=[2], greater=[3,4].

3. Step 3: Recursive call on less=[2]

   Length 1, base case, no rec calls.

4. Step 4: Recursive call on greater=[3,4]

   Pivot=3. less=[], greater=[4].

5. Step 5: Recursive calls on less=[] and greater=[4]

   Both base cases, no further rec calls.

6. Step 6: Recursive call on greater=[5]

   Base case.

7. Step 7: Count total recursive calls

   Counting all calls including base cases: initial call + quick_sort(less) + quick_sort(greater) + recursive calls inside less and greater partitions results in 7 total calls.

8. Final Answer:

   7 -> Option D

9. Quick Check:

   Count each function call including base cases [OK]

Hint: Count each function call including base cases [OK]

Common Mistakes:

• Ignoring base case calls
• Counting only partition steps
• Miscounting calls on empty lists