Quick Sort Algorithm in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA C++

void swap(int& a, int& b) {
    int temp = a;
    a = [1];
    b = temp;
}

Drag options to blanks, or click blank then click option'

A0

Ba

Ctemp

Db

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning 'a' to itself instead of 'b'.

Using 'temp' incorrectly.

We assign 'a' the value of 'b' to swap their values correctly.

2fill in blank

medium

Complete the code to choose the pivot element for partitioning.

DSA C++

int partition(int arr[], int low, int high) {
    int pivot = arr[[1]];
    int i = low - 1;
    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;
}

Drag options to blanks, or click blank then click option'

Ahigh

Blow

Clow + 1

Dhigh - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing the wrong index for the pivot.

Using an index outside the array bounds.

The pivot is chosen as the last element at index 'high' for partitioning.

3fill in blank

hard

Fix the error in the recursive quickSort call to sort the left partition.

DSA C++

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

Drag options to blanks, or click blank then click option'

Api

Bpi - 1

Clow

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Including the pivot index in the left partition.

Using the wrong boundary for recursion.

The left partition ends at 'pi - 1' to exclude the pivot element.

4fill in blank

hard

Fill both blanks to complete the partition function's loop condition and swap call.

DSA C++

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

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' in the loop condition causing out-of-bound errors.

Using '>' instead of '<=' in the if condition.

The loop runs while j < high, and elements less than or equal to pivot are swapped.

5fill in blank

hard

Fill all three blanks to complete the quickSort function with correct recursive calls and base condition.

DSA C++

void quickSort(int arr[], int low, int high) {
    if (low [1] high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, [2]);
        quickSort(arr, [3], high);
    }
}

Drag options to blanks, or click blank then click option'

A<

Bpi - 1

Cpi + 1

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators in the base condition.

Including the pivot index in recursive calls.

The base condition is 'low < high', and recursive calls sort left and right partitions excluding the pivot.

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