Divide and Conquer

◀ A Four-Step Programming Model▶ Four Step Programming Model: An Example Amazon In terms of programming techniques, divide and conquer is a common way to design algorithms particularly recursive algorithms. It essentially consists of two steps:

• Divide: Divide a big problem into smaller ones, then solve them recursively until they hit the base case, which you use brute force to solve.
• Conquer: The solution to the initial problem comes from the solutions to its sub-problems.

In other words a divide and conquer algorithm works by recursively breaking down a problem into multiple sub problems of the same nature until they become simple enough to be solved directly.

A classic example is the quick sort algorithm. Here's the source code to perform quick sort in C:

void quickSort(int numbers[], int array_size){
  q_sort(numbers, 0, array_size - 1);
}
 
// a recursive function that breaks down the problem into smaller ones
// until they are simple enough to solve directly
void q_sort(int numbers[], int left, int right){
  int pivot, l_hold, r_hold;
 
  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right){
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right){
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right){
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

However, what I mean here is to divide the program into a group of tasks and deal with them one by one.

When code that does one task is written, particularly a function, you should go ahead and test it to see if it fully works, hence conquering a part of the program.

In Chapter 15 we'll be going through a set of programming exercises which will utilize the concept of Divide and Conquer.

When testing it, you should take into account every possible precondition and postcondition associated with that function. This is part of the fourth step we discussed in the previous section.
Next we'll look at an example of applying the divide and conquer concept as well as the four step programming paradigm so you can see both in action!◀ A Four-Step Programming Model▶ Four Step Programming Model: An Example