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:
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 <>; 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!
- => [3, 4, 6, 6, 8, 23, 78]