Quick Sort as Divide and Conquer in DSA C#

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, and then combines them to get a sorted list.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then sorting each side the same way until all cards are in order.

Array: [7, 2, 9, 4, 3]
Pivot chosen: 7
Partition: [2, 4, 3] -> 7 -> [9]

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot 7, partition array into elements less than 7 and greater than or equal to 7

[2, 4, 3] -> 7 -> [9]

Why: We separate smaller and larger elements around pivot to sort parts independently

Step 2: Recursively apply Quick Sort on left part [2, 4, 3]

Pivot 3 chosen, partition into [2] -> 3 -> [4]

Why: Sort left side by choosing new pivot and partitioning

Step 3: Recursively apply Quick Sort on right part [4]

[4]

Why: Single element is already sorted

Step 4: Combine sorted parts: [2] -> 3 -> [4] -> 7 -> [9]

[2, 3, 4, 7, 9]

Why: Merging sorted parts gives fully sorted array

Result:

Sorted array: [2, 3, 4, 7, 9]

Annotated Code

DSA C#

using System;

class QuickSortExample
{
    // Function to perform Quick Sort on array between low and high indices
    static void QuickSort(int[] arr, int low, int high)
    {
        if (low < high)
        {
            // Partition the array and get pivot index
            int pivotIndex = Partition(arr, low, high);

            // Recursively sort elements before pivot
            QuickSort(arr, low, pivotIndex - 1);

            // Recursively sort elements after pivot
            QuickSort(arr, pivotIndex + 1, high);
        }
    }

    // Partition function to place pivot correctly and partition array
    static int Partition(int[] arr, int low, int high)
    {
        int pivot = arr[high]; // Choose last element as pivot
        int i = low - 1; // Index of smaller element

        for (int j = low; j < high; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Place pivot after smaller elements
        int temp1 = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp1;

        return i + 1; // Return pivot index
    }

    static void Main()
    {
        int[] arr = {7, 2, 9, 4, 3};
        QuickSort(arr, 0, arr.Length - 1);

        // Print sorted array
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);
            if (i < arr.Length - 1) Console.Write(", ");
        }
        Console.WriteLine();
    }
}

if (low < high)

Check if current sub-array has more than one element to sort

int pivotIndex = Partition(arr, low, high);

Partition array and get pivot position

QuickSort(arr, low, pivotIndex - 1);

Recursively sort left sub-array before pivot

QuickSort(arr, pivotIndex + 1, high);

Recursively sort right sub-array after pivot

int pivot = arr[high];

Choose last element as pivot for partitioning

if (arr[j] < pivot)

Compare current element with pivot to decide placement

Swap arr[i] and arr[j]

Move smaller elements to left side

Swap arr[i + 1] and arr[high]

Place pivot in correct sorted position

Output

2, 3, 4, 7, 9

Complexity Analysis

Time: O(n log n) average case because the array is divided into halves recursively and each element is compared once per level

Space: O(log n) due to recursive call stack in average case

vs Alternative: Compared to Bubble Sort's O(n^2), Quick Sort is much faster on average due to divide and conquer splitting

Edge Cases

Empty array

Function returns immediately without changes

DSA C#

if (low < high)

Array with one element

No sorting needed, function returns immediately

DSA C#

if (low < high)

Array with all elements equal

Partitioning still works but no swaps needed, array remains same

DSA C#

if (arr[j] < pivot)

When to Use This Pattern

When you need to sort a list efficiently by breaking it into smaller parts and sorting each part, use Quick Sort because it uses divide and conquer to reduce sorting time.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping elements properly during partition
Fix: Always pick a pivot (commonly last element) and swap smaller elements before pivot correctly

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting sub-arrays recursively.

Use Quick Sort when you want an efficient, average O(n log n) sorting algorithm.

The key insight is dividing the problem into smaller parts around a pivot to sort independently.

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