Various ways of implementing bubble sort?

Question

How should I implement the classic bubble sort algorithm? I'd particularly like to see a C++ implementation, but any language (even pseudocode) would be helpful.

P.S. Not a homework.

Answer 1

Here is an implementation of bubble sort in c and one in c++. And here is an implementation in pseudocode.

Answer 2

Wikipedia provides two pseudocode implementations of the bubble sort:

procedure bubbleSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length(A) - 1 inclusive do:
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        swapped := true
      end if
    end for
  while swapped
end procedure

and

procedure bubbleSort( A : list of sortable items ) defined as:
  n := length( A )
  do
    swapped := false
    for each i in 0 to n - 1  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
    n := n - 1
  while swapped
end procedure

Answer 3

Wikipedia actually covers most of the fundamental algorithms rather well, and google knows everything, so, without being snarky, those really are good places to start.

You can get extra credit by implementing the only-slightly-more-complicated but much superior cocktail sort. Don't actually use either one in a real program, though.

Answer 4

http://www.sorting-algorithms.com/ contains a number of algorithms, examples, and pseudocode.

Answer 5

There are 59 implementations in different languages at rosettacode.com at the moment of this writing.

This is the great algorithm to implement in different languages, recently I've tried to implement it in J, and I suspected there can be a shorter implementation (though I haven't created my own yet). It allows you to find out which means language provides you to solve different kind of problems. So before watching on real examples try to implement your own version, I'm sure you'll like it.

Answer 6

Here's a hastily written C# (and could be Java) version. I'm sure it could be improved, and I've avoided LINQ so you can convert it.

int[] items = {1,2,5,2,5,9,2,3};
int[] sorted =  (int[]) items.Clone();

for (int i =0;i < items.Length -1;i++)
{
    for (int j=0;j < items.Length -1;j++)
    {
        if (sorted[j] > sorted[j+1])
        {
            int item = sorted[j];
            sorted[j] = sorted[j +1];
            sorted[j+1] = item;
        }   
    }
}

foreach (int number in sorted)
{
    Console.WriteLine(number);
}