Quick Sort Algorithm in DSA C#

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

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

Array: [7, 2, 9, 4, 3]
Pivot chosen: 4
Partitioned: [2, 3] -> [4] -> [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 3 (last element), partition array around pivot

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

Why: Pivot divides array into smaller and larger elements

Step 2: Recursively quick sort left part [2]

[2]

Why: Single element is already sorted

Step 3: Recursively quick sort right part [7, 9, 4], choose pivot 4

[4] -> [7, 9]

Why: Partition right part around pivot 4

Step 4: Recursively quick sort left part [] (empty)

[]

Why: Empty part needs no sorting

Step 5: Recursively quick sort right part [7, 9], choose pivot 9

[7] -> [9]

Why: Partition right part around pivot 9

Step 6: Recursively quick sort left part [7]

[7]

Why: Single element is sorted

Step 7: Recursively quick sort right part [] (empty)

[]

Why: Empty part needs no sorting

Result:

[2, 3, 4, 7, 9]

Annotated Code

DSA C#

using System;

class QuickSort {
    // Function to swap two elements in array
    static void Swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Partition function to place pivot correctly
    static int Partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // pivot is last element
        int i = low - 1; // index of smaller element

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                Swap(arr, i, j); // move smaller element to left
            }
        }
        Swap(arr, i + 1, high); // place pivot after smaller elements
        return i + 1; // return pivot index
    }

    // QuickSort recursive function
    static void QuickSortRecursive(int[] arr, int low, int high) {
        if (low < high) {
            int pi = Partition(arr, low, high); // partition array

            QuickSortRecursive(arr, low, pi - 1); // sort left part
            QuickSortRecursive(arr, pi + 1, high); // sort right part
        }
    }

    // Driver function
    static void Main() {
        int[] arr = {7, 2, 9, 4, 3};
        QuickSortRecursive(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();
    }
}

int pivot = arr[high]; // pivot is last element

select pivot to divide array

for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; Swap(arr, i, j); } }

move elements smaller or equal to pivot to left side

Swap(arr, i + 1, high); return i + 1;

place pivot in correct position and return its index

if (low < high) { int pi = Partition(arr, low, high); QuickSortRecursive(arr, low, pi - 1); QuickSortRecursive(arr, pi + 1, high); }

recursively sort left and right parts around pivot

Output

2, 3, 4, 7, 9

Complexity Analysis

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

Space: O(log n) due to recursive call stack depth 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 approach

Edge Cases

empty array

function returns immediately without changes

DSA C#

if (low < high) {

array with one element

function returns immediately as low is not less than high

DSA C#

if (low < high) {

array with all elements equal

partitioning still works, but recursion depth remains balanced

DSA C#

if (arr[j] <= pivot) {

When to Use This Pattern

When you need to sort an array efficiently and can use divide and conquer, Quick Sort is a go-to pattern because it splits the problem into smaller parts around a pivot.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping elements properly during partition
Fix: Always pick pivot as last element and swap elements smaller than pivot to left side before placing pivot

Mistake: Not checking base case low < high before recursion
Fix: Add condition if (low < high) to stop recursion on small or empty parts

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting each part recursively.

Use Quick Sort when you want an efficient average-case sorting algorithm for arrays.

The key insight is dividing the array into smaller parts around a pivot to sort faster.

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