Divide and Conquer

Divide and conquer follows three stages:

1. Divide the problem into smaller subproblems.

2. Conquer the subproblems.

3. Combine their solutions.

The strategy is particularly effective when subproblems are independent. The difference with the previous exercises in the Recursion section, is that instead of reducing the problem size by “one” (for example computing \(N!\) from \((N-1)! \cdot N\)), a divide and conquer algorithm will often try to create two independent subproblems of size \(N/2\).

Exercise (intermediate)

The quicksort algorithm is:

• choosing a pivot

• partitioning elements smaller and greater than the pivot

• recursively sorting the partitions

• combining the results

1. Give the divide/conquer/combine steps.

2. Implement and test.

3. Worst and mean complexity.

Correction

1. The divide step is the partitioning in two sequences: one with elements smaller than the pivot, one with elements greater than the pivot.

   The conquer step corresponds to applying the strategy down to the base case: an empty sequence or a singleton is already “sorted”.

   The combine step is almost trivial. The ouput of quicksort function is a sorted sequence. Thus, after the partitioning, the smaller element sequence is sorted, so is the larger element sequence, the combine step is just reassembling these two sorted sequence with the pivot in between.

2. # do not focus on the type hinting
   
   from typing import Protocol, TypeVar
   
   
   T_contra = TypeVar("T_contra", contravariant=True)
   
   
   class SupportsLessThan(Protocol[T_contra]):
       def __lt__(self, other: T_contra, /) -> bool: ...
   
   
   U = TypeVar("U", bound=SupportsLessThan)
   

   src

   def quicksort(seq: list[U]) -> list[U]:
       """conquer the base cases and combine sorted subsequences"""
       if len(seq) <= 1:
           return seq
   
       left, pivot, right = partition(seq)
       return quicksort(left) + pivot + quicksort(right)
   

   src

   def partition(seq: list[U]) -> tuple[list[U], ...]:
       """creates three subsequences,
       + elements strictly lower than a pivot
       + the pivot
       + the rest"""
       pivot = seq.pop()
       left: list[U] = []
       right: list[U] = []
       for elt in seq:
           if elt < pivot:
               left.append(elt)
           else:
               right.append(elt)
   
       return left, [pivot], right
   

   tests

   def test_quicksort() -> None:
       seq: list[float] = [3, -1, 5, 2, -7, 9]
       expected: list[float] = sorted(seq)
       assert quicksort(seq) == expected
   

3. The costly operation is the comparaison.

   The worst case is when the last element for the partition is always the greatest, in this case the left subsequence contains all the elements except the last.

   It means \(n-1\) comparisons, then \(n-2\), \(n-3\), …

   For a total of \(n^2\).

   However, imagine that the pivot always split the sequence in exactly half. The number of required splitting levels is \(\propto \ln(n)\).

   For a total of \(n \ln(n)\).

   The mean expected splitting ratio is between half and one, which gives a \(n \ln(n)\) complexity too.

Exercise (intermediate)

The merge sort algorithm is:

• repeatedly divides a sequence into approximately equal halves until subproblems contain one element

• merges pairs of sorted sequences

1. Give the divide/conquer/combine steps.

2. Implement and test.

3. Complexity. If sorting a list of 1 000 elements takes 2 s, how long does it take for 1 000 000 elements?

Correction

1. The divide step is the successive division in half until singleton.

   The conquer step is the base case: a singleton is already sorted.

   All the leg work lies in the combine step: merging efficiently two sorted sequence. The trick is to first create the merged sequence in decreasing sorting order. To do so, append the element in an empty merged sequence and iterate from the right in one of the two sorted sequence where the current element is the largest, then at the end reverse the merged list.

2. src

   def merge_sort(seq: list[U]) -> list[U]:
       """divide in two subsequences,
       conquer the base case,
       combine two sorted subsequences"""
       nb_elts: int = len(seq)
       if nb_elts <= 1:
           return seq
   
       median: int = nb_elts // 2
       left: list[U] = merge_sort(seq[:median])
       right: list[U] = merge_sort(seq[median:])
       # split recursively the seq
   
       # left and right are results of merge_sort hence are sorted
       joined: list[U] = []
       # joins the remaining part of left or right
       while left and right:
           # while both sequences are not empty
           if left[-1] < right[-1]:
               joined.append(right.pop())
           else:
               joined.append(left.pop())
       # put joined in the ascending order
       joined.reverse()
       remains: list[U] = left or right
       # joins the remaining part of left or right
       # this remain is sorted in ascending order
       # and is smaller than every elements of joined
       return remains + joined
   

   tests

   def test_merge_sort() -> None:
       seq: list[float] = [3, -1, 5, 2, -7, 9]
       expected: list[float] = sorted(seq)
       assert merge_sort(seq) == expected
   

3. Splitting in half at every level leads to \(\propto \ln(n)\) levels. The combining step makes \(\approx n\) comparisons at every level. For a total of \(n \ln(n)\).

   \(2 \times \cfrac{1\,000\,000 \ln(1\,000\,000)}{1\,000 \ln(1\,000)}\approx 1\) h

Note

Comparing quicksort and merge sort shows two opposite solution in terms of where the heavy work is done. For quicksort, the hard work is the partition, when every element of the sequence is compared to the pivot to create the two subsequences of lower and larger elements. Then the combine step is trivial.

Conversely, the merge sort chooses a divide step that accomplish almost nothing except creating smaller and smaller sequences. The hard work is performed when two sorted subsequences are merged into a sorted sequence.

Exercise (intermediate)

The bisection insertion operates on a sorted collection. It indicates where to insert an element keeping the sequence sorted.

The algorithm:

• examines the middle element;

• discards one half if the target must lie in the other half;

• repeats on the remaining interval.

1. Give the divide/conquer/combine steps. (trick question)

2. Implement and test.

Hint

It is much easier to work with two indexes: for each slice, the index left indicates the location of the first element of the slice in the original sequence, the index right indicates the index following the last element of the slice in the original sequence.

The function bisect.bisect_left does exactly the job which is asked.

Correction

1. The divide step is splitting the sequence in half.

   The conquer step is getting rid of the half from which the element to insert can not belong and repeat the process.

   The combine step is inexistant because the incorrect half sequence has been discarded, so there is nothing to combine with.

2. # do not focus on the type hinting
   
   from typing import Protocol, TypeVar
   
   
   T_contra = TypeVar("T_contra", contravariant=True)
   
   class SupportsGreaterOrEqualAndLowerThan(Protocol[T_contra]):
       def __ge__(self, other: T_contra, /) -> bool: ...
       def __lt__(self, other: T_contra, /) -> bool: ...
   
   
   V = TypeVar("V", bound=SupportsGreaterOrEqualAndLowerThan)
   

   src

   def bisect(sorted_haystack: list[V], needle: V) -> int:
       """find the insertion index to keep the order of a sorted sequence:
       divide the sorted sequence in two and keep only one viable subsequence,
       conquer the base case, no combine required the job is done"""
   
       def bisect_nested(left: int, right: int) -> int:
           """left index is the index of the first element of the subsequence,
           right is the index following the last element of the subsequence."""
           width: int = right - left
   
           # single remaining elt, decide if insert before or after
           if width == 1:
               if sorted_haystack[left] >= needle:
                   return left
   
               return right
   
           # cut in half and keep right ...
           middle: int = (right + left) // 2
           if sorted_haystack[middle] < needle:
               return bisect_nested(middle, right)
   
           # ... or keep left
           return bisect_nested(left, middle)
   
       if not sorted_haystack:
           return 0
       return bisect_nested(0, len(sorted_haystack))
   

   tests

   def test_bisect() -> None:
       nb_trials: int = 100
       nb_elts: int = 100
       for _ in range(nb_trials):
           seq = sorted([randint(0, 2 * nb_elts) for _ in range(nb_elts)])
           obtained: int = bisect_(seq, nb_elts)
           expected: int = bisect.bisect_left(seq, nb_elts)
           assert obtained == expected