Quick Sort as Divide and Conquer 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, then dividing the list into two parts: elements less than the pivot and elements greater than or equal to the pivot. It then sorts these parts separately and combines them.

beginner

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

The pivot is the element used to split the list into two parts. Elements smaller than the pivot go to one side, and elements larger or equal go to the other side. This helps break the problem into smaller pieces.

intermediate

Explain the 'divide and conquer' approach in Quick Sort.

Divide and conquer means breaking a big problem into smaller problems, solving each smaller problem, and then combining the results. Quick Sort divides the list by pivot, sorts the parts, and combines them.

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. This means it sorts efficiently for most cases.

beginner

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

Quick Sort uses divide and conquer to reduce the problem size quickly, sorting parts independently. Bubble Sort compares and swaps elements repeatedly, which is slower for large lists.

In Quick Sort, what is the first step?

A Choose a pivot element

B Merge two sorted lists

C Swap all elements

D Count the number of elements

Quick Sort starts by choosing a pivot element to divide the list.

What happens to elements smaller than the pivot in Quick Sort?

A They are placed on the right side

B They are placed on the left side

C They are removed

D They are ignored

Elements smaller than the pivot are placed on the left side to be sorted separately.

Which of these best describes Quick Sort's approach?

A Divide and conquer

B Dynamic programming

C Greedy algorithm

D Brute force

Quick Sort uses divide and conquer by splitting and sorting parts independently.

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

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

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

After dividing the list by pivot, what does Quick Sort do next?

A Merges the parts immediately

B Stops sorting

C Deletes the pivot

D Sorts the two parts recursively

Quick Sort sorts the left and right parts recursively before combining them.

Describe how Quick Sort uses the divide and conquer method to sort a list.

Think about how the list is split and how smaller problems are solved.

Explain why Quick Sort is generally faster than simple sorting methods like Bubble Sort.

Focus on how Quick Sort handles the list compared to repeated swapping.

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

easy

A. Compare each element with every other element to sort

B. Divide the array into smaller parts using a pivot and sort them recursively

C. Merge two sorted arrays into one sorted array

D. Insert elements one by one into the correct position

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort picks a pivot 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 results to get a sorted array.

3. Final Answer:

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

4. Quick Check:

   Quick Sort = Divide and conquer with pivot [OK]

Hint: Remember pivot splits array for recursive sorting [OK]

Common Mistakes:

• Confusing Quick Sort with Merge Sort
• Thinking Quick Sort compares all pairs
• Believing 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. 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);

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

Solution

1. Step 1: Check parameter types for partition

   The partition function takes an array and two indices low and high to work on a subarray.

2. Step 2: Check return type

   It returns an integer index where the pivot ends after partitioning.

3. Final Answer:

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

4. Quick Check:

   Partition returns pivot index with array and bounds [OK]

Hint: Partition returns pivot index, needs array and bounds [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Missing one of the index parameters

3. What will be the output array after calling Quick Sort on arr = {3, 6, 8, 10, 1, 2, 1}?

medium

A. [1, 1, 2, 3, 6, 8, 10]

B. [3, 6, 8, 10, 1, 2, 1]

C. [10, 8, 6, 3, 2, 1, 1]

D. [1, 2, 1, 3, 6, 8, 10]

Solution

1. Step 1: Apply Quick Sort to the array

   Quick Sort rearranges elements so smaller come before pivot and larger after, recursively sorting subarrays.

2. Step 2: Sort the given array

   Sorting {3,6,8,10,1,2,1} results in {1,1,2,3,6,8,10} in ascending order.

3. Final Answer:

   [1, 1, 2, 3, 6, 8, 10] -> Option A

4. Quick Check:

   Sorted array = ascending order [OK]

Hint: Quick Sort outputs sorted array ascending [OK]

Common Mistakes:

• Assuming original array stays same
• Confusing ascending with descending order
• Misplacing duplicate elements

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

medium

A. For loop should run until j <= high

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

C. Swap should be called outside the loop only

D. Variable i should start at low - 1

Solution

1. Step 1: Check initialization of i

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

2. Step 2: Analyze loop and swaps

   Starting i at low causes incorrect swaps and wrong pivot placement.

3. Final Answer:

   Variable i should start at low - 1 -> Option D

4. Quick Check:

   i = low - 1 fixes partition indexing [OK]

Hint: Initialize i to low - 1 before loop [OK]

Common Mistakes:

• Starting i at low causes off-by-one errors
• Changing pivot position incorrectly
• Loop running beyond high index

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

hard

A. Avoid recursion and use iterative sorting only

B. Always pick the first element as pivot

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

D. Skip sorting duplicates to save time

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Duplicates cause many equal elements to be repeatedly partitioned, slowing sorting.

2. Step 2: Apply three-way partitioning

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

3. Final Answer:

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

4. Quick Check:

   Three-way partitioning optimizes duplicates [OK]

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

Common Mistakes:

• Picking fixed pivot causes worst-case time
• Skipping duplicates breaks sorting correctness
• Avoiding recursion does not fix duplicate issue