Quick Sort Algorithm 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 and 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 side. This helps in sorting the list efficiently.

intermediate

Explain the partition step in Quick Sort.

Partition rearranges the list so that all elements less than the pivot come before it, and all elements greater or equal come after. The pivot ends up in its correct sorted position.

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 to sort.

beginner

Why can Quick Sort be faster than other sorting algorithms like Bubble Sort?

Quick Sort divides the problem into smaller parts and sorts them independently, which reduces the total work. Bubble Sort compares and swaps elements repeatedly, which is slower for large lists.

What does Quick Sort use to divide the list?

A A stack

B A temporary array

C A pivot element

D A queue

Quick Sort uses a pivot element to split the list into smaller parts.

What happens to the pivot after partitioning?

A It swaps with the last element

B It stays at the start of the list

C It is removed from the list

D It moves to its correct sorted position

After partitioning, the pivot is placed where all smaller elements are left and larger or equal are right, so it is in the correct position.

What is the worst-case time complexity of Quick Sort?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

In the worst case, Quick Sort can take O(n^2) time, for example when the smallest or largest element is always chosen as pivot.

Which of these is NOT a step in Quick Sort?

A Merging sorted lists

B Choosing a pivot

C Partitioning the list

D Recursively sorting sublists

Quick Sort does not merge sorted lists; it sorts in place by partitioning and recursion.

Why is Quick Sort considered efficient on average?

A Because it divides the list and sorts parts independently

B Because it sorts by swapping adjacent elements only

C Because it uses extra memory

D Because it always picks the middle element as pivot

Quick Sort is efficient because it breaks the problem into smaller parts and sorts them separately.

Describe how Quick Sort sorts a list step-by-step.

Think about how the list is split and sorted in parts.

Explain why Quick Sort can be faster than simple sorting methods like Bubble Sort.

Focus on how Quick Sort handles the list differently.

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