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 the array [4, 7, 2, 9, 1]?

DSA C#

int[] arr = {4, 7, 2, 9, 1};
int pivot = arr[arr.Length - 1];
int i = -1;
for (int j = 0; j < arr.Length - 1; j++)
{
    if (arr[j] < pivot)
    {
        i++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
i++;
int tempPivot = arr[i];
arr[i] = arr[arr.Length - 1];
arr[arr.Length - 1] = tempPivot;
Console.WriteLine(string.Join(", ", arr));

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

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

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

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

💡 Hint

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

The partition step moves all elements smaller than the pivot (1) to the left. After swapping, the array becomes [1, 7, 2, 9, 4].

❓ Predict Output

intermediate

Final Sorted Array After Quick Sort

What is the final sorted array after applying Quick Sort on [3, 6, 8, 10, 1, 2, 1]?

DSA C#

int[] arr = {3, 6, 8, 10, 1, 2, 1};
QuickSort(arr, 0, arr.Length - 1);
Console.WriteLine(string.Join(", ", arr));

void QuickSort(int[] array, int low, int high)
{
    if (low < high)
    {
        int pi = Partition(array, low, high);
        QuickSort(array, low, pi - 1);
        QuickSort(array, pi + 1, high);
    }
}

int Partition(int[] array, int low, int high)
{
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (array[j] <= pivot)
        {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp1 = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp1;
    return i + 1;
}

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

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

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

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

💡 Hint

Quick Sort sorts the array in ascending order.

The Quick Sort algorithm sorts the array in ascending order. The final sorted array is [1, 1, 2, 3, 6, 8, 10].

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition Function

What error will the following Quick Sort partition function cause when run on any array?

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 (i <= j && 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;
}

A Correct partition with no error

B Infinite loop because i and j pointers never cross

C IndexOutOfRangeException due to i or j going out of bounds

D StackOverflowException due to recursion depth

💡 Hint

Check the inner while loops and their boundary conditions.

The inner while loops can increment i or decrement j beyond array bounds if conditions are not carefully checked, causing IndexOutOfRangeException.

🧠 Conceptual

advanced

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 log n), when pivot divides array into two equal halves

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

C O(n), when array is already sorted

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

💡 Hint

Worst case happens when partitioning is unbalanced.

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

🚀 Application

expert

Quick Sort Stability Check

Given the array of objects [{value: 4, id: 'a'}, {value: 4, id: 'b'}, {value: 3, id: 'c'}], which statement about Quick Sort stability is true?

A Quick Sort is unstable; the relative order of equal elements may change

B Quick Sort is stable; the relative order of equal elements is preserved

C Quick Sort is stable only if implemented with extra memory

D Quick Sort is unstable only when pivot is chosen as first element

💡 Hint

Think about how swapping equal elements affects order.

Quick Sort is generally unstable because swapping can change the relative order of equal elements.

Practice

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

easy

A. Insert elements one by one into a sorted list

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

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

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's partitioning

   Quick Sort picks a pivot and divides the array into parts smaller and larger than the pivot.

2. Step 2: Apply recursive sorting

   It then sorts these parts recursively to get the full sorted array.

3. Final Answer:

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

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
• Ignoring the pivot concept

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

easy

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

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

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

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

Solution

1. Step 1: Understand partition function return type

   The partition function returns the pivot index as an integer after rearranging elements.

2. Step 2: Check C# syntax for arrays and access modifiers

   In C#, arrays are declared as int[] arr and public methods specify return type before method name.

3. Final Answer:

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

4. Quick Check:

   Partition returns int index [OK]

Hint: Partition returns pivot index, so return type must be int [OK]

Common Mistakes:

• Using void instead of int as return type
• Incorrect array syntax like int arr[] in C#
• Missing access modifier or wrong order

3. What will be the output array after one partition call on arr = [8, 3, 7, 6, 2] with pivot as last element (2)?

medium

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

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

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

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

Solution

1. Step 1: Choose pivot and start partitioning

   Pivot is 2 (last element). Elements less than 2 go left, others right.

2. Step 2: Rearrange elements around pivot

   Only 2 is less or equal to pivot, so it swaps with first element 8. Result: [2, 3, 7, 6, 8]

3. Final Answer:

   [2, 3, 7, 6, 8] -> Option B

4. Quick Check:

   Pivot 2 placed at start [OK]

Hint: Pivot last element; smaller elements move left [OK]

Common Mistakes:

• Not swapping pivot correctly
• Assuming full sort after one partition
• Mixing 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, j);
      i++;
    }
  }
  Swap(arr, i, high);
  return i;
}

medium

A. The loop should use <= high instead of < high

B. The comparison should be <= pivot instead of < pivot

C. Swap should be called outside the loop only once

D. The initial value of i should be low - 1

Solution

1. Step 1: Understand partition index initialization

   Variable i tracks the position for swapping smaller elements. It should start at low - 1 to correctly place elements.

2. Step 2: Check loop and swap logic

   Loop runs from low to high-1, swapping when arr[j] < pivot. Starting i at low causes incorrect swaps.

3. Final Answer:

   The initial value of i should be low - 1 -> Option D

4. Quick Check:

   i starts at low-1 for correct partition [OK]

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

Common Mistakes:

• Starting i at low causes wrong swaps
• Changing loop bounds incorrectly
• Using wrong comparison operator

5. Given the array [10, 7, 8, 9, 1, 5], what is the array state after the first full Quick Sort partition step choosing the last element as pivot?

hard

A. [1, 5, 8, 9, 7, 10]

B. [1, 5, 7, 8, 9, 10]

C. [1, 7, 8, 9, 10, 5]

D. [1, 5, 8, 9, 10, 7]

Solution

1. Step 1: Identify pivot and partition process

   Pivot is 5 (last element). Elements less than 5 move left, others right.

2. Step 2: Rearrange elements around pivot

   Elements less than 5 are 1 only (index 4). Swap it with index 0: [1, 7, 8, 9, 10, 5]. Then swap index 1 (7) with high (5): [1, 5, 8, 9, 7, 10].

3. Final Answer:

   [1, 5, 8, 9, 7, 10] -> Option A

4. Quick Check:

   Pivot 5 placed correctly after smaller elements [OK]

Hint: Pivot last; smaller left, pivot placed next [OK]

Common Mistakes:

• Assuming full sort after one partition
• Swapping elements incorrectly
• Misplacing pivot index