Quick Sort Algorithm in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Quick Sort algorithm?

Quick Sort works by picking a 'pivot' element and rearranging the array so that elements smaller than the pivot come before it, and elements larger come after. Then it sorts the smaller and larger parts separately.

beginner

What role does the 'pivot' play in Quick Sort?

The pivot divides the array into two parts: elements less than the pivot and elements greater than or equal to the pivot. This helps to sort the array by focusing on smaller parts.

intermediate

Explain the partition step in Quick Sort.

Partition rearranges the array so that all elements less than the pivot are on the left, and all greater or equal are on the right. The pivot ends up in its correct sorted position.

intermediate

What is the average time complexity of Quick Sort?

The average time complexity of Quick Sort is O(n log n), where n is the number of elements to sort.

beginner

Why can Quick Sort be faster than other sorting algorithms like Bubble Sort?

Quick Sort divides the problem into smaller parts and sorts them quickly using the pivot, reducing the number of comparisons compared to Bubble Sort, which compares every pair repeatedly.

What does Quick Sort use to divide the array?

A A stack

B A temporary array

C A queue

D A pivot element

Quick Sort uses a pivot element to divide the array into parts smaller and larger than the pivot.

What is the worst-case time complexity of Quick Sort?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

In the worst case, Quick Sort can degrade to O(n^2), for example when the smallest or largest element is always chosen as pivot.

Which step places the pivot in its correct sorted position?

A Merge

B Swap

C Partition

D Recursion

The partition step rearranges elements and places the pivot in its correct position.

Quick Sort is an example of which algorithm design technique?

A Divide and Conquer

B Brute Force

C Greedy

D Dynamic Programming

Quick Sort uses divide and conquer by splitting the array and sorting parts separately.

Which of these is NOT true about Quick Sort?

A It sorts in place without extra arrays

B It always runs in O(n log n) time

C It uses recursion

D It selects a pivot element

Quick Sort does not always run in O(n log n); its worst case is O(n^2).

Describe how Quick Sort sorts an array step-by-step.

Think about how the array is split and sorted smaller parts.

Explain why Quick Sort is efficient on average but can be slow in the worst case.

Consider how the pivot affects the size of parts.

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