Quick Sort as Divide and Conquer in DSA Javascript - 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. 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 each part, and merges 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.

advanced

Why is Quick Sort considered efficient despite its worst-case time complexity?

Quick Sort is efficient because its average case is fast, and with good pivot choices, the worst case is rare. It also sorts in place, using little extra memory.

What does Quick Sort use to split the array?

A The first element only

B The largest element

C A pivot element

D The middle element always

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

Which of these best describes the 'divide and conquer' method in Quick Sort?

A Sorting the whole list at once

B Breaking the list into smaller parts, sorting them, then combining

C Using extra memory to copy the list

D Sorting only the first half of the list

Divide and conquer means breaking the problem into smaller parts, sorting each, then combining.

What is the average time complexity of Quick Sort?

A O(n log n)

B O(n^2)

C O(log n)

D O(n)

Quick Sort has an average time complexity of O(n log n), making it efficient for most cases.

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

A They go to the right side

B They stay in place

C They are removed

D They go to the left side

Elements smaller than the pivot are moved to the left side of the pivot.

Why is Quick Sort often preferred over other sorting algorithms?

A It sorts in place and is fast on average

B It is simple but slow

C It never uses recursion

D It always uses extra memory

Quick Sort sorts in place (uses little extra memory) and is fast on average, making it popular.

Describe how Quick Sort uses the divide and conquer approach to sort an array.

Think about how the array is split and sorted step by step.

Explain why the choice of pivot affects Quick Sort's performance.

Consider what happens if the pivot is always the smallest or largest element.

Practice

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

easy

A. Divide the array into smaller parts, sort them, and combine the results

B. Sort the array by repeatedly swapping adjacent elements

C. Use extra space to merge two sorted arrays

D. Sort the array by selecting the smallest element each time

Solution

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

   Quick Sort divides the array into parts based on a pivot, sorts each part recursively.

2. Step 2: Compare with other sorting methods

   Unlike bubble or selection sort, Quick Sort uses division and recursion, not just swapping or selecting smallest.

3. Final Answer:

   Divide the array into smaller parts, sort them, and combine the results -> Option A

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: divide, sort parts, then combine [OK]

Common Mistakes:

• Confusing Quick Sort with bubble or selection sort
• Thinking Quick Sort merges arrays like merge sort
• Ignoring the pivot selection step

2. Which of the following is the correct syntax to choose a pivot element in a Quick Sort function in JavaScript?

easy

A. const pivot = arr.push();

B. const pivot = arr.length;

C. const pivot = arr.sort();

D. const pivot = arr[0];

Solution

1. Step 1: Identify how to select pivot in Quick Sort

   The pivot is usually an element from the array, often the first or last element.

2. Step 2: Check each option's correctness

   const pivot = arr[0]; selects the first element as pivot correctly. Others use wrong methods or properties.

3. Final Answer:

   const pivot = arr[0]; -> Option D

4. Quick Check:

   Pivot selection = arr[0] [OK]

Hint: Pivot is an element, not array length or method result [OK]

Common Mistakes:

• Using array length as pivot
• Calling array methods instead of accessing element
• Confusing pivot with sorted array

3. What will be the output of the following JavaScript Quick Sort partition step?

const arr = [4, 2, 7, 1];
const pivot = arr[0]; // 4
let left = [];
let right = [];
for(let i = 1; i < arr.length; i++) {
  if(arr[i] <= pivot) left.push(arr[i]);
  else right.push(arr[i]);
}
console.log(left);
console.log(right);

medium

A. [4, 2] and [7, 1]

B. [7] and [2, 1]

C. [2, 1] and [7]

D. [1, 2, 4] and []

Solution

1. Step 1: Identify pivot and partition logic

   Pivot is 4. Elements less or equal to 4 go to left, others to right.

2. Step 2: Partition the array

   Elements: 2 <= 4 -> left, 7 > 4 -> right, 1 <= 4 -> left. So left = [2,1], right = [7].

3. Final Answer:

   [2, 1] and [7] -> Option C

4. Quick Check:

   Partition by pivot 4 = [2,1] left, [7] right [OK]

Hint: Compare each element to pivot, separate into left/right [OK]

Common Mistakes:

• Including pivot in left or right arrays
• Mixing up less than and greater than conditions
• Forgetting to start loop from index 1

4. Identify the error in this Quick Sort partition code snippet:

function partition(arr) {
  const pivot = arr[0];
  let left = [];
  let right = [];
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...left, pivot, ...right];
}

medium

A. Use arr[i] <= pivot in condition instead of <

B. Loop should start from 1 to avoid including pivot twice

C. Pivot should be last element, not first

D. Return statement should not use spread operator

Solution

1. Step 1: Analyze loop range and pivot usage

   The loop starts at 0, so pivot element arr[0] is included in left or right arrays again.

2. Step 2: Correct loop start index

   Loop should start at 1 to skip pivot element and avoid duplication.

3. Final Answer:

   Loop should start from 1 to avoid including pivot twice -> Option B

4. Quick Check:

   Loop index = 1 to exclude pivot [OK]

Hint: Start loop after pivot index to avoid duplicates [OK]

Common Mistakes:

• Starting loop at 0 causing pivot duplication
• Changing pivot position unnecessarily
• Misunderstanding spread operator usage

5. Given the array [3, 6, 8, 10, 1, 2, 1], what is the correct sorted array after applying Quick Sort fully?

hard

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

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

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

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

Solution

1. Step 1: Understand Quick Sort fully sorts the array

   Quick Sort recursively partitions and sorts all parts until fully sorted.

2. Step 2: Sort the array manually

   Sorted array is [1, 1, 2, 3, 6, 8, 10], including duplicates in order.

3. Final Answer:

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

4. Quick Check:

   Quick Sort output = sorted array ascending [OK]

Hint: Quick Sort returns fully sorted array ascending [OK]

Common Mistakes:

• Ignoring duplicate elements
• Confusing sorted with original array
• Thinking Quick Sort reverses array