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

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.

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

Cmin=n1C_{min} = n - 1

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

O(n2)O(n^2)