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.
#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);
}
