Quick Sort as Divide and Conquer in DSA Javascript

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, then combines them to get a sorted list.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then sorting each side the same way until all cards are in order.

Unsorted array:
[ 8, 3, 7, 6, 2 ]

Pivot chosen (e.g., last element): 2
Partitioned:
[ 2 ] [ 3, 7, 6, 8 ]

Each part sorted recursively.

Dry Run Walkthrough

Input: array: [8, 3, 7, 6, 2]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element (2), partition array around pivot

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

Why: Pivot divides array into smaller and larger elements

Step 2: Recursively quick sort left part [ ] (empty) and right part [3, 7, 6, 8]

Left: [] (already sorted)
Right: [3, 7, 6, 8]

Why: Sort smaller parts separately

Step 3: Choose pivot 8 in right part, partition around 8

[3, 7, 6] [8]

Why: 8 is largest, so right part splits into smaller and pivot

Step 4: Recursively quick sort [3, 7, 6]

[3, 7, 6]

Why: Sort remaining unsorted part

Step 5: Choose pivot 6, partition [3, 7]

[3] [6] [7]

Why: 6 divides into smaller and larger elements

Step 6: Recursively quick sort [3] and [7] (both single elements, sorted)

[3] [6] [7]

Why: Single elements are sorted by definition

Step 7: Combine all parts: [2] + [3, 6, 7] + [8]

[2, 3, 6, 7, 8]

Why: Merging sorted parts gives fully sorted array

Result:

[2, 3, 6, 7, 8]

Annotated Code

DSA Javascript

class QuickSort {
  static partition(arr, low, high) {
    const 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]]; // swap smaller element to front
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // place pivot after smaller elements
    return i + 1;
  }

  static quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
      const pi = QuickSort.partition(arr, low, high); // partition index
      QuickSort.quickSort(arr, low, pi - 1); // sort left part
      QuickSort.quickSort(arr, pi + 1, high); // sort right part
    }
  }
}

const arr = [8, 3, 7, 6, 2];
QuickSort.quickSort(arr);
console.log(arr.join(", "));

const pivot = arr[high];

select pivot as last element in current subarray

if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }

move elements smaller or equal to pivot to front

[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];

place pivot after smaller elements

const pi = QuickSort.partition(arr, low, high);

partition array and get pivot index

QuickSort.quickSort(arr, low, pi - 1);

recursively sort left subarray

QuickSort.quickSort(arr, pi + 1, high);

recursively sort right subarray

Output

2, 3, 6, 7, 8

Complexity Analysis

Time: O(n log n) average case because the array is split roughly in half each time and each element is compared once per level

Space: O(log n) due to recursive call stack depth in average case

vs Alternative: Better than simple sorting like bubble sort O(n^2) because it divides the problem and conquers smaller parts efficiently

Edge Cases

empty array

function returns immediately without changes

DSA Javascript

if (low < high) {

array with one element

function returns immediately as array is already sorted

DSA Javascript

if (low < high) {

array with all equal elements

partitioning keeps elements in place, recursion ends quickly

DSA Javascript

if (arr[j] <= pivot) {

When to Use This Pattern

When you see a problem asking to sort or order elements efficiently, especially with divide and conquer hints, reach for Quick Sort because it splits and sorts parts recursively.

Common Mistakes

Mistake: Not swapping elements correctly during partition causing wrong order
Fix: Ensure swap happens only when element is smaller or equal to pivot and pivot is placed correctly after partition

Mistake: Forgetting base case check causing infinite recursion
Fix: Add condition if (low < high) before recursive calls

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting parts recursively.

Use Quick Sort when you want an efficient average-case sorting algorithm with divide and conquer.

The key insight is choosing a pivot to split the array into smaller parts that can be sorted independently.

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