第二周下：Elementary Sorts

1. Selection Sort

• 思路：

  • In iteration i, find index min of smallest remaining entry
  • Swap a[i] and a[min]
  • 从左到右升序

• Performance：

  • Compares： ~
  • Changes: N

• Running time: Quadratic time, even if input is sorted

  • 因为即使已经sorted，但程序不知道，还是会全部比较一遍

• Java implementation

  public class Selection{
    public static void sort(Comparable[] a){
        int n = a.length;
        // 向右逐个移动pointer
        for(int i = 0; i < n; i++){
            // 在右边剩余item中找到最小的
            int min = i;
            for(int j = i+1; j < n; j++){
                if(less(a[j], a[min])){
                    min = j;
                }
            }
        }
        // a[i],a[min]交换位置
        exch(a, i, min);
    }
  
    // 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;
    }
    
    // 检验array是否完成排序
    private static boolean isSorted(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
  }
  

• 注：Comparable interface（built in to Java）

  public interface Comparable<Item>{
    public int compareTo(Item that);
  }
  

  • Interface是abstract class，其中的methods也是
  • 具体实现时，要在创建object时，在object中完成compareTo(Item that)
    • Less: return -1
    • Greater: return +1
    • Equal: return 0

2. Insertion sort

• 思路：

  • In iteration i， swap a[i] with each larger entry to its left

• Performance：

  • best case (升序):
    • Compares: N-1
    • Exchange: 0
  • worst case（降序且无重复）:
    • Compares: ~
    • Exchange: ~
  • on average:
    • Compares: ~
    • Exchange: ~

• Java implementation

  public class Insertion{
    public static void sort(Comparable[] a){
        int n = a.length;
        // 向右移动pointer
        for(int i = 0; i < n; i++){
            // j从右向左移动，a[j]和它左边较大的那个交换位置
            for (int j = i; j > 0; j--){
                if (less(a[j], a[j-1])){
                    exch(a, j, j-1)
                }else{
                    break;
                }
            }
        }
    }
  
    // 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;
    }
    
    // 检验array是否完成排序
    private static boolean isSorted(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
  }
  

3. Shellsort

• Idea:

  • shellsort 与 insertion sort相似，差别在于后者逐个比较，前者h个h个比较（shellsort：insertion sort，with stride length h）
  • 假设在一个完美降序且不重复的数列，insertion sort 的compares和exchange都是quadratic，很亏；利用shellsort，比如先7-sort，再4-sort，最后1-sort（标准insertion sort）的话，performance就比较优秀了
  • 常用的increment：3x+1，因为比较好算

• Performance（3x+1 increments）：

  • worst case ：compares:
  • best case(升序)：compares: ~ (linearithmic)

• Java implementation：

  public class Shell{
    public static void sort(Comparable[] a){
        int n = a.length;
  
        // 3x+1 increment数列：1， 4， 13, 40, 121 ...
        int h = 1;
        while(h < n/3){
            h = 3*h +1;
        }
  
        while(h >= 1){
            // h-sort the array
            for(int i = h; i < n; i++){
                for(int j = i; j>= h && less(a[j], a[j-h]); j-=h){
                    exch(a, j, j-h)
                }
            }
  
            // move to next increment
            h = h/3;
        }
    }
  
    // 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;
    }
    
    // 检验array是否完成排序
    private static boolean isSorted(Comparable[] a){
        for(int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
  }
  

4. Shuffle sort

• 思路：
  • 给每个array entry一个随机的实数
  • 利用这些实数，给array排序

5. Graham scan（Convex hull）

• 思路：

  • 选一个有最小的y-coordinate的点p

  • 其他点按照与p的polar angle给点排序

  • 如果是ccw(counterclockwise)保留

    • 给定3个点a, b, c

    • 

    • 如果 => a->b->c: ccw

    • 如果 => a->b->c: clockweise

    • 如果 => a->b->c: collinear

• Java implementation

  public class Point2D{
    public final Comparator<Point2D> POLAR_ORDER = new POlarOrder();
    private final double x;
    private final double y;
  
    public Point2D(double x, double y){
      this.x = x;
      this.y = y;
    }
  
    // 实现counterclockwise(ccw)
    public static int ccw(Point2D a, Point2D b, Point2D c){
      double area2 = (b.x -a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
      if(area2 < 0){
        return -1; // clockwise
      }else if(area2 > 0){
        return 1; // ccw
      }else{
        return 0; // collinear
      }
    }
  
    // one Comparator for each point(所以没有static)
    private class PolarOrder implements Comparator<Point2D>{ 
      public int compare(Point2D q1, Poin2D q2){
        double dy1 = q1.y - y;
        double dy2 = q2.y - y;
  
        if(dy1 == 0 && dy2 == 0){
          return 0;  // p, q1, q2 水平
        }else if(dy1 >=0 && dy2 < 0){
          return -1; // q1在p上，q2在p下
        }else if(dy2 >=0 $$ dy1 < 0){
          return +1; // q2在p上，q1在p下
        }else{
          //上述情况都不符合，说明q1，q2在p的同侧，比较是否ccw
          return -ccw(Point2D.this, q1, q2);
        }
      }
    }
  }