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)$

#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

#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

#include <utility>

size_t median3 (int* A, size_t first, size_t last) {
  size_t mid = first + (last - first) / 2;
  --last;
  if (A[last] < A[mid])
      std::swap (A[last], A[mid]);
  if (A[last] < A[first])
      std::swap (A[last], A[first]);
  if (A[mid] < A[first])
      std::swap (A[mid], A[first]);
  return mid;
}

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);
}

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

A

{ 1, 0, -1, 2, 2, 2, 5, 3, 4 }

result = partition(A, 0, 9);
std::cout << result.first << ' ' << result.second;

3 6

Additional Resources

• Merge Sort
  • Merge Demo
• Quick Sort
  • Partitioning Demo
  • QuickSelect (nth_element) Demo

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