Quick Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array around pivot

↓

Left sub-array < pivot

↓

Recursively quick sort left

↓

Combine sorted parts

↓

Done

Quick Sort picks a pivot, splits the array into smaller and bigger parts, sorts each part by repeating the process, then combines them.

Execution Sample

DSA Javascript

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

This code sorts an array by choosing the last element as pivot, splitting into left and right arrays, sorting them recursively, and combining.

Execution Table

Step	Operation	Array State	Pivot	Left Array	Right Array	Action
1	Start quickSort	[8, 3, 7, 6, 2]	2	[]	[8, 3, 7, 6]	Choose pivot 2
2	Partition	[8, 3, 7, 6, 2]	2	[]	[8, 3, 7, 6]	8 > 2 → right, 3 > 2 → right, 7 > 2 → right, 6 > 2 → right
3	Recurse left	[]	-	[]	[]	Left empty, return []
4	Recurse right	[8, 3, 7, 6]	6	[3]	[8, 7]	Choose pivot 6, partition into left [3], right [8,7]
5	Partition right	[8, 3, 7, 6]	6	[3]	[8, 7]	3 < 6 → left, 8 > 6 → right, 7 > 6 → right
6	Recurse left of right	[3]	3	[]	[]	Single element, return [3]
7	Recurse left of left of right	[]	-	[]	[]	Left empty, return []
8	Recurse right of left of right	[]	-	[]	[]	Right empty, return []
9	Combine left of right	[3]	3	[]	[]	Combine [] + 3 + [] → [3]
10	Recurse right of right	[8, 7]	7	[]	[8]	Choose pivot 7, left empty, right [8]
11	Recurse left of right of right	[]	-	[]	[]	Left empty, return []
12	Recurse right of right of right	[8]	8	[]	[]	Single element, return [8]
13	Combine right of right	[7, 8]	7	[]	[8]	Combine [] + 7 + [8] → [7,8]
14	Combine right	[3, 6, 7, 8]	6	[3]	[7, 8]	Combine [3] + 6 + [7,8] → [3,6,7,8]
15	Combine all	[2, 3, 6, 7, 8]	2	[]	[3, 6, 7, 8]	Combine [] + 2 + [3,6,7,8] → [2,3,6,7,8]
16	End	[2, 3, 6, 7, 8]	-	-	-	Array sorted

💡 Recursion ends when sub-array length is 0 or 1, fully sorted array returned

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 13	Final
arr	[8, 3, 7, 6, 2]	[8, 3, 7, 6, 2]	[8, 3, 7, 6]	[3]	[3]	[7, 8]	[2, 3, 6, 7, 8]
pivot	2	2	6	3	3	7	-
left	[]	[]	[3]	[]	[]	[]	-
right	[]	[8, 3, 7, 6]	[8, 7]	[]	[]	[8]	-

Key Moments - 3 Insights

Why do we choose the last element as the pivot?

Choosing the last element as pivot is a simple rule to split the array; see Step 1 and Step 4 in execution_table where pivot is last element.

What happens when the left or right sub-array is empty?

When left or right is empty, recursion returns immediately as in Step 3 and Step 7, preventing infinite loops.

How does the array get combined back after sorting sub-arrays?

After sorting left and right, the arrays are combined with pivot in the middle, shown in Steps 9, 13, and 14.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the pivot chosen?

A 6

B 2

C 8

D 3

💡 Hint

Check the 'Pivot' column at Step 4 in execution_table

At which step does the left sub-array become empty for the first time?

A Step 6

B Step 7

C Step 3

D Step 11

💡 Hint

Look at 'Left Array' column in execution_table rows for empty array

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

A Left and right arrays would be swapped

B Pivot would be different, changing partition elements

C No change in partitioning

D Algorithm would fail

💡 Hint

Pivot choice affects which elements go left or right, see Steps 1 and 4

Concept Snapshot

Quick Sort Algorithm:
- Pick a pivot (commonly last element)
- Partition array into left (< pivot) and right (> pivot)
- Recursively sort left and right sub-arrays
- Combine sorted left + pivot + sorted right
- Stops when sub-array size ≤ 1
- Efficient average O(n log n) sorting

Full Transcript

Quick Sort works by choosing a pivot element, usually the last in the array. It then splits the array into two parts: elements less than the pivot go to the left, and elements greater go to the right. Each part is sorted by repeating the same process recursively. When the parts are small enough (empty or one element), they are returned as sorted. Finally, the sorted left part, the pivot, and the sorted right part are combined to form the fully sorted array. This process is efficient and widely used for sorting arrays.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Sort the array by repeatedly selecting the smallest element

B. Compare every element with every other element and swap if needed

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

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element and divides the array into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting of parts

   It then sorts these parts by calling itself recursively until the whole array is sorted.

3. Final Answer:

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

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: pivot divides array, then sort parts recursively [OK]

Common Mistakes:

• Thinking Quick Sort compares all pairs directly
• Confusing Quick Sort with Selection Sort
• Believing Quick Sort merges arrays like Merge Sort

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in JavaScript during Quick Sort?

easy

A. arr[i], arr[j] = arr[j], arr[i];

B. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

C. swap(arr[i], arr[j]);

D. arr[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Identify correct swap method in JavaScript

   JavaScript does not support tuple unpacking like Python, so swapping requires a temporary variable.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable to swap correctly. arr[i], arr[j] = arr[j], arr[i]; is Python syntax, swap(arr[i], arr[j]); is undefined, arr[i] = arr[j]; arr[j] = arr[i]; overwrites values incorrectly.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Swap with temp variable = temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; [OK]

Hint: Use a temp variable to swap in JavaScript [OK]

Common Mistakes:

• Using Python-style tuple swap in JavaScript
• Overwriting one element before saving it
• Calling undefined swap function

3. What will be the output of the following Quick Sort partition step on array [4, 2, 7, 1] with pivot as the last element?

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++;
      let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
  }
  let temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
  return i + 1;
}

let arr = [4, 2, 7, 1];
let pi = partition(arr, 0, arr.length - 1);
console.log(arr);

medium

A. [1, 2, 7, 4]

B. [1, 2, 4, 7]

C. [4, 2, 7, 1]

D. [2, 1, 4, 7]

Solution

1. Step 1: Trace the partition loop

   Pivot = 1. Loop checks elements less than 1. No elements are less, so i stays at -1.

2. Step 2: Swap pivot with element at i+1

   Swap arr[0] and arr[3]: 4 and 1 swap places. Array becomes [1, 2, 7, 4].

3. Final Answer:

   [1, 2, 7, 4] -> Option A

4. Quick Check:

   Pivot 1 placed at start, others unchanged [OK]

Hint: Pivot swaps with first bigger element after loop [OK]

Common Mistakes:

• Assuming pivot stays at end
• Swapping wrong elements after loop
• Not updating i correctly

4. Identify the error in this Quick Sort partition function:

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) {
      let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
      i++;
    }
  }
  let temp = arr[low]; arr[low] = arr[i]; arr[i] = temp;
  return i;
}

medium

A. Loop should start from low, not low + 1

B. Pivot should be arr[high], not arr[low]

C. No error, function is correct

D. Swapping pivot with arr[i] should be with arr[i - 1]

Solution

1. Step 1: Understand pivot placement

   Pivot is arr[low]. After loop, pivot must be placed at correct position.

2. Step 2: Check swap of pivot with arr[i]

   Variable i points to next greater element, so pivot should swap with arr[i - 1], not arr[i].

3. Final Answer:

   Swapping pivot with arr[i] should be with arr[i - 1] -> Option D

4. Quick Check:

   Pivot swap index off by one [OK]

Hint: Pivot swap index is i-1 after partition loop [OK]

Common Mistakes:

• Swapping pivot with wrong index
• Confusing pivot position in array
• Changing loop start incorrectly

5. Which of the following pivot selection strategies in Quick Sort will result in the most balanced partitions and thus better performance?

hard

A. Choosing the median of first, middle, and last elements as pivot

B. Choosing the first element as pivot

C. Choosing the middle element as pivot

D. Choosing the last element as pivot

Solution

1. Step 1: Understand pivot selection strategies

   Choosing first or last can lead to worst-case O(n^2) on sorted arrays. Middle element alone may not be representative.

2. Step 2: Best strategy for balance

   Median-of-three selects a pivot likely closer to the array's true median, promoting balanced partitions and average O(n log n) performance.

3. Final Answer:

   Choosing the median of first, middle, and last elements as pivot -> Option A

4. Quick Check:

   Median-of-three pivot = balanced partitions [OK]

Hint: Median-of-three pivot improves balance and speed [OK]

Common Mistakes:

• Always picking first or last element as pivot
• Ignoring pivot choice impact on performance
• Assuming middle element is always best pivot