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 with Quick Sort changes as the list gets bigger.

How does the number of steps grow when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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++;
      std::swap(arr[i], arr[j]);
    }
  }
  std::swap(arr[i + 1], arr[high]);
  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

• Primary operation: The for-loop inside partition that compares and swaps elements.
• How many times: This loop runs once for each element in the current sub-array during each recursive call.
• Recursion: The function calls itself twice on smaller parts after partitioning.
• Dominant operation: The repeated partitioning and recursive calls dominate the time.

How Execution Grows With Input

When the list is split evenly, the number of operations grows a bit more than the size of the list times the number of splits.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons and swaps
100	About 700 to 800 comparisons and swaps
1000	About 10,000 to 12,000 comparisons and swaps

Pattern observation: The operations grow roughly like n times log n when splits are balanced.

Final Time Complexity

Time Complexity: O(n log n)

This means that as the list size doubles, the work grows a bit more than double, but much less than square.

Common Mistake

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

[OK] Correct: Splitting takes time, and the partition step compares many elements. Also, if splits are uneven, it can take longer.

Interview Connect

Understanding Quick Sort's time complexity helps you explain why it is fast on average and what can slow it down, a key skill in interviews.

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. Divide the array into smaller parts using a pivot and sort them recursively

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

C. Insert elements one by one into a sorted list

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's approach

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

2. Step 2: Recursive sorting of parts

   It then sorts these parts recursively, combining them to get the sorted array.

3. Final Answer:

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

4. Quick Check:

   Quick Sort = Divide and conquer using pivot [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
• Assuming Quick Sort inserts elements one by one

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

easy

A. void partition(int arr[], int low, int high);

B. int partition(int arr[], int high, int low);

C. int partition(int arr, int low, int high);

D. int partition(int arr[], int low, int high);

Solution

1. Step 1: Check parameter types and order

   The partition function takes an array and two indices: low and high, both integers.

2. Step 2: Check return type

   It returns an integer index where the pivot finally lies.

3. Final Answer:

   int partition(int arr[], int low, int high); -> Option D

4. Quick Check:

   Correct function signature = int partition(int arr[], int low, int high); [OK]

Hint: Partition returns pivot index; parameters are array and two ints [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Swapping low and high parameters

3. What will be the output array after applying Quick Sort on arr = {4, 2, 7, 1} using the last element as pivot?

medium

A. [1, 2, 4, 7]

B. [1, 4, 2, 7]

C. [2, 1, 4, 7]

D. [7, 4, 2, 1]

Solution

1. Step 1: Partition with pivot 1

   Pivot is 1 (last element). After partition, array becomes [1, 2, 7, 4] with pivot at index 0.

2. Step 2: Recursively sort subarrays

   Left subarray is empty; right subarray [2,7,4] is sorted recursively to [2,4,7]. Final array is [1,2,4,7].

3. Final Answer:

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

4. Quick Check:

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

Hint: Pivot last element; sort left and right recursively [OK]

Common Mistakes:

• Not placing pivot correctly after partition
• Sorting only once without recursion
• Confusing 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], arr[j]);
      i++;
    }
  }
  swap(arr[i], arr[high]);
  return i;
}

medium

A. Swap should be done only if arr[j] <= pivot

B. Loop should run from j = low to j <= high

C. Initialization of i should be low - 1

D. Pivot should be arr[low] instead of arr[high]

Solution

1. Step 1: Check initialization of i

   In partition, i should start at low - 1 to track smaller elements correctly.

2. Step 2: Analyze loop and swaps

   Loop runs j from low to high-1 correctly; swap with arr[i+1] after loop is correct.

3. Final Answer:

   Initialization of i should be low - 1 -> Option C

4. Quick Check:

   i starts at low - 1 in partition [OK]

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

Common Mistakes:

• Starting i at low causes wrong partitioning
• Loop running to high causes out-of-bound swap
• Changing pivot position incorrectly

5. Given an array with many duplicate elements, which modification to Quick Sort helps improve performance?

hard

A. Always choose the first element as pivot

B. Use a three-way partitioning to separate less, equal, and greater elements

C. Skip sorting subarrays with size less than 5

D. Use Bubble Sort instead for duplicates

Solution

1. Step 1: Understand problem with duplicates

   Standard Quick Sort performs poorly with many duplicates due to repeated swaps.

2. Step 2: Apply three-way partitioning

   Three-way partitioning divides array into less than, equal to, and greater than pivot, reducing unnecessary work.

3. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option B

4. Quick Check:

   Three-way partitioning improves duplicates handling [OK]

Hint: Three-way partitioning handles duplicates efficiently [OK]

Common Mistakes:

• Choosing fixed pivot without considering duplicates
• Ignoring small subarrays optimization
• Switching to slower sorts unnecessarily