Week 3 - Mergesort & Quicksort

1. Mergesort

  • Basic plan
    • Divide array into two halves.
    • Recursively sort each half.
    • Merge two halves.
  • Check https://cs.ericyy.me/cs50/week-3.html#merge-sort
  • Improvements:

    • Use insertion sort for small subarrays.
      • Mergesort has too much overhead for tiny subarrays.
      • Cutoff to insertion sort for ≈ 7 items.
    • Stop if already sorted.
    • Eliminate the copy to the auxiliary array.

        private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
      
            int i = lo; int 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[i], aux[j]))   a[k] = aux[i++];
                else                            a[k] = aux[j++];
            }
        }
      
        private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
      
            if(hi <= lo) return;
            int mid = lo + (hi - lo) / 2;
            sort(aux, a, lo, mid); // keep reverse aux and a
            sort(aux, a, mid+1, hi); 
            merge(a, aux, lo, mid, hi); // the last merge action is sorted 'a' 
            assert isSorted(a, lo, hi);
        }
      
        public static void sort(Comparable[] a) {
            Comparable[] aux = a.clone(); // duplicate a to aux
            sort(a, aux, 0, a.length-1);
            assert isSorted(a);
        }
      

1.1. Bottom-up Mergesort

  • Basic plan.
    • Pass through array, merging subarrays of size 1.
    • Repeat for subarrays of size 2, 4, 8, 16, ....

2. Stability

  • A stable sort preserves the relative order of items with equal keys.
  • For example:
    • The second sort changed the order of the students of section 3. So it's not stable.
  • To check whether a sort algorithm is stable or not is to check if it has long-distance exchange.
  • Insertion sort: every exchange is small steps. Stable
  • Selection sort: select the minimum to the front, which is big step and by-pass the equal items. Not Stable
  • Shell sort: Not Stable
  • Mergesort: Stable
  • Quicksort: Not Stable

3. Quicksort

  • Basic plan.

    • Shuffle the array.
      • Probabilistic guarantee against worst case.
    • 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
    • Sort each piece recursively.
  • Check https://cs.ericyy.me/cs50/week-3.html#quick-sort

  • empirical analysis

  • Best case. Number of compares is ~ N lg N.
  • Worst case. Number of compares is ~ ½ N 2 .
  • Average case. Number of compares is ~ 1.39 N lg N.
    • 39% more compares than mergesort.
    • But faster than mergesort in practice because of less data movement.
  • Improvements

    • Insertion sort small subarrays.
      • Even quicksort has too much overhead for tiny subarrays.
      • Cutoff to insertion sort for ≈ 10 items.
      • Note: could delay insertion sort until one pass at end.
    • Median of sample.

      • Best choice of pivot item = median.
      • Estimate true median by taking median of sample.
      • Median-of-3 (random) items.

          int m = medianOf3(a, lo, lo + (hi - lo)/2, hi); 
          swap(a, lo, m);
        

3.1. Quick-sort

  • Partition array so that:
    • Entry a[j] is in place.
    • No larger entry to the left of j.
    • No smaller entry to the right of j.
  • Repeat in one subarray, depending on j; finished when j equals k.
  • use quick-select if you don’t need a full sort.

3.2. Duplicate keys

  • Often, purpose of sort is to bring items with equal keys together.
  • Mergesort with duplicate keys. Between ½ N lg N and N lg N compares.
  • Quicksort with duplicate keys. Algorithm goes quadratic unless partitioning stops on equal keys!

3-way partitioning

  • Let v be partitioning item a[lo].
  • Scan i from left to right.
    • (a[i] < v): exchange a[lt] with a[i]; increment both lt and i
    • (a[i] > v): exchange a[gt] with a[i]; decrement gt
    • (a[i] == v): increment i
private 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, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else i++; 
    }

    sort(a, lo, lt - 1); 
    sort(a, gt + 1, hi);
}
  • Randomized quicksort with 3-way partitioning reduces running time from linearithmic to linear in broad class of applications.

3.3. System sorts

  • java.util.Array.sort()
    • Uses tuned quicksort for primitive types; tuned mergesort for objects.

4. Sorting Summary

results matching ""

    No results matching ""