Quick Sort as Divide and Conquer in DSA Python - Build from Scratch

Quick Sort as Divide and Conquer

📖 Scenario: You have a list of numbers that you want to sort from smallest to largest. Sorting helps you find things faster, like organizing books by their height on a shelf.

🎯 Goal: You will build a program that sorts a list of numbers using the Quick Sort method. Quick Sort works by picking a number, then arranging smaller numbers to the left and bigger numbers to the right, and repeating this step on each side.

📋 What You'll Learn

Create a list of numbers called numbers with the exact values: 29, 10, 14, 37, 13

Create a variable called pivot to hold the pivot value from the list

Write a function called quick_sort that sorts the list using the Quick Sort method

Print the sorted list after applying Quick Sort

💡 Why This Matters

🌍 Real World

Sorting is used everywhere, like arranging files, searching data quickly, or organizing products in a store.

💼 Career

Understanding Quick Sort helps in software development, data analysis, and any job that requires efficient data handling.

1

Create the list of numbers

Create a list called numbers with these exact values: 29, 10, 14, 37, 13

DSA Python

# Create the list called numbers with the given values
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Choose the pivot element

Create a variable called pivot and set it to the middle element of the numbers list using index 2

DSA Python

numbers = [29, 10, 14, 37, 13]
# Set pivot to the element at index 2 in numbers
# Your code here

Hint

Remember that list indexes start at 0, so the middle element is at index 2.

3

Write the Quick Sort function

Write a function called quick_sort that takes a list called arr and returns a sorted list using Quick Sort. Use the first element as the pivot inside the function. Split the list into less (elements less than pivot), equal (elements equal to pivot), and greater (elements greater than pivot). Recursively sort less and greater and combine them.

DSA Python

numbers = [29, 10, 14, 37, 13]
pivot = numbers[2]
# Define the quick_sort function below
# Your code here

Hint

Use list comprehensions to split the list. Remember to handle the base case when the list has 1 or 0 elements.

4

Print the sorted list

Use print to display the sorted list by calling quick_sort with the numbers list

DSA Python

numbers = [29, 10, 14, 37, 13]
pivot = numbers[2]

def quick_sort(arr):
    if len(arr)  pivot]
    return quick_sort(less) + equal + quick_sort(greater)

# Print the sorted list
# Your code here

Hint

Call quick_sort(numbers) inside the print statement to see the sorted list.

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