(maybe best algorithm for sorting.)

1. Quicksort

Idea:

1. shuffle the array
2. Partition the array into two subarrays to left and right of pivot (now pivot is in its final position)

no larger entry to the left of pivot
no smaller entry to the right of pivot

1. sort each subarray recursively

Implemetation

The partition process:
这个方法也比较巧妙.
Use 2 pointers i and j (个人觉得用hi, lo, pivot更好...) :

→ a[i]>=a[lo], a[j]<=a[lo] (注意是大于等于/小于等于)
⇒ exchange i and j
→ Scan until i and j cross (ie. j<=i)
⇒ finally exchange lo with j
函数的签名定义的好: 把lo到hi部分的数组分成两部分, 并返回分割点的index.

private static int partition(Comparable[] a, int lo, int hi){   
    int i=lo+1, j=hi;   
    while(i<j){   
        while( i<=hi && less(a[i],a[lo]) ) i++; //a[i]>=a[lo]   
        while( j>=lo && less(a[lo],a[j]) ) j--; //a[j]<=a[lo]   
        if(i<j) exch(a,i++,j--);   
    }   
    exch(a,lo,j); //exchange pivot with j   
    return j; //j in its final position   
}

这个函数其实并不好写对:

• test for cross pointers is not trival (ex. edge case: the pivot is the smallest/largest entry in the range)
• i<=hi is necessary !
• for keys equal to a[lo]: better to stop at them

invariance:

**Quicksort: **
使用partition函数和辅助sort函数(recursive). 注意在整个流程开始以前先shuffle一下.

private static void sort(Comparable[] a, int lo, int hi){   
    if(hi<=lo) return;   
    int pivot = partition(a, lo, hi);   
    sort(a,lo,pivot-1);   
    sort(a,pivot+1,hi);   
    return;
}   
public static void sort(Comparable[] a){   
    StdRandom.shuffle(a); // don't forget to shuffle the array   
    sort(a,0,a.length-1);   
}

The randomness is preserved: the subarrays after partitionning is still randomly ordered.

Analysis

Performance: ~40% faster than mergesort.

Best case

compares = NlgN

(each partition will divide the array in half)

**Worst case **

compares = 1/2*N^2

N+(N-1)+...+1
if the array is already in order, each partition will have one subarray of length=0

**Average case **

proposition **
On average, for array with N distinct keys, the #compares = ~2NlnN, #exchanges = ~1/2NlnN.
Proof.*
C(N) := # compares for N entries
pivot 在N个数离的排名是uniform的
接下来的数学推到很漂亮(不过可能没啥用..)

(上面最后一行写错了... 是2NlnN...orz) random shuffle: probalistic guarantee against worst case.

Pitfalls **
implementations will get quadratic performance if array:

• is sorted or reverse sorted
• has many duplicates (even if randomized)

Staility **
Quicksort is NOT** stable.
partitionning can make long range exchanges

Practical improvements

• cutoff to insertion sort for <10 items

→ ~20% improvement
Or we can leave the small subarrays unsorted and sort them at last using insertion sort

• estimate median by sampling 3 items

→ 10% improvement

2. Selection

Goal: given un array, find the kth largest item.

• Upper bound for this problem: NlgN (just sort the array)
• for small k (ex k=1,2,3), the upper bound is N (one-pass/two-pass)
• Lower bound is N: at least have to look at everything

Quick select

Algo proposed also by Hoare:

1. partition the array into two arrays left of pivot and right of pivot.
2. if pivot==k: return
3. continue the partition for just one of the subarrays

类似于二分查找的过程....
注意这里是不用递归的! 因为partition函数返回的直接就是pivot在整个数组里的位置!

Implementation

privater static int partition(Comparable[] a, int lo, int hi){...}

public static Comparable select(Comparable[] a, int k){   
    StdRandom.shuffle(a);   
    int lo=0,hi=a.length-1;   
    while(true){   
        int j = partition(a,lo,hi);   
        if(j<k) lo=j+1;   
        if(j==k) return a[j];   
        else hi=j-1;   
        if(hi<=lo) break;   
    }   
    return a[k];//这里不太理解为什么会在hi<lo的时候直接返回a[k]   
}

Analysis

Proposition **
Quick selection takes linear* time on average.
proof *
intuitively, each partition will ct the subarray size in half:
N+N/2+N/4+... = 2N
formal analysis 略...

worst case: quadratic (but very rare to happen)

Theoretical results

3. Duplicate keys

if array contains many duplicate keys.

• huge array
• small number of distinct keys

**for mergesort **
insensitive... always ~NlgN compares.

for quicksort **
Will get quadratic time if not stop on equal keys. (found in 1990s)
mistake: put all items equal to pivot *to just one side *
→ N^2 compares if all keys are equal from lo to hi.
correct: put all items equal to pivot in their final place.

3-way partitionning

(by Dijkstra)
partition the array into 3 parts:

Dijkstra's 3-way partition algo:
使用3个指针: lt指向中间部分的左边界, gt指向右边界; i指针从左向右扫描, 算法很subtle:

• lt=lo, gt=hi, i=lo
• if a[i]==v : i++
• if a[i]<v: exch(i,lt), i++, lt++
• if a[i]>v: exch(i,gt), gt--
• repeat until i and gt cross (i>gt)

invariance:

• [lo, lt) all < v
• [lt, i) all == v
• (gt, hi] all >v

Implementation: 3-way quick sort

不必再写partition函数, 直接在sort递归函数里面.

private static void sort(Comparable[] a, int lo, int hi){   
    if(hi<=lo) return; // 递归函数别忘了先写终止条件...   
    int lt=lo, gt = hi;   
    Comparable v = a[lo];   
    for(int i=lo;i<=gt;){ //不能写 i++   
        if( less(a[i],v) )   
            exch(a, i++, lt++);   
        else if ( less(v,a[i]) )   
            exch(a,i,gt--);   
        else // v==a[i]   
            i++;   
    }   
    sort(a, lo, lt-1);   
    sort(a, gt+1, hi);  
}

当N个数有很多重复的时候, lower bound可以变小于NlgN:

And Sedgewick proved that the 3-wy partition is propotional to the lower bound....

4. System Sorts

Arrays.sort() in java:

import java.util.Arrays;

quicksort for primitive arrays, mergesort for objects: java设计者认为如果用obj array表示空间不是问题...

Pb in java's system sort: killer input exsit (havn't shuffle)...

总结一下学过的5/6种排序: