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 on this array?

Initial array: [8, 3, 7, 6, 2]
Pivot: last element (2)

DSA C

int arr[] = {8, 3, 7, 6, 2};
int pivot = arr[4];
int i = -1;
for (int j = 0; j < 4; j++) {
    if (arr[j] < pivot) {
        i++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
i++;
int temp = arr[i];
arr[i] = arr[4];
arr[4] = temp;
// Print arr

A [3, 2, 7, 6, 8]

B [2, 3, 7, 6, 8]

C [8, 3, 7, 6, 2]

D [2, 3, 6, 7, 8]

💡 Hint

Remember, elements less than pivot move to the left, pivot placed after them.

The partition moves elements smaller than 2 to the left. Since only 2 is smallest, it swaps with first element. Result: [2, 3, 7, 6, 8].

❓ Predict Output

intermediate

Final Sorted Array by Quick Sort

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

Input array: [4, 1, 9, 7, 3]

DSA C

int arr[] = {4, 1, 9, 7, 3};
// Quick sort applied fully
// Print arr

A [1, 3, 4, 7, 9]

B [1, 4, 3, 7, 9]

C [4, 1, 3, 7, 9]

D [9, 7, 4, 3, 1]

💡 Hint

Quick Sort sorts in ascending order.

Quick Sort sorts the array fully in ascending order: [1, 3, 4, 7, 9].

🔧 Debug

advanced

Identify the Error in Quick Sort Partition Code

What error will this Quick Sort partition code cause when run?

Code snippet:
int partition(int arr[], int low, int high) { 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]; arr[i] = arr[high]; arr[high] = temp; return i; }

DSA C

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

A Swaps pivot with wrong element causing incorrect partition

B Returns wrong pivot index causing infinite recursion

C Array index out of bounds error

D No error, works correctly

💡 Hint

Check the swap of pivot with arr[i].

The pivot swap uses arr[i], but i points to last smaller element, pivot should swap with arr[i+1]. This 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 randomly shuffled array

B An array with all elements equal

C An already sorted array in ascending order

D An array sorted in descending order

💡 Hint

Worst case happens when pivot divides array unevenly.

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

🚀 Application

expert

Number of Recursive Calls in Quick Sort

Given the array [5, 3, 8, 4, 2] sorted by Quick Sort using last element as pivot, how many total recursive calls (including the initial call) are made?

A 5

B 7

C 11

D 9

💡 Hint

Count calls for each partition step carefully.

The partitioning splits the array into subarrays recursively. Counting all calls including base cases gives 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 [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
• 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. int partition(int arr[], int low, int high);

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

D. int partition(int arr[], int start, int end, int pivot);

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: Confirm return type

   It returns an integer index of the pivot after partitioning.

3. Final Answer:

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

4. Quick Check:

   Partition returns pivot index [OK]

Hint: Partition returns pivot index; use array and low, high indices [OK]

Common Mistakes:

• Using void return type for partition
• Passing array as int instead of int[]
• Adding extra parameters like pivot

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

medium

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

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

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

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

Solution

1. Step 1: Apply Quick Sort logic on the array

   Quick Sort rearranges elements around pivots recursively, sorting the array in ascending order.

2. Step 2: Sort the given array

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

3. Final Answer:

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

4. Quick Check:

   Sorted array ascending = [1,1,2,3,6,8,10] [OK]

Hint: Quick Sort outputs sorted array ascending by default [OK]

Common Mistakes:

• Assuming Quick Sort keeps original order
• Confusing ascending with descending order
• Not sorting duplicates correctly

4. Identify the error in this Quick Sort partition function 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. Variable i should start at low - 1, not low

B. Pivot should be arr[low], not arr[high]

C. Loop should run till j <= high, not j < high

D. Swap function is called with wrong arguments

Solution

1. Step 1: Check initialization of i

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

2. Step 2: Analyze loop and swaps

   Starting i at low causes skipping the first element comparison and wrong swaps.

3. Final Answer:

   Variable i should start at low - 1, not low -> Option A

4. Quick Check:

   i = low - 1 fixes partition indexing [OK]

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

Common Mistakes:

• Starting i at low causes incorrect partitioning
• Changing pivot position unnecessarily
• Extending loop beyond high index

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

hard

A. Use Bubble Sort instead for duplicates

B. Always choose the first element as pivot

C. Skip sorting duplicates by checking equality before partition

D. Use 3-way partitioning to separate less than, equal to, and greater than pivot

Solution

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

   Standard Quick Sort can degrade with many duplicates due to repeated swaps and partitions.

2. Step 2: Apply 3-way partitioning

   3-way partitioning divides array into three parts: less than, equal to, and greater than pivot, reducing unnecessary work.

3. Final Answer:

   Use 3-way partitioning to separate less than, equal to, and greater than pivot -> Option D

4. Quick Check:

   3-way partitioning optimizes duplicates [OK]

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

Common Mistakes:

• Choosing fixed pivot without randomization
• Skipping duplicates without partitioning
• Switching to slower sorts unnecessarily