Sorting algorithms/Bubble sort: Difference between revisions
Line 113: | Line 113: | ||
This sort is actually a C quicksort. |
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 sort! method to the Array object, making it readily available for all Array objects |
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 sort! method to the Array object (overwriting the already existing sort! method), making it readily available for all Array objects |
||
class Array |
class Array |
||
def sort! |
def sort! |
Revision as of 23:06, 22 January 2007
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;
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.
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 sort! method to the Array object (overwriting the already existing sort! method), making it readily available for all Array objects
class Array def sort! (length-1).downto(0) do |nrSwaps| nrSwaps.times do |ix| self[ix],self[ix+1]=self[ix+1],self[ix] if self[ix]>self[ix+1] end end return self end end ary = [5,4,2,3,1] puts ary.sort!