Divide & Conquer Approach and Quick Sort Algorithm

Overview of the “Quicksort” Algorithm and “Divide & Conquer” approach in JavaScript

Grokking Algorithms: Chapter 4, “Quicksort”, in 4 Minutes

Feeling Slow? Conquer Your Data with Divide and Conquer and Quicksort! Is your data a disorganized mess, taking forever to sort through? Fear not, fellow coder! Today’s blog post unveils the secrets of two powerful algorithms: Divide and Conquer (D&C) and Quicksort, a sorting algorithm that utilizes D&C. We’ll explore them through clear examples and code.

What is the Divide & Conquer Approach?

Divide and Conquer Approach Demonstration

Imagine you’re a farmer with a massive field(1680 meters X 640 meters) that needs to be divided into equal-sized plots. You want the biggest plots possible, but how do you tackle this giant rectangle? Enter Divide and Conquer (D&C), a problem-solving strategy that breaks down complex problems into smaller, more manageable ones.

Here’s the D&C approach in action:

1. Base Case: Identify the simplest version of the problem. Think “easy win.” For our farmer, this might be a square plot where one side length perfectly divides into the other (e.g., 25 meters by 50 meters).
2. Divide or Decrease: If it’s not the base case, chop the problem into smaller subproblems. Back to the field! We can mark out the biggest possible squares. Any leftover land becomes a new subproblem for the next round.

D&C works by recursively (meaning it calls itself) applying these steps until all subproblems reach the base case. It’s like a Russian nesting doll of problem-solving!

Here’s a JavaScript code example to illustrate the concept:

function divideAndConquer(land = [1680, 640]) {
  const [width, height] = land;
  // Base case
  if (width === height) {
    return `Biggest square plot that can be created in the given plot is ${width} meters X ${height} meters`;
  }
  console.log(width)
  console.log(height)
  // Divide
  const biggestSquare = Math.min(width, height);
  const remainingLand = [biggestSquare === width ? width : width - biggestSquare, biggestSquare === height ? height : height - biggestSquare];
  // Conquer (recursive call)
  return divideAndConquer(remainingLand);
}

divideAndConquer();

This is a simplified example, but it demonstrates the core idea of D&C with recursion.

Quicksort

Photo by Kelly Sikkema on Unsplash

Quicksort is a powerful sorting algorithm that leverages D&C. Here’s how it works:

• Base Case: Empty or single-element arrays are already sorted.
• Partitioning: Choose an element (pivot) from the array. Rearrange the array such that elements less than the pivot are on one side and elements greater than the pivot are on the other side. These become subproblems.
• Recursion: Sort the subproblems recursively using Quicksort.
• Combine: Combine the sorted subproblems (pivot in the middle) to get the final sorted array.

The efficiency of Quicksort depends on the chosen pivot. A random pivot selection leads to an average runtime of O(n log n), making it one of the fastest sorting algorithms.

Here’s a JavaScript code example to illustrate the concept:

function quicksort(array) {
  // Base case
  if (array.length < 2) {
    return array;
  }  
// Choose pivot (here, the first element)
  const pivot = array[0];

  // Partitioning
  const less = array.slice(1).filter(i => i <= pivot);
  const greater = array.slice(1).filter(i => i > pivot);

  // Recursion
  return [...quicksort(less), pivot, ...quicksort(greater)];
}

console.log(quicksort([10, 5, 2, 3])); // Output: [2, 3, 5, 10]

This code sorts an array using Quicksort. However, remember that a good pivot choice is crucial for optimal performance. In this case, the pivot point is the first item, making the current algorithm performance the worst-case scenario i.e. O(n²).

I hope this blog post has shed some light on the “Divide & Conquer Approach” and “Quicksort” algorithm. By understanding these concepts, you’ll be well on your way to mastering algorithms.

This blog post condenses Chapter 4, “Quicksort” from the fantastic book “Grokking Algorithms” by Aditya Bhargava. To learn more about algorithms and buy the book, check it out!

This in Nibesh Khadka. Make sure to show support by liking and sharing this post. Consider subscribing to the email list to get notified regularly about new posts.

This blog was originally published at Script Portal.