Quick Sort Algorithm 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 Quick Sort using the last element as pivot?

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++;
        std::swap(arr[i], arr[j]);
    }
}
std::swap(arr[i + 1], arr[high]);
// Print array after partition
for (int k = 0; k <= high; k++) {
    std::cout << 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 places elements smaller than pivot to the left and larger to the right.

The partition uses 2 as pivot. There are no elements less than 2, so the pivot is placed at index 0, and the array becomes 2 3 6 7 8.

❓ Predict Output

intermediate

Final Sorted Array by Quick Sort

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

DSA C++

int arr[] = {10, 7, 8, 9, 1, 5};
int n = 6;
// Assume quickSort(arr, 0, n-1) is called
// Print sorted array
for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
}

A 1 7 5 8 9 10

B 10 9 8 7 5 1

C 1 5 7 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, resulting in 1 5 7 8 9 10.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition Code

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 No error; works correctly

B Infinite loop during partition

C Runtime error due to invalid swap indices

D Off-by-one error causing incorrect partition

💡 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.

🧠 Conceptual

advanced

Quick Sort Worst Case Scenario

Which input array causes the worst-case time complexity for Quick Sort when using the last element as pivot?

A A random shuffled array

B An already sorted array in ascending order

C An array with all identical elements

D An array sorted in descending order

💡 Hint

Worst case happens when pivot divides array very unevenly.

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

❓ Predict Output

expert

Output of Quick Sort with Custom Pivot Selection

What is the output array after running Quick Sort with pivot chosen as middle element on this array?

DSA C++

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        int pivot = arr[mid];
        int i = low, j = high;
        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
            if (i <= j) {
                std::swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }
        if (low < j) quickSort(arr, low, j);
        if (i < high) quickSort(arr, i, high);
    }
}

int arr[] = {4, 9, 4, 8, 7, 3};
int n = 6;
quickSort(arr, 0, n - 1);
for (int k = 0; k < n; k++) {
    std::cout << arr[k] << " ";
}

A 3 4 4 7 8 9

B 3 4 4 8 7 9

C 4 3 4 7 8 9

D 4 4 3 7 8 9

💡 Hint

Pivot is middle element; partition around it and recursively sort.

The code sorts the array fully; final sorted array is 3 4 4 7 8 9.