QuickSort Review

This is a review about QuickSort by CLRS#3 & Algorithm#4.

Complexity

• Best: O(nlgn)
• Average: O(nlgn) random inputs
• Bad: O(n^2) sorted inputs, repeat inputs

<CLRS#3>

sort(A,1,A.length)

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

partition(A,p,r):
    x = A[r]
    i = p-1
    for j = p to r-1:
        if A[j] <= x:
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i+1

<Algorithm#4>

sort(A,1,A.length)

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

partition(A,p,r):
    x = A[p]
    i = p
    j = r+1
    while i < j
        while A[i] < x
            i = i+1
            if i == r
                break
        while A[j] > x
            j = j-1
            if j == p
                break
        exchange A[i] with A[j]
    exchange A[j] with A[p]
    return j

Optimization

1. Change to Insertion-Sort while sub-array’s item less than 5~15
2. Quick partition: Find middle item and set size 3 to make partition.
3. Dijkstra: [Quick3Way] for repeat inputs. Best O(N). Bad O(NlgN)

   Quick3Way

   sort(A,1,A.length)
   
   sort(A,p,r):
       if p < r
           // [p,lt) <= [lt,gt) <= [gt,r]
           lt = p
           gt = r
           i = p+1
           x = a[p]
           while i <= gt
               if A[i] < p
                   exchange A[lt] with A[i]
                   lt = lt+1
                   i = i+1
               else if A[i] > p
                   exchange A[i] with A[gt]
                   gt = gt-1
               else
                   i = i+1
       sort(A,p,lt-1)
       sort(A,gt+1,r)