Divide and Conquer

CSCI 362: Data Structures

Prof. William Killian

Graphical Example: Drawing a Ruler

Problem: Draw marks at regular intervals on a line

-----------------------------

             1/2
     1/4      |      3/4
 1/8  |  3/8  |  5/8  |  7/8
  |   |   |   |   |   |   |
--+---+---+---+---+---+---+--
// recursive
void drawRuler (double xBegin, double xEnd, int height);
// draws a single mark
void drawMark (double xCoord, int height);

drawRuler (0, 1, 3);
   --> drawMark (0.5, 3);

-----------------------------

             1/2
              |         
              |             
              |            
--------------+--------------
--> drawRuler (0, 0.5, 2);
    --> drawMark (0.25, 2);
--> drawRuler (0.5, 1, 2);
    --> drawMark (0.75, 2);

-----------------------------

             1/2
      1/4     |     3/4   
       |      |      |      
       |      |      |     
-------+------+------+-------
drawRuler (0, 0.25, 1)
--> drawMark (0.125, 0)
drawRuler (0.25, 0.5, 1)
--> drawMark (0.375, 0)
drawRuler (0.5, 0.75, 1)
--> drawMark (0.125, 0)
drawRuler (0.75, 1, 1)
--> drawMark (0.975, 0)

-----------------------------

             1/2
     1/4      |      3/4
 1/8  |  3/8  |  5/8  |  7/8
  |   |   |   |   |   |   |
--+---+---+---+---+---+---+--

Recursive Ruler

def drawRuler (begin, end, h):
    # base case?
    # recursive case?

if h == 0:
        return

mid = begin + (end - begin) / 2
    drawRuler (begin, mid, h - 1)
    drawMark (mid, h)
    drawRuler (mid, end, h - 1)

A divide and conquer (and combine) algorithm:

  • splits a problem into subproblems
  • solves those subproblems
  • combines solutions to subproblems to solve the whole problem

Iterative Ruler

def drawRuler(begin, end, incr):
    drawMark (begin, END_HEIGHT);
    begin += incr
    while begin != end:
        drawMark (begin, ???) # what goes here?
        begin += incr
    drawMark (end, END_HEIGHT);

Divide and Conquer Sorting Algorithms

Merge Sort

  • split in half (divide)
  • sort halfs recursively (conquer)
  • merge sorted halves (combine)
  • Worst = Average = $O(N lg N)$

Quick Sort

  • Choose a pivot value from the array
  • Partition the array into groups (divide)
    • Elements to left <= pivot
    • Elements to right >= pivot
  • Sort two subarrays recursively (conquer)
  • Average = $O(N lg N)$
  • Worst = $O(N^2)$
In [2]:
#include <algorithm>
void mergeSort (int A[], size_t first, size_t last) {
    if (last - first > 1) {
        size_t mid = first + (last - first) / 2;
        mergeSort (A, first, mid);
        mergeSort (A, mid, last);
        std::inplace_merge (A + first, A + mid, A + last);
    }
}

Merge algorithm

Merge sort requires a merge algorithm

  • Complexity?

Out-of-place merge: merge (v, first, mid, last)

  • v[first, mid) is sorted
  • v[mid, last) is sorted
  • Result: v[first, last) sorted

merge

def merge(v, first, mid, last, out):
    i1, i2 = first, mid
    j = 0
    # while the first "half" isn't empty
    while i1 != mid:
        if i2 == last: # still have the first range to copy
            while i1 != mid: # copy remaining elements in left half
                out[j] = v[i1]
                i1 += 1
                j += 1
            return
        if v[i1] < v[i2]: # copy the smaller value to out
            out[j] = v[i1]
            i1 += 1
        else:
            out[j] = v[i2]
            i2 += 1
        j += 1
    while i2 != mid: # copy remaining elements in right half
        out[j] = v[i2]
        i2 += 1
        j += 1

Chalkboard example:

int[8] A = {7, 6, 4, 1, 3, 5, 2, 8};
mergeSort (A, 0 /* low */, 4 /* mid */, 8 /* high */);

QuickSort

void quickSort (int A[], size_t first, size_t last) {
    if (last - first > 1) {
        auto i = partition (A, first, last);
        // pivot is placed in A[i]
        quickSort (A, first, i);
        quickSort (A, i + 1, last);
    }
}

Note: not quite the code we'll be writing

Partition

  • How do we want to partition our data?
    • Two groups: <= pivot and > pivot
    • Three groups: < pivot, == pivot, > pivot
  • How do we select a good pivot?
size_t partition (int A[], size_t first, size_t last) {
  int pivot = /* somehow figure this out */;
  size_t up = first, down = last - 2;
  while (true) {
    while (A[++up] < pivot) {}
    while (A[--down] < pivot) {}
    if (up < down)
      swap (A[up], A[down]);
    else
      break;
  }
  swap (A[last - 2], A[up]);
  return up;
}

Choosing a good pivot

  • What would be the "perfect pivot"?
  • How could we find this "perfect pivot"?
  • Alternatives:
    • randomly choose a pivot
    • median of 3
    • recursive median of 5

median of 3

In [1]:
#include <utility>
int median3 (int* A, size_t first, size_t last) {
  size_t mid = first + (last - first) / 2;
  --last; // important: make last inclusive
  if (A[mid] < A[first])
    std::swap (A[mid], A[first]);
  if (A[last] < A[first])
    std::swap (A[last], A[first]);
  if (A[last] < A[mid])
    std::swap (A[last], A[mid]);
  std::swap (A[mid], A[last - 1]);
  return A[last - 1];
}

recursive median of 5

def chunk (size, chunks, index):
    return size * index / chunks

# range is [first, last)
def median5 (v, first, last):
    if (last - first <= 5):
        sort (v, first, last)
        return first + (last - first) / 2
    for i in range (0, 5):
        low = chunk (last - first, 5, i)
        high = chunk (last - first, 5, i + 1)
        medIdx = median5 (v, low, high)
        # swap median with "out"
        v[medIdx], v[first + i] = v[first + i], v[medIdx]
    sort (v, first, first + 5)
    return first + 2

QuickSort vs MergeSort

  • They are both $O(N lg N)$ in the average case
  • Why is quicksort faster than mergesort?
    • inner loop
    • no extra "juggling" of elements see inner loop:
      while (a[++i] < pivot);
  while (a[--j] > pivot);
  if (i < j) swap (a[i], a[j]);
  else break;

Algorithmic Analysis

Assumptions:

  • Random pivot
  • No cutoff for small arrays

Running time:

  • pivot selection: constant time: $O(1)$
  • partitioning: linear time $O(N)$
  • running time of two recursive calls

$T(N) = T(i) + T(N - i - 1) + cN$

  • $i$ number of elements on left half

Algorithmic Analysis -- worst case

Always choose the smallest element as the pivot

$$T(N) = T(i) + T(N - i - 1) + cN$$

In the worse case, $i = 1$ (or $i = N - 1$)

$$T(N) = T(N-1) + cN$$$$T(N-1) = T(N-2) + c(N-1)$$$$T(N-2) = T(N-3) + c(N-2)$$$$\vdots$$$$T(2) = T(1) + c(2)$$$$T(N) = T(1) + c \sum_{i=2}^{N}{i} = O(N^2)$$

Algorithmic Analysis -- best case

Always choose the median

$$T(N) = 2 * T(N / 2) + cN$$$$\frac{T(N)}{N} = \frac{T(N/2)}{N/2} + c$$$$\frac{T(N/2)}{N/2} = \frac{T(N/4)}{N/4} + c$$$$\frac{T(N/4)}{N/4} = \frac{T(N/8)}{N/8} + c$$$$\vdots$$$$\frac{T(2)}{2} = \frac{T(1)}{1} + c$$$$\frac{T(N)}{N} = \frac{T(1)}{1} + c * lg N $$$$T(N) = c * N lg N + N = O(N lg N)$$

Finding the kth smallest element

  • nth_element (v.begin(), v.end(), 0) == MIN
  • nth_element (v.begin(), v.end(), v.size() - 1) == MAX
  • nth_element (v.begin(), v.end(), v.size() / 2) == MEDIAN

Partition based on some pivot value

  • Wait -- this sounds sort of like QuickSort!
  • i = partition (A, left, right)
  • if the index of i matches $k$, return iterator to i
  • otherwise, recurse!
    • on left half if k < i
    • on right half if k > i
      • but now look for (k - i)th smallest element
+-----------------------+---+-----------------------+
+     values <= kth     |kth|     values >= kth     |
+-----------------------+---+-----------------------+

nth_element

int nth_element (int* A, size_t first, size_t last, size_t n) {
  size_t mid = partition (A, first, last);
  if (n == mid)
    return A[n];
  if (n < mid)
    return nth_element (A, first, mid, n);
  else
    return nth_element (A, mid, last, n - mid);
}

3-way partition

Dutch National Flag Problem

  • partition data into three groups:
    • all elements < v
    • all elements == v
    • all elements > v
  • should not require any extra space
  • should not move any elements more than once
  • should not compare any elements more than once

3-way partition

In [2]:
std::pair<size_t, size_t>
partition (int* A, size_t first, size_t last) {
  if (last - first <= 1) {
    return std::pair(first, last);
  }
  int pivot = A[median3(A, first, last)];
  size_t i = 0;
  while (i < last) {
    if (A[i] < pivot) {
      std::swap(A[first++], A[i++]);
    } else if (A[i] > pivot) {
      std::swap(A[i], A[--last]);
    } else {
      ++i;
    }
  }
  return std::pair(first, last);
}
In [3]:
int A[9] = {3, 2, 0, -1, 2, 4, 5, 2, 1};
#include <iostream>
auto result = partition(A, 0, 9);
std::cout << result.first << ' ' << result.second;

3 6
In [4]:
A
Out[4]:
{ 1, 0, -1, 2, 2, 2, 5, 3, 4 }
In [5]:
result = partition(A, 0, 9);
std::cout << result.first << ' ' << result.second;

3 6

Additional Resources

Shell Sort

  • Insertion sort wasn't all that bad
  • But we only ever moved ONE element closer at a time
    • What if we could move over many elements at a time?
    • How could we split/partition our data to make that possible?
  • Introducing: h_sort

H-Sort

Similar to insertion sort, but we specify a stride distance h

void hSort (int* A, size_t size, size_t h) {
  if (size < 2) {
    return;
  }
  for (size_t i = h; i < size; ++i) {
    for (size_t c = i; c >= h; c -= h) {
      if (A[c] < A[c - h]) {
        std::swap (A[c], A[c - h]);
      } else {
        break;
      }
    }
  }
}

Shell Sort

  • Repetitive calls to h_sort with decreasing size of h

  • What's a good sequence for h?

    • $2^k+1 = 1, 3, 7, ..., 2 * (f(n) + 1) - 1$
      • decrement by dividing by 2
    • $2^k = 1, 2, 4, 8, ..., 2* f(n)$
      • decrement by dividing by 2
    • Knuth Sequence: $1, 4, 13, 40, ... 3 *f(n-1)+1$
      • decrement by dividing by 3

Shell Sort

void shellSort (int* A, size_t size) {
  // figure out proper h for knuth sequence
  for (; h > 1; h = h / 3) {
    h_sort (A, size, h);
  }
  h_sort (A, size, 1);
}

Youtube