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 state of the array after the partition step if the pivot is chosen as the last element?

DSA C

int arr[] = {8, 3, 7, 6, 2};
int low = 0, high = 4;
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
    if (arr[j] < pivot) {
        i++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// Print array state
for (int k = 0; k <= high; k++) {
    printf("%d ", arr[k]);
}

A 2 3 6 7 8

B 3 2 6 7 8

C 2 3 7 6 8

D 3 6 2 7 8

💡 Hint

Remember the partition step moves elements smaller than pivot to the left.

The partition step places all elements smaller than pivot (2) before it. Since 2 is the smallest element, it moves to index 0, resulting in 2 3 7 6 8. However, 3, 7, and 6 remain in their relative order after partitioning, so the array after partition is 2 3 7 6 8. But since 3, 6, and 7 are not all smaller than pivot, the correct partition places 2 at the start and the rest after it. The correct final array after partition is 2 3 7 6 8, which matches option A.

🧠 Conceptual

intermediate

Understanding Quick Sort's Divide and Conquer

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

A Sort the array by repeatedly swapping adjacent elements until sorted.

B Divide the array into two halves, sort each half recursively, then merge them.

C Select a pivot, partition the array around the pivot, then recursively sort the partitions.

D Split the array into single elements, then combine them without sorting.

💡 Hint

Focus on how Quick Sort uses a pivot to split the array.

Quick Sort picks a pivot, partitions the array so smaller elements go left, larger go right, then sorts partitions recursively.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition Code

What error will this 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) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }
    int temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;
    return i;
}

A Off-by-one error causing incorrect partition index

B Array index out of bounds error

C No error, code runs correctly

D Infinite loop due to wrong loop condition

💡 Hint

Check how variable i is initialized and incremented.

Variable i should start at low - 1 to correctly track smaller elements; starting at low causes wrong partition index.

❓ Predict Output

advanced

Final Sorted Array After Quick Sort

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

DSA C

int arr[] = {10, 7, 8, 9, 1, 5};
int n = 6;
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);
    }
}
// Assume partition is correctly implemented
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
}

A 10 9 8 7 5 1

B 1 5 7 8 9 10

C 1 7 5 8 9 10

D 5 1 7 8 9 10

💡 Hint

Quick Sort sorts the array in ascending order.

Quick Sort sorts the array fully in ascending order: 1 5 7 8 9 10.

🧠 Conceptual

expert

Quick Sort Worst Case Scenario

Which input array causes Quick Sort to have its worst-case time complexity?

A An array with all identical elements

B A randomly shuffled array

C An array sorted in reverse order when pivot is chosen as the middle element

D An already sorted array when pivot is always chosen as the last element

💡 Hint

Worst case happens when partitioning is unbalanced.

Choosing last element as pivot on sorted array causes unbalanced partitions, leading to O(n^2) time.

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

easy

A. Compare each element with every other element to sort

B. Divide the array into smaller parts using a pivot and sort them recursively

C. Merge two sorted arrays into one sorted array

D. Insert elements one by one into the correct position

Solution

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

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

2. Step 2: Recursive sorting of parts

   It then sorts these parts recursively, combining results to get a sorted array.

3. Final Answer:

   Divide the array into smaller parts using a pivot and sort them recursively -> Option B

4. Quick Check:

   Quick Sort = Divide and conquer with pivot [OK]

Hint: Remember pivot splits array for recursive sorting [OK]

Common Mistakes:

• Confusing Quick Sort with Merge Sort
• Thinking Quick Sort compares all pairs
• Believing Quick Sort inserts elements one by one

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

easy

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

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

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

D. int partition(int arr[], int low);

Solution

1. Step 1: Check parameter types for partition

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

2. Step 2: Check return type

   It returns an integer index where the pivot ends after partitioning.

3. Final Answer:

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

4. Quick Check:

   Partition returns pivot index with array and bounds [OK]

Hint: Partition returns pivot index, needs array and bounds [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Missing one of the index parameters

3. What will be the output array after calling Quick Sort on arr = {3, 6, 8, 10, 1, 2, 1}?

medium

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

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

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

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

Solution

1. Step 1: Apply Quick Sort to the array

   Quick Sort rearranges elements so smaller come before pivot and larger after, recursively sorting subarrays.

2. Step 2: Sort the given array

   Sorting {3,6,8,10,1,2,1} results in {1,1,2,3,6,8,10} in ascending order.

3. Final Answer:

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

4. Quick Check:

   Sorted array = ascending order [OK]

Hint: Quick Sort outputs sorted array ascending [OK]

Common Mistakes:

• Assuming original array stays same
• Confusing ascending with descending order
• Misplacing duplicate elements

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) {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return i + 1;
}

medium

A. For loop should run until j <= high

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

C. Swap should be called outside the loop only

D. Variable i should start at low - 1

Solution

1. Step 1: Check initialization of i

   In partition, i should start at low - 1 to correctly track smaller elements before j.

2. Step 2: Analyze loop and swaps

   Starting i at low causes incorrect swaps and wrong pivot placement.

3. Final Answer:

   Variable i should start at low - 1 -> Option D

4. Quick Check:

   i = low - 1 fixes partition indexing [OK]

Hint: Initialize i to low - 1 before loop [OK]

Common Mistakes:

• Starting i at low causes off-by-one errors
• Changing pivot position incorrectly
• Loop running beyond high index

5. Given an array with many duplicate elements, which modification to Quick Sort helps improve performance?

hard

A. Avoid recursion and use iterative sorting only

B. Always pick the first element as pivot

C. Use a three-way partitioning to separate less, equal, and greater elements

D. Skip sorting duplicates to save time

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Duplicates cause many equal elements to be repeatedly partitioned, slowing sorting.

2. Step 2: Apply three-way partitioning

   Three-way partitioning divides array into less than, equal to, and greater than pivot, reducing redundant work.

3. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option C

4. Quick Check:

   Three-way partitioning optimizes duplicates [OK]

Hint: Three-way partition handles duplicates efficiently [OK]

Common Mistakes:

• Picking fixed pivot causes worst-case time
• Skipping duplicates breaks sorting correctness
• Avoiding recursion does not fix duplicate issue