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 completes in this Quick Sort code snippet?

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 temp1 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp1;
    return i + 1;
}

int[] array = {9, 3, 7, 6, 2, 8, 5};
int pivotIndex = Partition(array, 0, array.Length - 1);
Console.WriteLine(string.Join(", ", array));

A 2, 3, 5, 6, 7, 8, 9

B 2, 3, 5, 6, 9, 8, 7

C 3, 2, 5, 6, 9, 8, 7

D 3, 2, 5, 6, 7, 8, 9

💡 Hint

Remember the pivot is the last element and elements less than pivot move to the left.

The partition function moves all elements smaller than the pivot (5) to the left. The pivot ends up at index 4. The array after partition is [3, 2, 1, 5, 6, 8, 9].

🧠 Conceptual

intermediate

Understanding Quick Sort Recursive Calls

After the first partition call on the array [4, 1, 3, 9, 7], which subarrays will Quick Sort recursively sort next?

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

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

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

D [1, 3] and [7]

💡 Hint

Look at where the pivot ends after partition and which parts are left and right.

After partition, the pivot is placed correctly. Quick Sort then sorts elements left of pivot and right of pivot separately. Here, those are [1, 3] and [7].

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition

What error will this Quick Sort partition code cause when run on array [5, 2, 9, 1]?

DSA C#

int Partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;
    while (true) {
        while (i <= j && arr[i] <= pivot) i++;
        while (j >= i && arr[j] > pivot) j--;
        if (i >= j) break;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    int temp2 = arr[low];
    arr[low] = arr[j];
    arr[j] = temp2;
    return j;
}

int[] array = {5, 2, 9, 1};
int p = Partition(array, 0, array.Length - 1);
Console.WriteLine(string.Join(", ", array));

A Infinite loop

B NullReferenceException

C IndexOutOfRangeException

D Correct partition with output: 2, 1, 5, 9

💡 Hint

Check the conditions in the inner while loops and how i and j move.

The inner loops can cause i to move beyond array bounds or get stuck if conditions are not properly checked, causing an infinite loop.

❓ Predict Output

advanced

Final Sorted Array After Quick Sort

What is the final sorted array after running Quick Sort on [10, 7, 8, 9, 1, 5] using Lomuto partition scheme?

DSA C#

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);
    }
}

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 temp1 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp1;
    return i + 1;
}

int[] array = {10, 7, 8, 9, 1, 5};
QuickSort(array, 0, array.Length - 1);
Console.WriteLine(string.Join(", ", array));

A 1, 5, 7, 8, 9, 10

B 1, 5, 7, 8, 10, 9

C 5, 1, 7, 8, 9, 10

D 10, 9, 8, 7, 5, 1

💡 Hint

Quick Sort sorts the array in ascending order using partitioning.

Quick Sort with Lomuto partition sorts the array fully in ascending order: [1, 5, 7, 8, 9, 10].

🧠 Conceptual

expert

Time Complexity of Quick Sort in Worst Case

What is the worst-case time complexity of Quick Sort and when does it occur?

A O(n), when array is already sorted

B O(n log n), when pivot divides array into two equal halves

C O(n^2), when pivot is always the smallest or largest element

D O(log n), when pivot is chosen randomly

💡 Hint

Think about how unbalanced partitions affect recursive calls.

The worst case happens when the pivot is the smallest or largest element every time, causing unbalanced partitions and O(n^2) time.

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

easy

A. Use extra memory to merge two sorted arrays

B. Sort the array by repeatedly swapping adjacent elements

C. Divide the array into smaller parts, sort them, and combine results

D. Sort elements by counting their frequency

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort divides the array into smaller parts using a pivot, then sorts each part separately.

2. Step 2: Compare with other sorting methods

   Unlike bubble sort or counting sort, Quick Sort uses division and conquering subproblems.

3. Final Answer:

   Divide the array into smaller parts, sort them, and combine results -> Option C

4. Quick Check:

   Divide and conquer = splitting and sorting parts [OK]

Hint: Remember: Quick Sort splits and sorts parts separately [OK]

Common Mistakes:

• Confusing Quick Sort with bubble sort
• Thinking Quick Sort uses extra memory like merge sort
• Believing Quick Sort counts frequencies

2. Which of the following is the correct way to declare the partition method header in C# for Quick Sort?

easy

A. public static int Partition(int[] arr, int low, int high)

B. void Partition(int arr[], int low, int high)

C. int Partition(int[] arr, int low, int high, int pivot)

D. public int Partition(int arr, int low, int high)

Solution

1. Step 1: Check C# method declaration syntax

   In C#, arrays are declared as int[] arr, and method must specify return type and access modifier.

2. Step 2: Validate parameters and return type

   Partition returns an integer index, so return type is int. Parameters include array and two indices.

3. Final Answer:

   public static int Partition(int[] arr, int low, int high) -> Option A

4. Quick Check:

   C# method syntax with array and return int = public static int Partition(int[] arr, int low, int high) [OK]

Hint: Remember C# arrays use [] after type, method needs return type [OK]

Common Mistakes:

• Using C-style array syntax like int arr[]
• Missing return type or access modifier
• Passing pivot as parameter unnecessarily

3. What will be the output array after applying Quick Sort on int[] arr = {4, 2, 7, 1}?

medium

A. [1, 2, 4, 7]

B. [7, 4, 2, 1]

C. [2, 1, 4, 7]

D. [4, 7, 2, 1]

Solution

1. Step 1: Apply Quick Sort partition and recursive calls

   Pivot chosen (commonly last element 1), partition places 1 at start, then sort left and right parts recursively.

2. Step 2: Sort remaining parts

   After partitioning and recursive sorting, array becomes sorted ascending: 1, 2, 4, 7.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing pivot placement
• Not sorting both sides recursively
• Assuming output is reversed

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. The initial value of i should be low - 1

B. Swap method is called with values, not indices

C. The loop should run until j <= high

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

Solution

1. Step 1: Analyze Swap usage in C#

   Swap is called with arr[i] and arr[j], which passes values, not array indices, so original array won't change.

2. Step 2: Correct Swap call

   Swap should be called with indices or use a method that swaps elements in the array by index.

3. Final Answer:

   Swap method is called with values, not indices -> Option B

4. Quick Check:

   Swap needs indices or ref to swap array elements [OK]

Hint: Swap array elements by indices, not by passing values [OK]

Common Mistakes:

• Using wrong loop range
• Incorrect pivot choice
• Initializing i incorrectly

5. Given an array int[] arr = {3, 6, 8, 10, 1, 2, 1}, how many recursive calls will Quick Sort make to fully sort this array using the last element as pivot each time?

hard

A. 7

B. 15

C. 13

D. 9

Solution

1. Step 1: Understand recursive calls in Quick Sort

   Each partition divides array into two parts; recursive calls happen on both sides unless base case reached.

2. Step 2: Trace recursive calls for given array

   Initial call on 7 elements, partitions and recurses on subarrays. Counting calls: initial + left + right calls totals 9.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Counting recursive calls carefully = 9 [OK]

Hint: Count initial call plus calls on subarrays after partition [OK]

Common Mistakes:

• Counting only partition steps, not recursive calls
• Assuming calls equal array length
• Ignoring base case stops