Sorting algorithms/Bubble sort

Sorting algorithms/Bubble sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

In this task, the goal is to sort an array of elements using the bubble sort algorithm. The elements must have a total order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.

Ada

Compiler: GCC 4.1.2

generic
 type Element is private;
 with function "<" (E1, E2 : Element) return Boolean is <>;
 type Index is (<>);
 type Arr is array (Index range <>) of Element;
procedure Bubble_Sort (A : in out Arr);

procedure Bubble_Sort (A : in out Arr) is
 Finished : Boolean;
 Temp     : Element;
begin
 loop
  Finished := True;
  for J in A'First .. Index'Pred (A'Last) loop
   if A (Index'Succ (J)) < A (J) then
    Finished := False;
    Temp := A (Index'Succ (J));
    A (Index'Succ (J)) := A (J);
    A (J) := Temp;
   end if;
  end loop;
  exit when Finished;
 end loop;
end Bubble_Sort;

--  Example of usage:
with Ada.Text_IO; use Ada.Text_IO;
with Bubble_Sort;
procedure Main is
 type Arr is array (Positive range <>) of Integer;
 procedure Sort is new
  Bubble_Sort
   (Element => Integer,
    Index   => Positive,
    Arr     => Arr);
 A : Arr := (1, 3, 256, 0, 3, 4, -1);
begin
 Sort (A);
 for J in A'Range loop
  Put (Integer'Image (A (J)));
 end loop;
 New_Line;
end Main;

C++

Compiler: g++ 4.0.2

#include <iostream>
#include <algorithm>

template< typename ARRAY_TYPE, typename INDEX_TYPE >
void
bubble_sort( ARRAY_TYPE array[], INDEX_TYPE size )
{
 bool done = false ;
 
 while( !done )
 {
  done = true ;
  for( INDEX_TYPE i = 0 ; i < size - 1 ; i++ )
  {
   if( array[i] > array[i+1] )
   {
    done = false ;
    ARRAY_TYPE temp = array[i+1] ;
    array[i+1] = array[i] ;
    array[i] = temp ;
   }
  }
 }
}

template< typename TYPE >
void
print( TYPE val )
{
 std::cout << val << " " ;
}

int
main( int argc, char* argv[] )
{
 int array[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 } ;
 bubble_sort( array, 10 ) ;
 std::for_each( &array[0], &array[10], print<int> ) ;
 std::cout << std::endl ;
 
 //But in real life...
 int data[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 } ;
 std::sort( data, data+10 ) ;
 std::for_each( data, data+10, print<int> ) ;
 std::cout << std::endl ;
}

Perl

Interpreter: perl 5.8.8

 # Sorts an array in place and returns a copy
 sub bubble_sort (@) {
     my $len = @_ - 1;
     for my $i (0..$len-1){
         for my $j ($i+1..$len){
             @_[$i,$j] = @_[$j,$i] if $_[$j] lt $_[$i];
         }
     }
     return @_;
 }

 # Usage
 @a = qw/G F C A B E D/; 
 bubble_sort(@a);

Alternate "Long Hand" Perl Method

  sub Bubble_Sort {
     my @list = @_;
     my $temp = 0;
     my $done = 0;
     my $elements = $#list + 1;
  
     while ($done == 0) {
        $done = 1;
        for (my $i=0;$i<$elements;$i++) {
           if ($list[$i] > $list[$i+1] && ($i + 1) < $elements) {
              $done = 0;
              $temp = $list[$i];
              $list[$i] = $list[$i+1];
              $list[$i+1] = $temp;
           }
        }
     }
  
     return @list;
  }

  #usage
  my @test = (1, 3, 256, 0, 3, 4, -1);
  print join(",",Bubble_Sort(@test));

Note: Of course, there's no need to implement bubble sort in Perl as it has sort built-in.

Python

def bubblesort(seq):
    for i in xrange(len(seq) - 2):
        for j in range(i, len(seq) - 1):
            if seq[j] > seq[j+1]:
                seq[j], seq[j+1] = seq[j+1], seq[j]

data = [3, 78, 4, 23, 6, 8, 6]
bubblesort(data)
print data # [3, 4, 6, 6, 8, 23, 78]

Python has a built in sort method, it's a quite modified Merge Sort called Timsort: http://py-stablesort.sourceforge.net/

>>> foo = [3, 5, 2, 6, 1]
>>> sorted(foo)
[1, 2, 3, 5, 6]
>>> foo
[3, 5, 2, 6, 1]
>>> foo.sort()
>>> foo
[1, 2, 3, 5, 6]

Ruby

Sorting can be done with the sort method

new_array = [3, 78, 4, 23, 6, 8, 6].sort
#=> [3, 4, 6, 6, 8, 23, 78]
# Sort on arbitrary criteria:
new_array = [3, 78, 4, 23, 6, 8, 6].sort {|a,b| a % 2 <=> b}
#=> [3, 78, 8, 4, 6, 23, 6]
# Sort and modify the current object to be sorted
ary = [3, 78, 4, 23, 6, 8, 6]
ary.sort! {|a,b| a % 2 <=> b}
#ary => [3, 78, 8, 4, 6, 23, 6]

This sort is actually a C quicksort.

Although the native Ruby sort method for Arrays if much faster (O(n*log(n)) versus O(n**2)), you can find a Ruby version of Bubble sort hereunder. It adds the bubblesort! method to the Array object. There are a couple of different ways to implement this in ruby.

class Array

 def bubblesort!
   for j in 0...length
     for i in 1...(length - j)
       if self[i] < self[i - 1]
         self[i], self[i - 1] = self[i - 1], self[i]
       end
     end
   end
   
   return self
 end

end

class Array

 def bubblesort!
   each_index do |index|
     (length - 1).downto( index ) do |i|
       a, b = self[i-1], self[i]
       a, b = b, a if b < a
     end
   end
   
   return self
 end

end

ary = [3, 78, 4, 23, 6, 8, 6] puts ary.bubblesort!

1. => [3, 4, 6, 6, 8, 23, 78]