• Home
• Contact

Description

Strategy: split and rule. Array gets splitted into two parts which will separatly sorted recursively. There are many criteria to split the array:

• array[ (left + right) / 2 ]
• array[ left ]
• array[ right ]
• median of three elements from the array in the interval [left, right]
• median of the smallest and greatest element within the array
• etc.

Notes:

• quick sort is in typical case just 40% worse as in best case
• additional memory required
• not stable

Algorithm

void qsort(Array & array, int left, int right)
{
    if (left < right)
    {
        int m = array[(left + right) / 2];
        int i = left;
        int j = right;

        while (i <= j) {
            while (array[i] < m) ++i;
            while (array[j] > m) --j;
            if (i <= j) {
                array.swap( i, j );
                ++i;
                --j;
            }
        }
        if (left < j) qsort( array, left, j );
        if (i < right) qsort( array, i, right );
    }
}

Analysis

Best case: median splits array in two parts of equal size:

⇒ $O(n * log(n))$

Worst case: median splits array in two parts of lengths 1 and n-1 (number of recusive calls: $n - 1$)

⇒ $O(n^2)$

Typical case:

⇒ $O(n * log(n))$