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

## Description

This sorting algorithm is a modification of the bubble sort algorithm. The algorithm remembers if a swap was necessary and where it was. It also sorts bi-directional.

• stable

## Algorithm

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` ``````int left = 0; int right = array.count()-1; int lastSwap = 0; while (left < right) { // smallest element towards left for (int i = right; i > left; --i) { if (array[i-1] > array[i]) { array.swap( i, i-1 ); lastSwap = i; // save index } } left = lastSwap; // greatest element towards right for (i = left; i < right; ++i) { if (array[i] > array[i+1]) { array.swap( i, i+1 ); lastSwap = i; // save index } } right = lastSwap; }``````

## Analysis

$C_{min} = n - 1$

$C_{avg} = ( n^2 + k * n - n * log( n ) ) / 2$

$O(n^2)$