Quick Sort as Divide and Conquer in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Quick Sort algorithm?

Quick Sort uses the divide and conquer approach by choosing a pivot element, then dividing the list into smaller parts with elements less than and greater than the pivot, and sorting these parts recursively.

beginner

What role does the pivot play in Quick Sort?

The pivot is the element used to split the list into two parts: elements smaller than the pivot go to one side, and elements larger go to the other side. This helps in sorting the list efficiently.

intermediate

Explain the divide and conquer steps in Quick Sort.

Divide: Choose a pivot and split the list into two parts based on the pivot.
Conquer: Recursively apply Quick Sort to the two parts.
Combine: Since the parts are sorted in place, no extra merging is needed.

intermediate

What is the average time complexity of Quick Sort and why?

The average time complexity is O(n log n) because the list is divided roughly in half each time (log n divisions), and each division requires scanning all elements (n).

beginner

Why can Quick Sort be faster than other sorting algorithms like Bubble Sort?

Quick Sort reduces the problem size quickly by dividing the list and sorting parts recursively, while Bubble Sort compares and swaps elements repeatedly without dividing, making Quick Sort more efficient on average.

What is the first step in the Quick Sort algorithm?

A Choose a pivot element

B Merge two sorted lists

C Swap all elements

D Find the maximum element

Quick Sort starts by choosing a pivot element to divide the list.

In Quick Sort, after choosing the pivot, the list is divided into parts with elements...

A Equal to the pivot only

B Sorted already

C Randomly shuffled

D Less than and greater than the pivot

The list is split into elements less than and greater than the pivot.

What is the time complexity of Quick Sort in the average case?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Quick Sort has average time complexity O(n log n) due to recursive division.

Which of these is NOT a step in Quick Sort?

A Divide the list using a pivot

B Merge sorted parts by extra space

C Recursively sort the divided parts

D Sort in place without extra merging

Quick Sort sorts in place and does not require merging with extra space.

Why is Quick Sort called a divide and conquer algorithm?

A Because it uses a queue

B Because it merges sorted lists

C Because it divides the problem and solves smaller parts recursively

D Because it sorts by swapping adjacent elements

Quick Sort divides the list and conquers by sorting smaller parts recursively.

Describe how Quick Sort uses the divide and conquer approach to sort a list.

Think about how the list is split and how smaller problems are solved.

Explain why Quick Sort is generally faster than simple sorting methods like Bubble Sort.

Focus on how Quick Sort handles the list differently.

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