Quick Sort as Divide and Conquer in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output list after the partition step using the last element as pivot in the quick sort algorithm on the list [8, 3, 7, 6, 2]?

DSA Python

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return arr

arr = [8, 3, 7, 6, 2]
result = partition(arr, 0, len(arr)-1)
print(result)

A [2, 3, 6, 7, 8]

B [2, 3, 7, 6, 8]

C [8, 3, 7, 6, 2]

D [3, 2, 7, 6, 8]

💡 Hint

Remember the pivot is the last element and elements smaller or equal go to the left.

The partition function moves all elements smaller or equal to the pivot (2) to the left and places the pivot after them. So 2 moves to the front, and 8 moves to the end.

❓ Predict Output

intermediate

Final Sorted List by Quick Sort

What is the final sorted list after applying quick sort on [4, 1, 9, 7, 3]?

DSA Python

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

arr = [4, 1, 9, 7, 3]
quick_sort(arr, 0, len(arr)-1)
print(arr)

A [1, 3, 4, 7, 9]

B [9, 7, 4, 3, 1]

C [1, 4, 3, 7, 9]

D [3, 1, 4, 7, 9]

💡 Hint

Quick sort sorts the list in ascending order.

Quick sort rearranges the list so that all elements are in ascending order: 1, 3, 4, 7, 9.

🧠 Conceptual

advanced

Understanding Quick Sort Pivot Choice

Which of the following statements about the pivot choice in quick sort is TRUE?

A Quick sort does not use a pivot element.

B Choosing the first element as pivot always guarantees the best performance.

C The pivot must always be the median of the list for quick sort to work.

D Choosing a pivot randomly can help avoid worst-case performance on sorted inputs.

💡 Hint

Think about how pivot choice affects performance on sorted or nearly sorted lists.

Choosing a random pivot helps avoid worst-case O(n²) time on already sorted or nearly sorted lists by reducing the chance of unbalanced partitions.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition

What error will this quick sort partition code cause when run on [5, 2, 9, 1]?

DSA Python

def partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    for j in range(low + 1, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[low], arr[i-1] = arr[i-1], arr[low]
    return i-1

arr = [5, 2, 9, 1]
pi = partition(arr, 0, len(arr))
print(arr, pi)

A IndexError because the loop misses the last element.

B No error, outputs [1, 2, 5, 9] and pivot index 2.

C TypeError due to wrong swap syntax.

D ValueError because pivot is not in the list.

💡 Hint

Check the range used in the for loop and the list length.

The for loop uses range(low + 1, high), but high is len(arr), so it excludes the last element index, causing incorrect partition and potential index errors.

🚀 Application

expert

Quick Sort Recursive Call Count

Given the list [10, 7, 8, 9, 1, 5], how many total recursive calls to quick_sort (including the initial call) are made until the list is fully sorted?

DSA Python

def quick_sort(arr, low, high, count=[0]):
    if low < high:
        count[0] += 1
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1, count)
        quick_sort(arr, pi + 1, high, count)
    return count[0]

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

arr = [10, 7, 8, 9, 1, 5]
calls = quick_sort(arr, 0, len(arr)-1)
print(calls)

A 11

B 7

C 9

D 5

💡 Hint

Count each time quick_sort is called with low < high.

The quick_sort function is called 9 times in total including the initial call for this list before it is fully sorted.

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