Super Bubble Sort Contest

[James Parsons]

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]
linker(if any) [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 [e-mail]

Have Fun ;)

[ResidentBiscuit]

Uh, aren't there only like two variations to the bubble sort? Kind of a pointless competition...

[MiiNiPaa]

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.

[AkramIzzeldin]

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)

[xismn]

You never stated what the contest is for. Is it to write the fastest solution?

[Lachlan Easton]

Is it to write the slowest solution?

[Duthomhas]

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 <algorithm> 

  //--------------------------------------------------------------------------
  // bubble_sort
  //--------------------------------------------------------------------------

  template <typename Iterator, typename Predicate>
  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 <typename Iterator, typename Compare>
  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 <typename Iterator>
  void bubble_sort( Iterator begin, Iterator end )
    {
    bubble_sort( begin, end,
      std::less <typename std::iterator_traits <Iterator> ::value_type> () );
    }


  //--------------------------------------------------------------------------
  // bidirectional_bubble_sort
  //--------------------------------------------------------------------------

  template <typename Iterator, typename Compare>
  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 <typename Iterator>
  void bidirectional_bubble_sort( Iterator begin, Iterator end )
    {
    bidirectional_bubble_sort( begin, end,
      std::less <typename std::iterator_traits <Iterator> ::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:

  //--------------------------------------------------------------------------
  // insertion sort
  //--------------------------------------------------------------------------

  template <typename Iterator, typename Compare>
  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 <typename Iterator> inline
  void insertion_sort( Iterator begin, Iterator end )
    {
    insertion_sort(
      begin,
      end,
      std::less <typename std::iterator_traits <Iterator> ::value_type> ()
      );
    }

Enjoy!

[MiiNiPaa]

O(n) "sorting" algorithm:

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

template <class T, typename P = std::less<typename T::value_type>>
void dropsort(T& cont, P pred = P())
{
    cont.erase(std::unique(cont.begin(), cont.end(), std::not2(pred)),
               cont.end()
              );
}

int main( )
{
    std::vector<int> 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 :)