mario::konrad
programming / C++ / sailing / nerd stuff
Algorithm: Quick Sort
© 2005 / Mario Konrad

Description

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

Notes:

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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))O(n * log(n))

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

O(n2)O(n^2)

Typical case:

O(n*log(n))O(n * log(n))