Sorting

• 效率 | Efficiency

• 原地性 | In Place

• 稳定性 | Stability

A sorting algorithm is stable if elements with equal elements are left in the same order as they occur in the input.

A stable algorithm can be suitable for Multiple targets.

Insertion Sort

Shell Sort

$h_t$ = $\lfloor N/2\rfloor$, $h_k$ = $\lfloor h_{k+1}/2\rfloor$.

with Worst case $O(N^2)$

Now we have better selection with worst case $O(N^{7/6})$ with

$$h_k=\{\begin{array}{l}9\cdot 4^i-9\cdot 2^i+1,i\mathrm{mod}2==0\\ 4^{i+1}-6\cdot 2^i+1,i\mathrm{mod}2==1\end{array}$$

Heap Sort

Merge Sort

Quick Sort

• Picking the Pivot

• Partition

Partition

Partition(A, p, q)
    x=A[p]
    i=p+1
    j=q
    while(i!=j)
        while(A[j]>=x && i<j)
            j-- // put larger element in place 
        while(A[i]<=x && i<j)
            i++ // put smaller element in place 
        if(i<j)
            swap(A[i], A[j])
    swap(A[p], A[i])

Another Partition

Partition(A, p, q)
    x=A[p]
    i=p
    for j=p+1 to q:
        if(A[j]<=x)
            i=i+1
            swap(A[i],A[j])
    A[p]=A[i]
    return i

QuickSort

QuickSort(A,p,q)
    if(p<q)
        r=partition(A,p,q)
        QuickSort(A,p,r-1)
        QuickSort(A,r+1,q)

Time cost:

• Ordered sequence

$$\begin{array}{r}T(n)=T(1)+T(n-1)+\mathrm{\Theta }(n)\end{array}$$

• Best sequence

$$T(n)=2T(n/2)+\mathrm{\Theta }(n)$$

• not Bad or Good

Every Partition gives 1:9 sequence

Randomize pivot

Text Only

Randomized_Partition(A,p,q)
    i=random(p,q)
    swap(A[p],A[i])
    return Partition(A,p,q)

Text Only

randomized_quicksort(A,p,q)
    if(p<q)
        r=randomized_Partition(A,p,q+1)
        randomized_quicksort(A,p,r-1)
        randomized_quicksort(A,r+1,q)

Some Details

• Consider repetitive elements

Text Only

Hoore_Partition(A,p,q)
    x=A[p]
    i=p, j=q+1
    while(1):
        do:
            j=j-1
        until(A[j]<=x)
        do:
            i=i+1
        until(A[i]>=x)
        if(i<j)
            swap(A[i],A[j])
        else
            swap(A[p],A[j])
            return j

A General Lower Bound for Sorting

Efficiency of sorting with comparing

The best efficiency of sorting based on comparing is $\mathrm{\Theta }(n\log n)$

Proof

left tree denotes true, right tree denotes false, every leaf node represents a result of sorting. We have $n!$ nodes. And let h denote the height of the decision tree. we have

$$n!\le 2^h$$

"=" holds for complete binary decision tree. So

$$h\ge \log n!\ge \log (n/e{)}^n=\mathrm{\Omega }(n\log n)$$