Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

Princeton Algorithms P1W3 Mergesort and Quicksort

2017-01-07

merge sort

  1. divide array into two halves
  2. recursively sort each half
  3. merge two halves

mergesort

time: at most \(N \log N\) compares and \(6N \lg N\) array accesses to sort any array of size \(N\).
memory: use extra space proportional to N

merge

Goal: given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi], replace with sorted subarray a[lo] to a[hi]

Copy to auxiliary array aux[], use index i and j for each half, use index k for the output a[];
compare aux[] of each half with the minimum index, then copy the smaller one to a[];
increase both the corresponding index of the smaller one and k by one.

code for merge

// assertion  
assert isSorted(a,lo,mid);
assert isSorted(a, mid+1, hi);  

for (int k = lo; k<=hi; k++)
    aux[k] = a[k];
    
int i = lo, j = mid + 1;
for (int k = lo; k <= hi, k++)
{
    if      (i > mid)               a[k] = aux[j++];
    else if (j > hi)                a[k] = aux[i++];
    else if (less(aux[j], aux[i])   a[k] = aux[j++];
    else                            a[k] = aux[i++];
}

assert isSorted(a, lo, hi);

code for mergesort

create aux array outside the merge class

if (hi <= lo) return;  
int mid = lo + (hi - lo)/2;  
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);

assertion

java -ea prog   // enable assertion  
java -da prog   // disable assertion  

improvement

  1. Use insertion sort for small subarrays.

    • mergesort has too much overhead for tiny subarrays
    • cutoff to insertion sort for about 7 items.
      if (hi <= lo +cutoff -1)
      {
       Insertion.sort(a, lo, hi);
       return;
      }
      
  2. Stop if already sorted
    • if the biggest in the first half is less than or equal to the smallest in second half.
    • Helps for partially-ordered arrays
      if (!less(a[mid+1], a[mid]) return;
      
  3. eliminate the copy to the auxiliary array (save time but not space)

bottom-up mergesort

no recursion

  1. pass through array, merging subarrays of size 1
  2. repeat for subarray of size 2, 4, 8, 18, …
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz + sz)
    for (int lo = 0; lo < N - sz; lo += sz+sz)
        merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1__;

sorting complexity

Computational complexity: to study efficiency of algorithms for solving a particular problem X.

Model of computation: allowable operations
Cost model: Operation count(s)
Upper bound: Cost guarantee provided by some algorithms for X
Lower bound: Proven limit on cost guarantee of all algorithms for X
Optimal algorithm: Algorithm with best possible cost guarantee for X

Example: sorting

Model of computation: decision tree
Cost model: # of compares
Upper bound: \(\sim N \lg N\) from mergesort
Lower bound: \(N \lg N\)
Optimal algorithm: mergesort (but not for space)

Any compare-based sorting algorithm must use at least \(\lg(N!) \sim N \lg N\) compares in the worst case.

  • worst case dictated by height h of decision tree.
  • binary tree of height h has at most \(2^h\) leaves
  • \(N!\) different orderings \(\rightarrow\) at least \(N!\) leaves

\(2^h \ge \text{# leaves} \ge N! \)

Lower bound may not hold if the algorithm has some information:

  • initial order of the input
  • distribution of key values
  • representation of the keys

comparators

Can sort using an alternate order or many different order
Must be a total order

Arrays.sort(a, String.CASE_INSENSITIVE_ORDER);  

public static void sort(Object[] a, Comparator comparator)
{   
    int N = a.length;
    for (int i = 0; i<N; i++)
        for (int j = i; j > 0 && less(comparator, a[j], a[j-1]); j--)
            exch(a,j,j-1);
            
    private static boolean less(Comparator c, Object v, Object w)
    { return c.compare(v,w) < 0;    }
    private static void exch(Object[] a, int i, int j)
    { Object swap = a[i]; a[i]=a[j]; a[j] = swap;   }
}

implement

public static final Comparator<Student> BY_NAME = new ByName();
private static class ByName implements Comparator<Student>
{
    public int compare(Student v, Student w)
    { return v.name.compareTo(w.name);  }
}

// use
Arrays.sort(a, Student.BY_NAME);

stability

Insertion sort and mergesort are stable (but not selection sort or shellsort)

For Insertion sort, equal items never move pass each other.
Selection sort is not stable since it have long-distance exchange might move an item pass some equal item.
The original order of equal items may be changed so unstable.

quicksort

quicksort

  1. shuffle the array
  2. partition so that, for some j
    • entry a[j] is in place
    • no larger entry to the left of j
    • no smaller entry to the right of j
  3. sort each piece recursively.

Phase 1: repeat until i and j pointers cross.

  • scan i from the left to right so long as (a[i]<a[lo])
  • scan j from the right to left so long as (a[j]>a[lo])
  • exchange a[i] with a[j]

Phase 2: When pointer cross

  • exchange a[lo] with a[j]
private static int partition(Comparable[] a, int lo, int hi)
{
    int i = lo, j = hi + 1;
    while (true)
    {
        while (i < hi && less(a[++i], a[lo]);
        while (j > lo && less(a[lo], a[--j]);
        if (i >= j) break;
        exch(a, i, j);
    }
    
    // phase 2
    exch(a, lo, j);
    return j;
}

// quicksort, recursively

public class Quick
{
    private static int partition(Comparable[] a, int lo, int hi)
    {...}
    public static void sort(Comparable[] a)
    {
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1);
    }
    private static void sort(Comparable[] a, int lo, int hi)
    {
        if (hi <= lo + CUTOFF - 1) 
        {
            Insertion.sort(a, lo, hi);
            return;
        }
        int j =  partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

details

  1. partition in-place: does not use extra space
  2. terminating the loop: testing whether the pointers cross is a bit trickier than it might seem.
  3. staying in bounds. The (j == lo) test is redundant but the (i == hi) is not.
  4. preserving randomness: shuffling is needed for performance guarantee.
  5. Equal keys: when duplicates are presents, it is better to stop on keys equal to the partitioning item’s key.

best case: \(\sim N \log N\)
worst case: \(\sim 0.5 N^2\) (if already sorted, so shuffling is needed.)

The average number of compares to quicksort an array of N distinct keys is \(\sim 2N \ln N\) and the number of exchanges is \(\sim \frac{1}{3}N \lg N\)

average case:

  • number of compare is \(\sim 1.39 N \lg N\)
  • 39% more compares than mergesort
  • but faster than mergesort because of less data movement

properties

  1. partitioning: constant extra space
  2. depth of recursion: logarithmic extra space
  3. not stable

improvements

  1. insertion sort small subarrays (around 10)
  2. best choice of pivot item is the median
// median
int m = medianOf3(a, lo, lo + (hi - lo)/2, hi);
swap(a, lo, m);

selection

Goal: Given an array of N items, find a \(k^{th}\) smallest item.
Upper bound: \(N \log N\)
Lower bound: \(N\)

quick-select

  1. entry a[j] is in place
  2. no larger entry to the left of j
  3. no smaller entry to the right of j
StdRandom.shuffle(a);
int lo = 0; hi = a.length - 1;
while (hi > lo)
{
    int j = partition(a, lo, hi);
    if          (j < k) lo = j + 1;
    else if     (j > k) hi = j - 1;
    else               return a[k];
}
return a[k];

Quick-select takes linear time on average.

There is a compare-based selection algorithm whose worst-case running time is linear. But constants are too high \(\rightarrow\) not used in practice.

duplicate keys

Often, purpose of sort is to bring items with equal keys together.

  • sort population by age
  • find collinear points
  • remove duplicates from mailing list
  • sort job applicants

mergesort with duplicate keys: between \(\frac{1}{2}N \lg N\) and \(N\lg N\) compares.

quicksort with duplicate keys: algorithm goes quadratic unless partitioning stops on equal keys.

Recommend: Stop scans on items equal to the partitioning item. \(\sim N \lg N\) compares when all keys equal.
Desirable: Put all items equal to the partitioning item in place.

3-way partitioning (Dijkstra)

  • entries between lt and gt equal to partition item v.
  • no larger entries to left of lt
  • no smaller entries to the right of lt
public static void sort(Comparable[] a, int lo, int hi)
{
    if hi <= lo return;
    int lt = lo; gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt)
    {
        int cmp = a[i].compareTo(v);
        if cmp > 0      exch(a, i, gt--);
        else if cmp <0  exch(a, i++, lt++);
        else            i++;
    }
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
}

Quicksort with 3-way partitioning is entropy optimal.

system sorts

Arrays.sort()

  • has different method for each primitive type
  • has a method for data types that implement Comparable
  • has a method that uses a Comparator
  • use tuned quicksort for primitive types (performance is key factor); tuned mergesort for objects
import java.util.Arrays;

Arrays.sort(a)

Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2019. All rights reserved by melonskin. Powered by Jekyll.