Shaker Sort

Everyone who has ever programmed a sort has probably done a Bubble sort (and hopefully lived to tell about it). The truth is is that bubble sorts are incredibly simple. But they do have worst cases, such as a reverse ordered list of items. It would take bubble sort order n^2 time to complete any semi-reverse ordered items. Shaker sorts can help resolve this problem.

Generally bubble sorts move from one end of a list of items to the next. Shaker sorts move from one end of the list to the next and then from the other end of the list to the beginning. Pretty straight forward? Well you can write up a C bubble sort in about 6 lines of code. Shaker sorts take a little bit more, and are a little more complicated, but well worth the study.

Here is a C based example of a shaker sort.

#include

#define key(A) (A)

#define less(A, B) (key(A) <>

#define exch(A, B) {int t = A; A = B; B = t;}

#define compexch(A, B) if(less(B, A)) exch(A, B)

void shaker(int *, int, int);

int main(){

int array[10] = {4, 1, 7, 3, 2, 8, 9, 6, 5};

shaker(array, 0, 9);

int i;

for(i = 1; i < 10; i++){

printf("%d ", array[i]);

}

return 0;

}

void shaker(int *array, int l, int r){

int sorted = 1, i, swaps = 0; // Define two integers. Initialize sorted to 1. Sorted will terminate the while loop if nothing has been sorted.

while(sorted){

sorted = 0; // Always set sorted to 0 just to make sure we can continually test to see if it has been sorted

for(i = l; i <>// This loop will be the left-to-right swapping

if(less(array[i], array[i - 1])){ // Check adjacent elements to see if i is less than  i - 1. Swap them if they are.

exch(array[i - 1], array[i]);

sorted = 1; // Sorted will be set to 1 to make sure we either continue looping or don't.

swaps++;

}

if(sorted == 0) break; // An extra text but it will terminate the function if it is already sorted.

}

for(i = r; i > 0; i--){ // This loop will be the right-to-left swapping

if(less(array[i], array[i - 1])){ // Check adjacent elements to see if i is less than  i - 1. Swap them if they are.

exch(array[i - 1], array[i]); 

sorted = 1; // Sorted will be set to 1 to make sure we either continue looping or don't.

swaps++;

}

if(sorted == 0) break;

}

}

printf("\nIt took a total of %d exchanges to sort the list.\n", swaps);

}