.. role:: python(code) :language: python .. index:: divide conquer combine independent subproblems .. `Quicksort `_ `Merge sort `_ `Bisection insertion `_ .. _`sec:divide_conquer`: 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 :ref:`Recursion ` section, is that instead of reducing the problem size by "one" (for example computing :math:`N!` from :math:`(N-1)! \cdot N`), a divide and conquer algorithm will often try to create two independent subproblems of size :math:`N/2`. .. admonition:: 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. .. _`ex:quicksort`: .. collapse:: 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 :python:`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. .. code-block:: python # 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) .. literalinclude:: ../../../../src/algo/divide_conquer/divide_conquer.py :pyobject: quicksort :name: quicksort :linenos: :caption: src .. literalinclude:: ../../../../src/algo/divide_conquer/divide_conquer.py :pyobject: partition :name: partition :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/divide_conquer/test_divide_conquer.py :pyobject: test_quicksort :name: test_quicksort :linenos: :caption: tests 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 :math:`n-1` comparisons, then :math:`n-2`, :math:`n-3`, ... For a total of :math:`n^2`. However, imagine that the pivot always split the sequence in exactly half. The number of required splitting levels is :math:`\propto \ln(n)`. For a total of :math:`n \ln(n)`. The mean expected splitting ratio is between half and one, which gives a :math:`n \ln(n)` complexity too. .. admonition:: 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? .. _`ex:mergesort`: .. collapse:: 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. .. literalinclude:: ../../../../src/algo/divide_conquer/divide_conquer.py :pyobject: merge_sort :name: merge_sort :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/divide_conquer/test_divide_conquer.py :pyobject: test_merge_sort :name: test_merge_sort :linenos: :caption: tests 3. Splitting in half at every level leads to :math:`\propto \ln(n)` levels. The combining step makes :math:`\approx n` comparisons at every level. For a total of :math:`n \ln(n)`. :math:`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. .. admonition:: 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. .. collapse:: Hint It is much easier to work with two indexes: for each slice, the index :python:`left` indicates the location of the first element of the slice in the original sequence, the index :python:`right` indicates the index following the last element of the slice in the original sequence. The function :python:`bisect.bisect_left` does exactly the job which is asked. .. _`ex:bisection`: .. collapse:: 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. .. code-block:: python # 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) .. literalinclude:: ../../../../src/algo/divide_conquer/divide_conquer.py :pyobject: bisect :name: bisect :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/divide_conquer/test_divide_conquer.py :pyobject: test_bisect :name: test_bisect :linenos: :caption: tests