Sorting algorithms/Bubble sort: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 207: Line 207:
return self
return self
end
end
end


class Array
def bubblesort!
def bubblesort!
each_index do |index|
each_index do |index|
Line 221: Line 223:


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

Revision as of 17:11, 25 January 2007

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

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;

Template:Array operation

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]