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.

Practice

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

easy

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

B. Compare every element with every other element and swap if needed

C. Insert elements one by one into a sorted list

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element 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 them to get the sorted array.

3. Final Answer:

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

4. Quick Check:

   Quick Sort = Divide and conquer using pivot [OK]

Hint: Remember: Quick Sort uses a pivot to split and sort recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges arrays like Merge Sort
• Assuming 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. void partition(int arr[], int low, int high);

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

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

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

Solution

1. Step 1: Check parameter types and order

   The partition function takes an array and two indices: low and high, both integers.

2. Step 2: Check return type

   It returns an integer index where the pivot finally lies.

3. Final Answer:

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

4. Quick Check:

   Correct function signature = int partition(int arr[], int low, int high); [OK]

Hint: Partition returns pivot index; parameters are array and two ints [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Swapping low and high parameters

3. What will be the output array after applying Quick Sort on arr = {4, 2, 7, 1} using the last element as pivot?

medium

A. [1, 2, 4, 7]

B. [1, 4, 2, 7]

C. [2, 1, 4, 7]

D. [7, 4, 2, 1]

Solution

1. Step 1: Partition with pivot 1

   Pivot is 1 (last element). After partition, array becomes [1, 2, 7, 4] with pivot at index 0.

2. Step 2: Recursively sort subarrays

   Left subarray is empty; right subarray [2,7,4] is sorted recursively to [2,4,7]. Final array is [1,2,4,7].

3. Final Answer:

   [1, 2, 4, 7] -> Option A

4. Quick Check:

   Sorted array = [1, 2, 4, 7] [OK]

Hint: Pivot last element; sort left and right recursively [OK]

Common Mistakes:

• Not placing pivot correctly after partition
• Sorting only once without recursion
• Confusing pivot with first element

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. Swap should be done only if arr[j] <= pivot

B. Loop should run from j = low to j <= high

C. Initialization of i should be low - 1

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

Solution

1. Step 1: Check initialization of i

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

2. Step 2: Analyze loop and swaps

   Loop runs j from low to high-1 correctly; swap with arr[i+1] after loop is correct.

3. Final Answer:

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

4. Quick Check:

   i starts at low - 1 in partition [OK]

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

Common Mistakes:

• Starting i at low causes wrong partitioning
• Loop running to high causes out-of-bound swap
• Changing pivot position incorrectly

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

hard

A. Always choose the first element as pivot

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

C. Skip sorting subarrays with size less than 5

D. Use Bubble Sort instead for duplicates

Solution

1. Step 1: Understand problem with duplicates

   Standard Quick Sort performs poorly with many duplicates due to repeated swaps.

2. Step 2: Apply three-way partitioning

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

3. Final Answer:

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

4. Quick Check:

   Three-way partitioning improves duplicates handling [OK]

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

Common Mistakes:

• Choosing fixed pivot without considering duplicates
• Ignoring small subarrays optimization
• Switching to slower sorts unnecessarily