• Home
• Contact

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

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