Quick Sort as Divide and Conquer in DSA Javascript - Execution Trace

Concept Flow - Quick Sort as Divide and Conquer

Choose pivot element

↓

Partition array into two parts

↓

Left part < pivot

↓

Recursively quick sort left

↓

Combine sorted parts + pivot

↓

Done

Quick Sort picks a pivot, splits the array into smaller and bigger parts, sorts each part by repeating the same steps, then joins them back.

Execution Sample

DSA Javascript

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length - 1];
  const left = arr.filter(x => x < pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

This code sorts an array by picking the last element as pivot, splitting smaller and bigger elements, sorting them recursively, and joining results.

Execution Table

Step	Operation	Array State	Pivot	Left Partition	Right Partition	Result After Step
1	Start quickSort on [5, 3, 8, 4, 2]	[5, 3, 8, 4, 2]	2	[]	[5, 3, 8, 4]	Not sorted yet
2	quickSort left []	[]	N/A	[]	[]	[]
3	quickSort right [5, 3, 8, 4]	[5, 3, 8, 4]	4	[3]	[5, 8]	Not sorted yet
4	quickSort left [3]	[3]	3	[]	[]	[3]
5	quickSort right [5, 8]	[5, 8]	8	[5]	[]	Not sorted yet
6	quickSort left [5]	[5]	5	[]	[]	[5]
7	quickSort right []	[]	N/A	[]	[]	[]
8	Combine [5] + 8 + []	[5, 8]	8	[5]	[]	[5, 8]
9	Combine [3] + 4 + [5, 8]	[3, 4, 5, 8]	4	[3]	[5, 8]	[3, 4, 5, 8]
10	Combine [] + 2 + [3, 4, 5, 8]	[2, 3, 4, 5, 8]	2	[]	[3, 4, 5, 8]	[2, 3, 4, 5, 8]
11	Final sorted array	[2, 3, 4, 5, 8]	N/A	N/A	N/A	[2, 3, 4, 5, 8]

💡 Recursion ends when sub-array length is 0 or 1, which are already sorted.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 8	Final
arr	[5,3,8,4,2]	[5,3,8,4,2]	[5,3,8,4]	[5,8]	[5,8]	[2,3,4,5,8]
pivot	N/A	2	4	8	8	N/A
left	N/A	[]	[3]	[5]	[5]	N/A
right	N/A	[5,3,8,4]	[5,8]	[]	[]	N/A
result	N/A	Not sorted	Not sorted	Not sorted	[5,8]	[2,3,4,5,8]

Key Moments - 3 Insights

Why does quickSort call itself on smaller parts instead of sorting the whole array at once?

Because quickSort uses divide and conquer: it splits the array around a pivot and sorts smaller parts recursively (see steps 2, 3, 5 in execution_table). This breaks the problem into easier pieces.

What happens when the array has 0 or 1 element?

The function returns immediately because such arrays are already sorted (see steps 2 and 7). This stops recursion and avoids infinite calls.

Why do we combine left part, pivot, and right part at the end?

Because after sorting left and right parts, joining them with the pivot gives the fully sorted array (see steps 8, 9, 10). This is how the sorted pieces come together.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what is the pivot chosen?

A 2

B 5

C 8

D 4

💡 Hint

Check the 'Pivot' column at step 1 in the execution_table.

At which step does quickSort sort the array [5, 8]?

A Step 3

B Step 8

C Step 5

D Step 10

💡 Hint

Look at the 'Array State' and 'Operation' columns to find when [5, 8] is processed.

If the pivot was chosen as the first element instead of the last, how would step 1's pivot change?

A Pivot would be 2

B Pivot would be 5

C Pivot would be 3

D Pivot would be 8

💡 Hint

The first element of [5,3,8,4,2] is 5; step 1 pivot is last element 2 currently.

Concept Snapshot

Quick Sort divides array by pivot
Partitions into smaller and bigger parts
Recursively sorts each part
Joins sorted parts with pivot
Stops when array size ≤ 1
Efficient divide and conquer sorting

Full Transcript

Quick Sort works by picking a pivot element from the array. It then splits the array into two parts: elements smaller than the pivot and elements bigger than the pivot. It sorts these parts by calling itself again on each part. When the parts are small enough (empty or one element), it stops. Finally, it joins the sorted parts and the pivot to get the fully sorted array. This process repeats recursively until the whole array is sorted.

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