Sorting algorithms/Bubble sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 15:23, 31 January 2007

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 <>;
 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 ;
}

Haskell

This version checks for changes in a separate step for simplicity, because Haskell has no variables to track them with.

bsort :: Ord a => [a] -> [a]
bsort s = case _bsort s of
               t | t == s    -> t
                 | otherwise -> bsort t
  where _bsort (x:x2:xs) | x > x2    = x2:(_bsort (x:xs))
                         | otherwise = x:(_bsort (x2:xs))
        _bsort s = s

This version uses the polymorphic Maybe type to designate unchanged lists. (The type signature of _bsort is now Ord a => [a] -> Maybe [a].) It is slightly faster than the previous one.

bsort :: Ord a => [a] -> [a]
bsort s = case _bsort s of
               Nothing -> s
               Just s2 -> bsort s2
  where _bsort (x:x2:xs) | x > x2    = case _bsort (x:xs) of
                                            Nothing  -> Just $ x2:x:xs
                                            Just xs2 -> Just $ x2:xs2
                         | otherwise = case _bsort (x2:xs) of
                                            Nothing  -> Nothing
                                            Just xs2 -> Just $ x:xs2
        _bsort _ = Nothing

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));

Python

def bubblesort(seq):
    for i in xrange(1, len(seq)):
        for j in range(len(seq) - i):
            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]

Ruby

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. Below are two different methods that show four different iterating constructs in ruby.

 class Array
   def bubblesort1!
     length.times do |j|
       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

   def bubblesort2!
     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

 puts [3, 78, 4, 23, 6, 8, 6].bubblesort1!
 # => [3, 4, 6, 6, 8, 23, 78]

@@ Line 2: / Line 2: @@
 {{Sorting Algorithm}}
-In this task, the goal is to sort an array of elements using the [[Bubble Sort (algorithm)|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.
+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]]==