### Super Bubble Sort Contest

So we all know bubble sorts are a slow way to sort a list. There has already been a forum post on this. Being so, this is the perfect opportunity for this contest. You are to use any language(as long as it fits the requirements) to right a bubble sort algorithm to sort a list of one thousand items 1-1000 in descending order. The requirements are as follows:

 ``` 1. Target Windows 32-bit compiled exe executable 2. Language any that can compile to the above format 3. When completed, post here with the following format ```

Format:
language
compiler [flags used]

After that, create a zip file with both executable and source. Upload it here: http://www.filehosting.org/ and set the email as jamesmp98@gmail.com

Have Fun ;)
Last edited on
Uh, aren't there only like two variations to the bubble sort? Kind of a pointless competition...
ResidentBiscuit wrote:
aren't there only like two variations to the bubble sort
Bubblesort, shaker sort, even-odd sort, comb sort.
Each of those can be implemented naively or optimized.
isn't going to be easier to put the source here since it's just for fun?
also people who don't want to participate can see the code and learn sth
or at least sending it to your account (pm you)
You never stated what the contest is for. Is it to write the fastest solution?
Is it to write the slowest solution?
Last edited on
It would be easy enough to write a slower bubble sort, but a faster one would be interesting.

The problem you have to overcome is the 50% branch prediction failure rate for each of those n² comparisons.

Basic bubblesort with two optimizations:

 `` `` ``#include ``
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162`` `````` //-------------------------------------------------------------------------- // bubble_sort //-------------------------------------------------------------------------- template bool iter_swap_if( Iterator a, Iterator b, Predicate& f ) { bool result = f( *a, *b ); if (result) std::iter_swap( a, b ); return result; } template void bubble_sort( Iterator begin, Iterator end, Compare compare ) { bool any = true; while (any and (begin != end--)) { any = false; for (Iterator i = begin; i != end; ++i) any |= iter_swap_if( i + 1, i, compare ); } } template void bubble_sort( Iterator begin, Iterator end ) { bubble_sort( begin, end, std::less ::value_type> () ); } //-------------------------------------------------------------------------- // bidirectional_bubble_sort //-------------------------------------------------------------------------- template void bidirectional_bubble_sort( Iterator begin, Iterator end, Compare compare ) { bool any = true; while (any) { any = false; if (begin != end--) { for (Iterator i = begin; i != end; ++i) any |= iter_swap_if( i + 1, i, compare ); } if (any and (begin++ != end)) { for (Iterator i = end; i-- != begin; ) any |= iter_swap_if( i, i - 1, compare ); } } } template void bidirectional_bubble_sort( Iterator begin, Iterator end ) { bidirectional_bubble_sort( begin, end, std::less ::value_type> () ); }``````

(I think that covers it. 'Twas chopped from a larger collection of STL sorting algorithms I wrote.)

1000 elements is too small to time usefully, so I did 100,000 elements, randomized using the standard Mersenne Twister 19937 in <random>.

 ```ALGORITHM FASTEST TIME IN SECONDS bubble 20.543 bidirectional-bubble 15.911 counting 0.106 heap 0.013 insertion 1.416 introsort 0.018 merge 0.345 quick 0.019```

Notice that the only other n² algorithm (insertion sort) outperforms bubble by factors of 14.5 and 11.2 respectively.

Oh, and here's reference for that:

 ``123456789101112131415161718192021222324`` `````` //-------------------------------------------------------------------------- // insertion sort //-------------------------------------------------------------------------- template void insertion_sort( Iterator begin, Iterator end, Compare compare ) { if (begin != end) for (Iterator i = begin, i0 = ++i; i != end; ) { i0 = i++; std::rotate( std::upper_bound( begin, i0, *i0, compare ), i0, i ); } } template inline void insertion_sort( Iterator begin, Iterator end ) { insertion_sort( begin, end, std::less ::value_type> () ); }``````

Enjoy!
O(n) "sorting" algorithm:
 ``12345678910111213141516171819`` ``````#include #include #include #include template > void dropsort(T& cont, P pred = P()) { cont.erase(std::unique(cont.begin(), cont.end(), std::not2(pred)), cont.end() ); } int main( ) { std::vector arr = {0, 2, 1, 4, 3, 6, 5, 7, 9, 8}; dropsort(arr); std::cout << std::is_sorted(arr.begin(), arr.end()); }``````
http://ideone.com/yK1Vyx
Beat it :)
Last edited on
Topic archived. No new replies allowed.