第三周下：QuickSort

Java sort for primitive types

1. Quicksort

1. 思路：

   • 打乱array中的item顺序（用来保障Performance）
   • 锚定一个item，比如第一个a[lo]，比它大的都去右边，比它小的都去左边
     • i pointer：从左到右扫，直到a[i] > a[lo]时停下
     • J pointer：从右到左扫，直到a[j] < a[lo]时停下
     • 交换a[i]和a[j]
     • 全部结束后(i>=j)，交换a[lo]和a[j]
   • 递归地将所有排好

2. Performance

   • best case：~ compares
   • worst case: ~ compares
   • Average: ~ compares，~
     • Compares 比 merge sort 多39%
     • 但因为更少的data movement，所以比merge sort要快

3. Stability

   • Quicksort is not stable

4. Java implementation

   import edu.princeton.cs.algs4.StdRandom;
   
   public class Quick{
    private static int partition(Comparable[] a, int lo, int hi){
        int i = lo;
        int j = hi + 1;
        while(true){
            // 找到比a[lo]大的a[i]
            while(less(a[++i], a[lo])){
                if(i == hi){
                    break;
                }
            }
            // 找到比a[lo]小的a[j]
            while(less(a[lo], a[--j])){
                if(j == lo){
                    break;
                }_
            }
            // 检查i，j是否已经跨过彼此（即i>=j），是的话就结束
            if(i >=j){
                break;
            }
            // 交换a[i],a[j]
            exch(a, i, j);  
        }
        // 狡猾a[lo],a[j]
        exch(a, lo, j);
        // 返回j,代表已经排好的item所在的index
        return j;
   
    }
   
    public static void sort(Comparable[] a){
        // shuffle让performance至少大概率不会在worst case
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1);
    }
   
    private static void sort(Comparable[] a, int lo, int hi){
        // 递归地终止条件
        if(hi <= lo){
            return;
        }
   
        // 优化1：对于比较小的array(定cutoff=10)，用quick sort太浪费memory，改用insertion sort
        int cutoff = 7;
        if(hi <= lo+cutoff - 1){
            Insertion.sort(a); // Insertion.java与Merge.java放在同一个目录下
            return;
        }
            // 结束优化1
   
        // 优化2：不再随意地直接选第一个item，即a[lo]来锚定，而选用a[lo], a[hi], a[(lo+hi)/2]中的median
        int m = medianOf3(a, lo, (lo+hi)/2, hi);
        exch(a, lo, m);  
        // 结束优化2
   
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }
   
    // item v，w比较大小
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0
    }
   
    // a[i]和a[j]交换位置
    private static void exch(Comparable[] a, int i, int j){
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
   
    private static int medianOf3(Comparable[] a, int lo, int md, int hi){
        int[] arr3 = new int[];
        arr3[0] = a[lo];
        arr3[1] = a[md];
        arr3[2] = a[hi];
        Insertion.sort(arr3);
        return 
    }
   }
   

2. Selection

1. 目标：给定一个array（有n个items），找到第k个最小的item
2. 思路：
   • 找到合适的a[j]，它的左边都比它小，右边都比它大
   • 根据j，在一个subarray中重复，直到找到j=k
   • (代码见上方)
3. Performance
   1. on average：take linear time，~ compares
   2. worst case：~ compares （但已经靠random shuffle来提供一个probabilistic guarantee了)

3. Duplicate keys

1. Quicksort问题：

   • 遇到和锚定的item相同时，会将相同的item都放在锚定的item的一边，这样是很没效率的。因为，当所有key全部相同时，需要比较_{$\frac{1}{2}N^2$次。我们希望，它在遇到相同的item时就能停下来，不改变这个item的位置。这样当所有key都相同时，只需比较}

2. 思路（3-way partitioning）：

   • 锚定item v，比如选第一个item a[lo]。

   • 与v相同的都放在lt和gt之间，lt左边的item都小于v，gt*右边的item都大于v

     • 当a[i] < v时，a[lt]和a[i]交换，lt和i都+1
     • 当a[i] > v时，a[gt]和a[i]交换，gt-1
     • 当a[i] == v时，i+1

3. Java implementation

   import edu.princeton.cs.algs4.StdRandom;
   
   public class Quick3Way{
    public static void sort(Comparable[] a){
        // shuffle让performance至少大概率不会在worst case
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1);
    }
   
    private static void sort(Comparable[] a, int lo, int hi){
        int lt = lo;
        int gt = hi;
        int i = lo;
        Comparable v = a[lo];
   
        if(hi <= lo){
            return;
        }
   
        while(i <= gt){
            int cmp = a[i].compareTo(v);
            if(cmp < 0){ // a[i] < v
                exch(a, lt++, i++);
            }else if(cmp > 0){ // a[i] > v
                exch(a, i, gt--);
            }else{
                i++;
            }
        }
   
        sort(a, lo, lt-1);
        sort(a, lt+1, hi);
    }
   
    // a[i]和a[j]交换位置
    private static void exch(Comparable[] a, int i, int j){
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
   }
   

4. System sorts

1. Java system sorts: Array.sort()

   • 遇到Reference types: 用merge sort。优点：稳定，保证 的compares
   • 遇到primitive types：用quick sort。优点：占用更少的memory，更快

   import java.util.Arrays
   import edu.princeton.cs.algs4.StdIn;
   import edu.princeton.cs.algs4.StdOut;
   
   public class StringSort{
     public static void main(String args){
       String[] a = StdIn.readString();
       Array.sort(a);
       for(int i = 0; i < a.length; i++){
         StdOut.println(a[i]);
       }
     }
   }