Algorithm Design: Divide-and-Conquer Algorithms

Divide-and-conquer algorithms

One big problem might be hard to solve, but two half-sized problems might be significantly easier. In these cases, divide-and-conquer algorithms cope well by:

• Splitting the problem into smaller subproblems.

• Solving the subproblems independently.

• Combining the solutions of subproblems into a solution of the original problem.

The situation is usually more complicated than this. After splitting one problem into subproblems, a divide-and-conquer algorithm usually splits these subproblems into even smaller sub-subproblems until it reaches a point at which it no longer needs to recurse. A critical step in many divide-and-conquer algorithms is recombining solutions of subproblems into a solution for a larger problem.

To give an example of a divide-and-conquer algorithm, we will consider the Sorting Problem:

$\rule[0 pt]{1000 pt}{0.5 pt}\\$

Sorting Problem

Sort a list of integers.

Input: A list of $n$ distinct integers $a = (a_{1},a_{2},...,a_{n})$.

Output: Sorted list of integers, that is, a reordering $b = (b_{1},b_{2},...,b_{n})$ of integers from $a$ such that $b_{1}$ $<$ $b_{2}$ $<$ $···$ $<$ $b_{n}$. $\rule[0 pt]{1000 pt}{0.5 pt}\\$

Before talking about a divide-and-conquer strategy for sorting, let’s discuss a simpler algorithm for sorting.

Selection sort algorithm

$SelectionSort$ is a simple iterative method to solve the Sorting Problem. It first finds the smallest element in $a$ and moves it to the first position by swapping it with whatever happens to be in the first position (i.e., $a_1$).

Next, it finds the second smallest element in $a$, and moves it to the second position, again by swapping with $a_2.$ At the $i$-th iteration, $SelectionSort$ ...