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.
The bubble sort is generally considered to be the simplest sorting algorithm. Because of its simplicity and ease of visualization, it is often taught in introductory computer science courses. Because of its abysmal O(n2) performance, it is never used anywhere else.
The bubble sort works by passing sequentially over a list, comparing each value to the one immediately after it. If the first value is greater than the second, their positions are switched. Over a number of passes, at most equal to the number of elements in the list, all of the values drift into their correct positions (large values "bubble" rapidly toward the end, pushing others down around them). Because each pass finds the maximum item and puts it at the end, the portion of the list to be sorted can be reduced at each pass. A boolean variable is used to track whether any changes have been made in the current pass; when a pass completes without changing anything, the algorithm exits.
This can be expressed in pseudocode as follows (assuming 1-based indexing):
repeat set hasChanged to false decrement itemCount repeat with index from 1 to itemCount if (item at index) > (item at (index + 1)) swap (item at index) with (item at (index + 1)) set hasChanged to true until hasChanged is false
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;
ALGOL 68
MODE DATA = INT; PROC swap = (REF[]DATA slice)VOID: ( DATA tmp = slice[1]; slice[1] := slice[2]; slice[2] := tmp ); PROC sort = (REF[]DATA array)VOID: ( BOOL sorted; INT shrinkage := 0; FOR size FROM UPB array - 1 BY -1 WHILE sorted := TRUE; shrinkage +:= 1; FOR i FROM LWB array TO size DO IF array[i+1] < array[i] THEN swap(array[i:i+1]); sorted := FALSE FI OD; NOT sorted DO SKIP OD ); main:( [10]INT random := (1,6,3,5,2,9,8,4,7,0); printf(($"Before: "10(g(3))l$,random)); sort(random); printf(($"After: "10(g(3))l$,random)) )
Output:
Before: +1 +6 +3 +5 +2 +9 +8 +4 +7 +0 After: +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
BASIC
Compiler: QuickBasic 4.5
Assume numbers are in a DIM of size "size" called "nums".
FOR I = 1 TO size - 1 FOR J = I + 1 TO size IF nums(I) > nums(J) THEN tmp = nums(I) nums(I) = nums(J) nums(J) = tmp END IF NEXT J NEXT I
C
void swap(int *p) { int t = p[0]; p[0] = p[1]; p[1] = t; } void sort(int *a, int size) { int i,sorted; do { sorted = 1; --size; for (i=0; i<size; i++) if (a[i+1] < a[i]) { swap(a+i); sorted = 0; } } while (!sorted); }
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 ; }
Clean
Bubble sorting an array in-situ (using destructive updates), using Clean's uniqueness typing. We specified the type of sweep using strictness annotations to improve performance.
import StdEnv bsort :: *(a e) -> *(a e) | Array a e & < e bsort array # (done, array) = sweep 1 True array = if done array (bsort array) where sweep :: !Int !Bool !*(a e) -> (!Bool, !*(a e)) | Array a e & < e sweep i done array | i >= size array = (done, array) # (e1, array) = array![i - 1] (e2, array) = array![i] | e1 > e2 = sweep (i + 1) False {array & [i - 1] = e2, [i] = e1} = sweep (i + 1) done array
Using it to sort an array of a hundred numbers:
Start :: {Int} Start = bsort {x \\ x <- [100,99..1]}
D
Compiler: DMD 1.025
module BubbleSort; import std.stdio; void bubbleSort(T)(T[] array) { int itemCount = array.length; bool hasChanged; do { hasChanged = false; --itemCount; for (int index = 0; index < itemCount; ++index) { if (array[index] > array[index + 1]) { T temp = array[index]; array[index] = array[index + 1]; array[index + 1] = temp; hasChanged = true; } } } while (hasChanged); } void main() { // array literal auto array = [ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ] ; // member function invocation syntax for arrays array.bubbleSort(); foreach (index, value; array) { writefln("array[%d] = %d", index, value); } }
E
def bubbleSort(target) { __loop(fn { var changed := false for i in 0..(target.size() - 2) { def [a, b] := target(i, i + 2) if (a > b) { target(i, i + 2) := [b, a] changed := true } } changed }) }
(Uses the primitive __loop directly because it happens to map to the termination test for this algorithm well.)
Forth
Sorts the 'cnt' cells stored at 'addr' using the test stored in the deferred word 'bubble-test'. Uses forth local variables for clarity.
defer bubble-test ' > is bubble-test : bubble { addr cnt -- } cnt 1 do addr cnt i - cells bounds do i 2@ bubble-test if i 2@ swap i 2! then cell +loop loop ;
This is the same algorithm done without the local variables:
: bubble ( addr cnt -- ) dup 1 do 2dup i - cells bounds do i 2@ bubble-test if i 2@ swap i 2! then cell +loop loop ;
Version with O(n) best case:
: bubble ( addr len -- ) begin 1- 2dup true -rot ( sorted addr len-1 ) cells bounds ?do i 2@ bubble-test if i 2@ swap i 2! drop false ( mark unsorted ) then cell +loop ( sorted ) until 2drop ;
Test any version with this:
create test 8 , 1 , 4 , 2 , 10 , 3 , 7 , 9 , 6 , 5 , here test - cell / constant tcnt test tcnt cells dump ' > is bubble-test test tcnt bubble test tcnt cells dump ' < is bubble-test test tcnt bubble test tcnt cells dump
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
Java
Bubble sorting (ascending) an array of any Comparable type:
for(int a = 0; a < comparable.length - 1; a++){ for(int b = a + 1; b < comparable.length; b++){ if(comparable[a].compareTo(comparable[b]) > 0){ int tmp = comparable[a]; comparable[a] = comparable[b]; comparable[b] = tmp; } } }
For descending, simply switch the direction of comparison:
if(comparable[a].compareTo(comparable[b]) < 0){ //same swap code as before }
JavaScript
Array.prototype.bubblesort = function() { var done = false; while (!done) { done = true; for (var i = 1; i<this.length; i++) { if (this[i-1] > this[i]) { done = false; [this[i-1], this[i]] = [this[i], this[i-1]] } } } return this; }
MAXScript
fn bubbleSort arr = ( while true do ( changed = false for i in 1 to (arr.count - 1) do ( if arr[i] > arr[i+1] then ( swap arr[i] arr[i+1] changed = true ) ) if not changed then exit ) arr ) -- Usage myArr = #(9, 8, 7, 6, 5, 4, 3, 2, 1) myArr = bubbleSort myArr
Perl
# 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){ if ($_[$j] lt $_[$i]) { @_[$i, $j] = @_[$j, $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; while ($done == 0) { $done = 1; $elements--; for (my $i = 0; $i < $elements; $i++) { if ($list[$i] > $list[$i + 1]) { $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));
Pop11
define bubble_sort(v); lvars n=length(v), done=false, i; while not(done) do true -> done; n - 1 -> n; for i from 1 to n do if v(i) > v(i+1) then false -> done; ;;; Swap using multiple assignment (v(i+1), v(i)) -> (v(i), v(i+1)); endif; endfor; endwhile; enddefine; ;;; Test it vars ar = { 10 8 6 4 2 1 3 5 7 9}; bubble_sort(ar); ar =>
Python
def bubble_sort(seq): while 1: changed = 0 for i in xrange(len(seq) - 1): if seq[i] > seq[i+1]: seq[i], seq[i+1] = seq[i+1], seq[i] changed = 1 if not changed: break
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]
Seed7
const proc: bubbleSort (inout array integer: arr) is func local var integer: i is 0; var integer: j is 0; var integer: help is 0; begin for i range 1 to length(arr) do for j range succ(i) to length(arr) do if arr[i] < arr[j] then help := arr[i]; arr[i] := arr[j]; arr[j] := help; end if; end for; end for; end func;
var array integer: arr is [] (3, 78, 4, 23, 6, 8, 6);
bubbleSort(arr);
Toka
Toka does not have a bubble sort predefined, but it is easy to code a simple one:
#! A simple Bubble Sort function value| array count changed | [ ( address count -- ) to count to array count 0 [ count 0 [ i array array.get i 1 + array array.get 2dup > [ i array array.put i 1 + array array.put ] [ 2drop ] ifTrueFalse ] countedLoop count 1 - to count ] countedLoop ] is bsort #! Code to display an array [ ( array count -- ) 0 swap [ dup i swap array.get . ] countedLoop drop cr ] is .array #! Create a 10-cell array 10 cells is-array foo #! Fill it with random values 20 1 foo array.put 50 2 foo array.put 650 3 foo array.put 120 4 foo array.put 110 5 foo array.put 101 6 foo array.put 1321 7 foo array.put 1310 8 foo array.put 987 9 foo array.put 10 10 foo array.put #! Display the array, sort it, and display it again foo 10 .array foo 10 bsort foo 10 .array