Quick Sort as Divide and Conquer in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output array after the partition step in this quick sort code snippet?

DSA Javascript

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

let array = [8, 3, 7, 6, 2];
let pivotIndex = partition(array, 0, array.length - 1);
console.log(array);

A [2, 3, 6, 7, 8]

B [2, 3, 7, 6, 8]

C [3, 7, 6, 2, 8]

D [3, 2, 7, 6, 8]

💡 Hint

Focus on how elements less than the pivot are moved to the left side.

The partition function moves all elements smaller than the pivot (8) to the left. Here, 3 and 2 are less than 8 and get swapped to the front. The pivot 8 is placed after these smaller elements, resulting in [3, 2, 7, 6, 8].

❓ Predict Output

intermediate

Final Sorted Array from Quick Sort

What is the output of the following quick sort implementation on the array [4, 1, 5, 2]?

DSA Javascript

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    let pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

console.log(quickSort([4, 1, 5, 2]));

A [4, 1, 2, 5]

B [1, 4, 2, 5]

C [1, 2, 4, 5]

D [2, 1, 4, 5]

💡 Hint

Quick sort sorts the array in ascending order.

The quick sort algorithm recursively partitions and sorts the array. The final sorted array is [1, 2, 4, 5].

🧠 Conceptual

advanced

Understanding Quick Sort Pivot Choice Impact

Which statement best explains how the choice of pivot affects quick sort's performance?

A Pivot choice does not affect quick sort performance because all partitions are equal.

B Choosing a pivot near the median value helps quick sort run faster by balancing partitions.

C Choosing the smallest or largest element as pivot always results in the fastest sorting.

D Choosing a random pivot always causes quick sort to run in worst-case time.

💡 Hint

Think about how balanced partitions affect recursion depth.

Choosing a pivot near the median splits the array into roughly equal parts, reducing recursion depth and improving performance.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition

What error will this quick sort partition code cause when run on array [3, 6, 2]?

DSA Javascript

function partition(arr, low, high) {
  let pivot = arr[low];
  let i = low + 1;
  for (let j = low + 1; j <= high; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[low], arr[i - 1]] = [arr[i - 1], arr[low]];
  return i - 1;
}

let arr = [3, 6, 2];
let p = partition(arr, 0, arr.length - 1);
console.log(arr);

A Array after partition: [2, 6, 3]

B TypeError: Cannot read property 'length' of undefined

C Array after partition: [2, 3, 6]

D RangeError: Index out of bounds

💡 Hint

Check the swap of pivot with arr[i] at the end.

The pivot swap uses arr[i], but i can be equal to high + 1, causing the pivot to swap with an element outside the partition range, leading to incorrect partitioning.

🚀 Application

expert

Quick Sort Recursive Call Count

Given an array of 7 unique elements, what is the minimum number of recursive calls quick sort will make to fully sort the array if the pivot always splits the array into two equal halves?

A 13

B 31

C 7

D 15

💡 Hint

Think about the recursion tree height and total calls in a balanced binary recursion.

With perfect splits, quick sort forms a balanced binary recursion tree. For 7 elements, the recursion tree has 3 levels (ceil of log2(7)). Total calls = 2 * n - 1 = 13.

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