programming / C++ / sailing / nerd stuff
Algorithm: Quick Sort

## 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
• 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))$