Quick Sort Algorithm in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output of the 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, 5, 4];
let pivotIndex = partition(array, 0, array.length - 1);
console.log(array);

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

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

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

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

💡 Hint

Focus on how elements smaller than the pivot are moved before it.

The partition function moves all elements smaller than the pivot (8) to the left and places the pivot after them. So the pivot 8 ends up at the last position, and smaller elements are before it but not fully sorted.

❓ Predict Output

intermediate

Final Sorted Array from Quick Sort

What is the output of the array after running the full Quick Sort on this input?

DSA Javascript

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

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 = [10, 7, 8, 9, 1, 5];
quickSort(array, 0, array.length - 1);
console.log(array);

A [5, 1, 7, 8, 9, 10]

B [10, 9, 8, 7, 5, 1]

C [1, 7, 5, 8, 9, 10]

D [1, 5, 7, 8, 9, 10]

💡 Hint

Quick Sort sorts the array in ascending order.

Quick Sort recursively partitions and sorts the array. The final output is the fully sorted array in ascending order.

🧠 Conceptual

advanced

Understanding Quick Sort Pivot Choice Impact

Which statement best explains how the choice of pivot affects Quick Sort's performance?

A Choosing the middle element as pivot always guarantees the fastest sorting.

B Choosing a pivot that splits the array into two nearly equal parts leads to better average performance.

C Pivot choice does not affect Quick Sort's performance at all.

D Choosing the smallest element as pivot always results in the best case time complexity.

💡 Hint

Think about how balanced partitions affect recursion depth.

Quick Sort performs best when the pivot divides the array into two roughly equal parts, minimizing recursion depth and comparisons.

🔧 Debug

advanced

Identify the Bug in Quick Sort Partition

What error will this Quick Sort partition function cause when run?

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 array = [4, 5, 3, 7, 2];
let pi = partition(array, 0, array.length - 1);
console.log(array);

A Array is incorrectly partitioned with pivot not in correct position.

B SyntaxError due to invalid swap syntax.

C TypeError because i is undefined.

D No error, array is correctly partitioned.

💡 Hint

Check the final swap indices carefully.

The final swap uses arr[i] but i points one past the last smaller element, causing pivot to be placed incorrectly.

🚀 Application

expert

Quick Sort on Linked List

Which approach is best to implement Quick Sort on a singly linked list?

A Use the last node as pivot and rearrange nodes by changing links without extra space.

B Use merge sort instead because quick sort is not suitable for linked lists.

C Convert linked list to array, quick sort array, then rebuild linked list.

D Quick sort cannot be implemented on linked lists.

💡 Hint

Think about how to rearrange nodes efficiently in a linked list.

Quick Sort can be done in-place on linked lists by choosing a pivot and rearranging nodes by changing pointers, avoiding extra space.