Sorting algorithms/Bubble sort: Difference between revisions
m (→[[Ada]]: Add generic function parameter "=") |
(added Haskell) |
||
Line 105: | Line 105: | ||
std::cout << std::endl ; |
std::cout << std::endl ; |
||
} |
} |
||
==[[Haskell]]== |
|||
[[Category: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 <tt>Maybe</tt> type to designate unchanged lists. (The type signature of <tt>_bsort</tt> is now <tt>Ord a => [a] -> Maybe [a]</tt>.) 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]]== |
==[[Perl]]== |
Revision as of 23:30, 28 January 2007
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:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) 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 <>; 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));
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. 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]