/*-----------------------------------------------------------------------------*\ | File: BubbleSort.c | | Author: Christopher Niederauer | | Update: 2 / 5 / 99 | | | | Description: | | This popular algorythm has a constant big O. It is also very easy to | | implement. The swap macro here is about as fast as a swap gets, so use it | | wisely. Please do not distribute this code without this description. | *\-----------------------------------------------------------------------------*/ #define SWAP(_x,_y) _x ^= _y; _y ^= _x; _x ^= _y #define MAX 100 void BubbleSortNormal ( int []); void BubbleSortExtra ( int []); // This sorts an array of integers. Use this version for arrays are already // partly in order. The big O is mainly constant with minimal time going to // swapping the variables. void BubbleSortNormal ( int list [ MAX ]) { int pass, comparison; for ( pass = 1; pass < MAX; pass++ ) for ( comparison = 1; comparison <= MAX - pass; comparison++ ) if ( list [ comparison - 1 ] > list [ comparison ] ) SWAP (( list [ comparison ]), ( list [ comparison - 1 ])); } // This sorts an array of integers. With an extra variable to see if it's done, // the algorythm can be faster if the array is almost sorted. If the array is // not almost already sorted, this version can actually go a bit slower. void BubbleSortExtra ( int list [ MAX ]) { int pass, comparison, done; for ( pass = 1; pass < MAX; pass++ ) { for ( comparison = 1, done = true; comparison <= MAX - pass; comparison++ ) if ( list [ comparison - 1 ] > list [ comparison ] ) { SWAP (( list [ comparison ]), ( list [ comparison - 1 ])); done = false; } if ( done == true ) break; } }