Quick Sort

Posted on

Method:

  • The key process in QuickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Choose Pivot

  • Pick first element as pivot.
  • Pick last element as pivot.
  • Pick a random element as pivot.
  • Pick median as pivot.

Python Code for QuickSort function:

def quick_sort(A, l, r):
    # only one element
    if l >= r:
        return
    
    # choose median as pivot
    pivot = A[(l + r) >> 1]
    i, j = l - 1, r + 1
    
    while i < j:
        i += 1
        while A[i] < pivot:
            i += 1
        j -= 1
        while A[j] > pivot:
            j -= 1
        if i < j:
            A[i], A[j] = A[j], A[i]
    
    quick_sort(A, l, j)
    quick_sort(A, j + 1, r)

C++ Code for QuickSort function:

void quick_sort(int A[], int l, int r)
{
    // only one element
    if (l >= r) return;

    // choose median as pivot
    int pivot = A[l + r >> 1];
    int i = l - 1, j = r + 1;

    while (i < j)
    {
        do i ++ ; while (A[i] < pivot);
        do j -- ; while (A[j] > pivot);
        if (i < j) swap(A[i], A[j]);
    }
    
    quick_sort(A, l, j);
    quick_sort(A, j + 1, r);
}

Idea:

  1. Choose median element as pivot.
  2. Using two pointers, left pointer points to the most left element - 1; right pointer points to the most right element + 1.
  3. left pointer move from left to right, until the element is great or equal then pivot;
    right pointer move from right to left, until the element is less or equal then pivot.
  4. swap() the value of two pointers points to.
  5. Repeat 3 & 4 until left < right is no longer true.
  6. Repeat 1 – 4 for two sub-lists.

Other:

Reference: