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.