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{cases} 9\cdot 4^i - 9\cdot 2^i+1, \quad i\mod 2 == 0\\ 4^{i+1}-6 \cdot 2^i+1, \quad i\mod 2 == 1 \end{cases} \]

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{align*} T(n)=T(1)+T(n-1)+\Theta(n) \end{align*} \]

• Best sequence

\[ T(n)=2T(n/2)+\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 \(\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!\leq 2^h \]

"=" holds for complete binary decision tree. So

\[ h\geq \log{n!} \geq \log{(n/e)^n} =\Omega(n\log{n}) \]