Quick Sort Algorithm in DSA C# - Time & Space Complexity

Time Complexity: Quick Sort Algorithm

O(n log n)

Understanding Time Complexity

We want to understand how the time to sort a list using Quick Sort changes as the list gets bigger.

Specifically, how many steps does Quick Sort take when sorting more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code sorts an array by picking a pivot, dividing the array around it, and sorting the parts recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop inside Partition that compares and swaps elements.
• How many times: This loop runs for the current sub-array size, and QuickSort calls itself recursively on smaller parts.

How Execution Grows With Input

When the array is split evenly, each step divides the problem in half, doing work proportional to the size of the current part.

Input Size (n)	Approx. Operations
10	About 50 to 60 comparisons and swaps
100	About 700 to 800 operations
1000	About 10,000 operations

Pattern observation: The operations grow faster than just doubling but slower than squaring the input size.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort grows a bit more than linearly, multiplying the input size by the number of times it can be halved.

Common Mistake

[X] Wrong: "Quick Sort always sorts in linear time because it just splits the array."

[OK] Correct: Splitting helps, but the work inside each split depends on the size of the parts, so it takes more than just linear time.

Interview Connect

Understanding Quick Sort's time complexity helps you explain why it is fast on average and what happens in worst cases, showing your grasp of efficient sorting.

Self-Check

"What if we always picked the first element as pivot instead of the last? How would the time complexity change?"

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