Quicksort

Divide & Conquer

Divide and Conquer is a fundamental algorithmic technique that breaks a problem into smaller subproblems, solves them independently, and then combines the results to obtain the final solution.

Problem: Sum of Array using Divide and Conquer

function arraySum(arr) {
    if (arr.length === 0) {
       return 0; 
    }
    return arr[0] + arraySum(arr.slice(1)); 
}

console.log(arraySum([1, 2, 3, 4])); // 10

---

Quicksort ( Algorithm )

1. Base Case: Empty array, array with 1 element, or array with 2 element (swap if first is bigger)
2. Choose a Pivot: Select a pivot element from the array.
3. Partitioning: Split the array into two sub-arrays:
   • Elements smaller than the pivot.
   • Elements greater than or equal to the pivot.
4. Recursion: Recursively apply Quicksort on both sub-arrays and then combine them.

function quickSort(arr) {
  // Base case: arrays of length 0 or 1 are already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // 1. Recurrence (Divide): Pick the first element as pivot
  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // 2. Backtracking (Combine): left + pivot + right
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// Test with the diagram's exact array:
const input = [7, 2, 9, 4, 3, 8, 1];
console.log(quickSort(input)); 
// Output: [1, 2, 3, 4, 7, 8, 9]