With standard BubbleSort, you're pretty much guaranteed O(n^2) running time. If I'm doing my math right, the number of swaps, in worst case, is also n^2. This is, by all accounts, a pretty crappy algorithm. Yeah, you can get down to O(n^2 / 2), but really, on a big enough list, it's just not very good.

My dad mentioned a variation he's come to rely on, invented by his good friend Dan Stover, which uses standard bubble sort logic (compare a to b, swap if a > b), but starts with an n/2-width span. For example, given an array A of size 10, it first compares A[0] to A[5], then A[1] to A[6], etc. until A[size - span - 1] to A[span - 1]. If any swaps were made, it goes through again at the same span. Once no swaps are made, the span halves, and the comparison loop runs again. This continues until no swaps are made at span size 1 (same as the original BubbleSort's base case).

void bubbleSpanSort(int A[], int size) { if (size < 2) { return; //an array of size 0 or 1 is already 'sorted' } int span = ( size ); //this is to ensure the first span is 1/2 the size... bool swapMade = false; do { //if no swaps were made, and the span could be smaller... if (!swapMade && span > 1) { span = span / 2; } //reset each cycle swapMade = false; for (int i = 0; i < (size - span); i++) { if ( A[i] > A[i+span] ) { swap( A, i, (i+span) ); //standard swap implementation swapMade = true; numSwaps++; } } } while (swapMade || span > 1); //done! }

If you'd like to check it out, I posted a running example on Runnable.com. While still in beta, I'm really digging their site!

Cheers,

Steve