Quick Sort Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort on a small list

What is the output of the following Python code after sorting the list using Quick Sort?

DSA Python

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)

print(quick_sort([3, 6, 8, 10, 1, 2, 1]))

A [1, 2, 3, 6, 8, 10]

B [10, 8, 6, 3, 2, 1, 1]

C [1, 1, 2, 3, 6, 8, 10]

D [3, 6, 8, 10, 1, 2, 1]

💡 Hint

Remember Quick Sort divides the list around a pivot and sorts recursively.

The code picks the middle element as pivot and recursively sorts elements less than and greater than the pivot. The final output is the sorted list in ascending order.

🧠 Conceptual

intermediate

Understanding Quick Sort Partitioning

In Quick Sort, what is the main purpose of the partition step?

A To divide the list into two parts where elements less than pivot are on the left and greater on the right

B To reverse the list before sorting

C To find the maximum element in the list

D To merge two sorted lists into one sorted list

💡 Hint

Think about how Quick Sort organizes elements around the pivot.

Partitioning rearranges elements so that those smaller than the pivot come before it and those larger come after, enabling recursive sorting.

🔧 Debug

advanced

Identify the error in this Quick Sort implementation

What error will this Quick Sort code produce when run?

DSA Python

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

print(quick_sort([3, 6, 8, 10, 1, 2, 1]))

A The code loses duplicate elements equal to the pivot

B The code runs correctly and outputs [1, 1, 2, 3, 6, 8, 10]

C The code raises a TypeError

D The code outputs the list in descending order

💡 Hint

Check how elements equal to the pivot are handled in the list comprehensions.

Elements equal to the pivot are excluded from both left and right lists, causing duplicate elements equal to the pivot to be lost.

❓ Predict Output

advanced

Output of Quick Sort with duplicates and negative numbers

What is the output of this Quick Sort code?

DSA Python

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    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)

print(quick_sort([0, -1, 5, 3, -1, 5, 2]))

A [5, 5, 3, 2, 0, -1, -1]

B [-1, -1, 0, 2, 3, 5, 5]

C [-1, 0, 2, 3, 5]

D [0, -1, 5, 3, -1, 5, 2]

💡 Hint

Remember the pivot is the last element and duplicates are handled in the middle list.

The code sorts the list including duplicates and negative numbers correctly in ascending order.

🧠 Conceptual

expert

Time Complexity of Quick Sort in Worst Case

What is the worst-case time complexity of Quick Sort and when does it occur?

A O(n), when the list is already sorted

B O(n log n), when the pivot divides the list into two equal halves

C O(log n), when the list has many duplicates

D O(n^2), when the pivot is always the smallest or largest element

💡 Hint

Think about how unbalanced partitions affect recursion depth.

Worst case happens when pivot picks smallest or largest element causing unbalanced partitions and O(n^2) time.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Sort the list by inserting elements into their correct position one by one

B. Sort the list by repeatedly swapping adjacent elements

C. Divide the list into smaller parts using a pivot and sort them recursively

D. Sort the list by merging two sorted halves

Solution

1. Step 1: Understand Quick Sort approach

   Quick Sort picks a pivot element and divides the list into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting

   It then sorts these parts recursively, combining them to get the sorted list.

3. Final Answer:

   Divide the list into smaller parts using a pivot and sort them recursively -> Option C

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: pivot divides list, then sort parts recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges sorted halves
• Assuming Quick Sort inserts elements one by one

2. Which of the following is the correct way to define the partition function header in Python for Quick Sort?

easy

A. def partition(arr, low, high):

B. def partition(arr):

C. def partition(low, high):

D. def partition(arr, pivot):

Solution

1. Step 1: Identify required parameters

   The partition function needs the array and the current low and high indices to work on a sublist.

2. Step 2: Match function signature

   Only def partition(arr, low, high): correctly includes all three parameters: arr, low, and high.

3. Final Answer:

   def partition(arr, low, high): -> Option A

4. Quick Check:

   Partition needs array and index bounds [OK]

Hint: Partition needs array plus low and high indexes [OK]

Common Mistakes:

• Omitting low and high parameters
• Using pivot as parameter instead of indices
• Defining partition with only one parameter

3. What will be the output of the following code snippet?

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 = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr, 0, len(arr) - 1)
print(arr)

medium

A. [1, 1, 2, 3, 6, 8, 10]

B. [10, 8, 6, 3, 2, 1, 1]

C. [3, 6, 8, 10, 1, 2, 1]

D. [1, 2, 1, 3, 6, 8, 10]

Solution

1. Step 1: Understand partition and recursive calls

   The partition function places the pivot in correct position and divides array into smaller and larger parts. Quick sort recursively sorts these parts.

2. Step 2: Trace sorting of given array

   Starting with [3,6,8,10,1,2,1], after full recursion, the array becomes sorted ascending: [1,1,2,3,6,8,10].

3. Final Answer:

   [1, 1, 2, 3, 6, 8, 10] -> Option A

4. Quick Check:

   Quick Sort output = sorted array ascending [OK]

Hint: Quick Sort outputs sorted array ascending by default [OK]

Common Mistakes:

• Thinking Quick Sort sorts descending by default
• Confusing original array with sorted output
• Ignoring pivot placement effect

4. Identify the error in this Quick Sort partition function:

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

medium

A. Swapping inside the loop is incorrect

B. Pivot should be arr[high] instead of arr[low]

C. Return statement should return 'i' instead of 'i-1'

D. The for loop should include 'high' index by using range(low + 1, high + 1)

Solution

1. Step 1: Check loop range for partitioning

   The for loop uses range(low + 1, high), which excludes the 'high' index element. It should include 'high' to consider the pivot's correct position.

2. Step 2: Correct loop range

   Changing to range(low + 1, high + 1) includes the last element, ensuring all elements are compared to pivot.

3. Final Answer:

   The for loop should include 'high' index by using range(low + 1, high + 1) -> Option D

4. Quick Check:

   Loop must cover full sublist including high index [OK]

Hint: Loop must include high index to compare all elements [OK]

Common Mistakes:

• Forgetting to include last element in loop
• Changing pivot position unnecessarily
• Returning wrong index after partition

5. You want to sort a list of strings by their length using Quick Sort. Which modification to the partition function is correct?

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

What should replace ??? to sort by string length?

hard

A. arr[j].startswith(pivot)

B. len(arr[j]) <= len(pivot)

C. len(arr[j]) >= len(pivot)

D. arr[j] <= pivot

Solution

1. Step 1: Understand sorting by string length

   To sort strings by length, compare lengths of elements, not the strings themselves.

2. Step 2: Replace condition with length comparison

   Using len(arr[j]) <= len(pivot) ensures elements with length less or equal to pivot's length go left.

3. Final Answer:

   len(arr[j]) <= len(pivot) -> Option B

4. Quick Check:

   Compare lengths to sort strings by length [OK]

Hint: Compare lengths, not strings, to sort by length [OK]

Common Mistakes:

• Comparing strings lexicographically instead of length
• Using >= instead of <= causing reverse order
• Using unrelated string methods like startswith