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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output array after the partition step in this Quick Sort code snippet?

DSA C++

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;
    int pi = partition(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

A [1, 5, 7, 8, 9, 10] (pivot index 2)

B [1, 5, 7, 8, 9, 10] (pivot index 4)

C [1, 5, 7, 8, 9, 10]

D [1, 5, 7, 8, 9, 10] (pivot index 3)

💡 Hint

Remember the pivot is the last element and partition places it in the correct position.

The partition function uses the last element as pivot (5). After partition, all elements less than 5 are before it. The pivot 5 ends at index 2, so the array is rearranged as [1, 5, 7, 8, 9, 10].

🧠 Conceptual

intermediate

Understanding Quick Sort's Divide and Conquer

Which statement best describes the divide and conquer approach in Quick Sort?

A Quick Sort uses a heap to repeatedly extract the smallest element.

B Quick Sort sorts the array by repeatedly swapping adjacent elements.

C Quick Sort merges two sorted arrays into one sorted array.

D Quick Sort divides the array into two parts around a pivot and sorts each part recursively.

💡 Hint

Think about how Quick Sort breaks down the problem into smaller parts.

Quick Sort picks a pivot, partitions the array into elements less than and greater than the pivot, then recursively sorts these parts. This is the divide and conquer strategy.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition

What error will this Quick Sort partition code cause when run?

DSA C++

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            std::swap(arr[i], arr[j]);
            i++;
        }
    }
    std::swap(arr[i], arr[high]);
    return i;
}

A Off-by-one error causing incorrect partitioning.

B No error, code runs correctly and partitions array.

C Runtime error due to invalid index access.

D Infinite loop because loop condition is wrong.

💡 Hint

Check the initial value of i and how it moves.

The variable i starts at low instead of low - 1, causing the partition to swap incorrectly and produce wrong partitioning results.

❓ Predict Output

advanced

Final Sorted Array After Quick Sort

What is the final sorted array after running Quick Sort on this input?

DSA C++

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

int main() {
    int arr[] = {4, 2, 6, 9, 3};
    int n = 5;
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

A [2, 3, 4, 6, 9]

B [2, 3, 4, 9, 6]

C [9, 6, 4, 3, 2]

D [4, 2, 3, 6, 9]

💡 Hint

Quick Sort sorts the array in ascending order.

Quick Sort correctly sorts the array into ascending order: 2, 3, 4, 6, 9.

🧠 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 log n), occurs when pivot divides array evenly.

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

C O(n), occurs when array is already sorted.

D O(log n), occurs when array has many duplicates.

💡 Hint

Think about how unbalanced partitions affect recursion depth.

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

Practice

1. What is the main idea behind the Quick Sort algorithm as a divide and conquer method?

easy

A. Use extra memory to merge two sorted arrays

B. Sort the array by repeatedly swapping adjacent elements

C. Divide the array into smaller parts, sort them, and combine results

D. Sort the array by selecting the smallest element each time

Solution

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

   Quick Sort divides the array into parts around a pivot, then sorts each part separately.

2. Step 2: Recognize the sorting and combining process

   After dividing, it sorts the parts recursively and combines them by the nature of recursion.

3. Final Answer:

   Divide the array into smaller parts, sort them, and combine results -> Option C

4. Quick Check:

   Divide and conquer = divide, sort, combine [OK]

Hint: Remember: divide, sort parts, then combine [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort uses extra memory like Merge Sort
• Believing Quick Sort selects smallest element each time

2. Which of the following is the correct way to declare the partition function header in C++ for Quick Sort?

easy

A. void partition(int arr[], int low, int high);

B. int partition(int arr[], int low, int high);

C. int partition(int arr, int low, int high);

D. int partition(int arr[], int start, int end, int pivot);

Solution

1. Step 1: Identify correct parameter types

   The partition function takes an array and two indices low and high to work on a subarray.

2. Step 2: Check return type

   Partition returns an integer index where the pivot finally sits.

3. Final Answer:

   int partition(int arr[], int low, int high); -> Option B

4. Quick Check:

   Partition returns int index with arr[], low, high [OK]

Hint: Partition returns pivot index, takes array and two indices [OK]

Common Mistakes:

• Using void return type for partition
• Passing array as int instead of int[]
• Adding extra parameters like pivot unnecessarily

3. What will be the output array after one partition call on arr = [4, 7, 2, 9, 1] with low=0 and high=4 if pivot is chosen as last element?

medium

A. [1, 4, 2, 7, 9]

B. [4, 7, 2, 9, 1]

C. [1, 2, 7, 9, 4]

D. [1, 7, 2, 9, 4]

Solution

1. Step 1: Choose pivot and start partitioning

   Pivot is last element: 1. There are no elements less than 1.

2. Step 2: Rearrange array around pivot

   No swaps occur in the loop since all arr[j] > 1 for j = 0 to 3. Then swap arr[0] and arr[4], resulting in [1, 7, 2, 9, 4].

3. Final Answer:

   [1, 7, 2, 9, 4] -> Option D

4. Quick Check:

   Pivot 1 placed at position 0, all to right > 1 [OK]

Hint: Pivot last element, smaller left, larger right [OK]

Common Mistakes:

• Not moving pivot to correct position
• Swapping elements incorrectly
• Assuming pivot stays at end

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

int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low;
  for (int j = low; j < high; j++) {
    if (arr[j] < pivot) {
      swap(arr[i], arr[j]);
      i++;
    }
  }
  swap(arr[i], arr[high]);
  return i;
}

medium

A. Initialization of i should be low - 1

B. Loop should run until j <= high

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

D. Swap inside if should be swap(arr[j], arr[i])

Solution

1. Step 1: Check initialization of i

   i should start at low - 1 to track last smaller element index before loop.

2. Step 2: Understand loop and swaps

   Loop runs j from low to high-1 correctly; swapping arr[i+1] and arr[high] places pivot correctly.

3. Final Answer:

   Initialization of i should be low - 1 -> Option A

4. Quick Check:

   i = low - 1 needed for correct partition [OK]

Hint: i starts before low to track smaller elements [OK]

Common Mistakes:

• Starting i at low causes wrong swaps
• Loop running to high causes out-of-bound errors
• Changing pivot position unnecessarily

5. Given an array arr = [10, 80, 30, 90, 40, 50, 70], what is the state of the array after the first full Quick Sort partition step choosing the last element as pivot?

hard

A. [10, 30, 40, 50, 70, 80, 90]

B. [10, 30, 40, 50, 70, 90, 80]

C. [10, 80, 30, 90, 40, 50, 70]

D. [10, 30, 40, 50, 80, 90, 70]

Solution

1. Step 1: Identify pivot and partition

   Pivot is last element 70. Partition rearranges elements less than 70 to left.

2. Step 2: Rearrange array after partition

   Elements less than 70: 10, 30, 40, 50. Elements greater: 80, 90. After partition, pivot 70 placed after smaller elements: [10, 30, 40, 50, 70, 80, 90]

3. Final Answer:

   [10, 30, 40, 50, 70, 80, 90] -> Option A

4. Quick Check:

   Pivot 70 placed after smaller elements [OK]

Hint: Pivot last, smaller left, pivot placed next, larger right [OK]

Common Mistakes:

• Sorting entire array in first step
• Swapping pivot with wrong element
• Assuming pivot moves to last position