Sorting algorithms/Bubble sort: Difference between revisions
Line 708: | Line 708: | ||
print(j) |
print(j) |
||
end |
end |
||
<lang> |
</lang> |
||
=={{header|Lucid}}== |
=={{header|Lucid}}== |
Revision as of 13:11, 6 December 2009
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 not used often for large (or even medium-sized) datasets.
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 hasChanged := 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)) hasChanged := true until hasChanged = false
ActionScript
<lang actionscript>public function bubbleSort(toSort:Array):Array { var changed:Boolean = false;
while (!changed) { changed = true;
for (var i:int = 0; i < toSort.length - 1; i++) { if (toSort[i] > toSort[i + 1]) { var tmp:int = toSort[i]; toSort[i] = toSort[i + 1]; toSort[i + 1] = tmp;
changed = false; } } }
return toSort; }</lang>
Ada
<lang ada>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;</lang>
ALGOL 68
<lang algol68>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))
)</lang> Output:
Before: +1 +6 +3 +5 +2 +9 +8 +4 +7 +0 After: +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
AutoHotkey
<lang AutoHotkey>var = ( dog cat pile abc ) MsgBox % bubblesort(var)
bubblesort(var) ; each line of var is an element of the array {
StringSplit, array, var, `n hasChanged = 1 size := array0 While hasChanged { hasChanged = 0 Loop, % (size - 1) { i := array%A_Index% aj := A_Index + 1 j := array%aj% If (j < i) { temp := array%A_Index% array%A_Index% := array%aj% array%aj% := temp hasChanged = 1 } } } Loop, % size sorted .= array%A_Index% . "`n" Return sorted
}</lang>
AWK
Sort the standard input and print it to standard output. <lang awk>{ # read every line into an array
line[NR] = $0
} END { # sort it with bubble sort
do { haschanged = 0 for(i=1; i < NR; i++) { if ( line[i] > line[i+1] ) {
t = line[i] line[i] = line[i+1] line[i+1] = t haschanged = 1
} } } while ( haschanged == 1 ) # print it for(i=1; i <= NR; i++) { print line[i] }
}</lang>
BASIC
Assume numbers are in a DIM of size "size" called "nums". <lang qbasic>DO
changed = 0 for I = 1 to size -1 IF nums(I) > nums(I + 1) THEN tmp = nums(I) nums(I) = nums(I + 1) nums(I + 1) = tmp changed = 1 END IF
LOOP WHILE(NOT changed)</lang>
C
<lang 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);
}</lang>
C++
<lang cpp>#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 ;
}</lang>
C#
<lang csharp>using System; using System.Collections.Generic;
namespace RosettaCode.BubbleSort {
public static class BubbleSortMethods { //The "this" keyword before the method parameter identifies this as a C# extension //method, which can be called using instance method syntax on any generic list, //without having to modify the generic List<T> code provided by the .NET framework. public static void BubbleSort<T>(this List<T> list) where T : IComparable { bool madeChanges; int itemCount = list.Count; do { madeChanges = false; itemCount--; for (int i = 0; i < itemCount; i++) { if (list[i].CompareTo(list[i + 1]) > 0) { T temp = list[i + 1]; list[i + 1] = list[i]; list[i] = temp; madeChanges = true; } } } while (madeChanges); } }
//A short test program to demonstrate the BubbleSort. The compiler will change the //call to testList.BubbleSort() into one to BubbleSortMethods.BubbleSort<T>(testList). class Program { static void Main() { List<int> testList = new List<int> { 3, 7, 3, 2, 1, -4, 10, 12, 4 }; testList.BubbleSort(); foreach (var t in testList) Console.Write(t + " "); } }
}</lang>
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. <lang clean>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</lang>
Using it to sort an array of a hundred numbers: <lang clean>Start :: {Int} Start = bsort {x \\ x <- [100,99..1]}</lang>
Clojure
Bubble sorts a Java ArrayList in place. Uses 'doseq' iteration construct with a short-circuit when a pass didn't produce any change, and within the pass, an atomic 'changed' variable that gets reset whenever a change occurs.
<lang lisp>(import 'java.util.ArrayList)
(defn bubble-sort
([arr] (bubble-sort compare arr)) ([cmp #^ArrayList arr] (letfn [(swap!
[i j] (let [t (.get arr i)] (doto arr (.set i (.get arr j)) (.set j t)))) (sorter [stop-i] (let [changed (atom false)] (doseq [i (range stop-i)] (if (> (cmp (.get arr i) (.get arr (inc i))) 0) (do (swap! i (inc i)) (reset! changed true)))) @changed))]
(doseq [stop-i (range (dec (.size a)) -1 -1)
:while (sorter stop-i)])
arr)))</lang>
Common Lisp
Bubble sort an sequence in-place, using the < operator for comparison if no comaprison function is provided <lang lisp>(defun bubble-sort (sequence &optional (compare #'<))
"sort a sequence (array or list) with an optional comparison function (cl:< is the default)" (loop with sorted = nil until sorted do (setf sorted t) (loop for a below (1- (length sequence)) do (unless (funcall compare (elt sequence a) (elt sequence (1+ a))) (rotatef (elt sequence a) (elt sequence (1+ a))) (setf sorted nil)))))</lang>
<lang lisp>(bubble-sort (list 5 4 3 2 1))</lang>
elt
has linear access time for lists, making the prior implementation of bubble-sort very expensive (although very clear, and straightforward to code. Here is an implementation that works efficiently for both vectors and lists. For lists it also has the nice property that the input list and the sorted list begin with the same cons
cell.
<lang lisp>(defun bubble-sort-vector (vector predicate &aux (len (1- (length vector))))
(do ((swapped t)) ((not swapped) vector) (setf swapped nil) (do ((i (min 0 len) (1+ i))) ((eql i len)) (when (funcall predicate (aref vector (1+ i)) (aref vector i)) (rotatef (aref vector i) (aref vector (1+ i))) (setf swapped t)))))
(defun bubble-sort-list (list predicate)
(do ((swapped t)) ((not swapped) list) (setf swapped nil) (do ((list list (rest list))) ((endp (rest list))) (when (funcall predicate (second list) (first list)) (rotatef (first list) (second list)) (setf swapped t)))))
(defun bubble-sort (sequence predicate)
(etypecase sequence (list (bubble-sort-list sequence predicate)) (vector (bubble-sort-vector sequence predicate))))</lang>
D
<lang d>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() {
auto array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1].dup;
// member function invocation syntax for arrays array.bubbleSort(); foreach (index, value; array) writefln("array[%d] = %d", index, value);
}</lang>
E
<lang 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 })
}</lang>
(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.
<lang forth>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 ;</lang>
This is the same algorithm done without the local variables:
<lang forth>: 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 ;</lang>
Version with O(n) best case: <lang forth>: 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 ;</lang>
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
Fortran
<lang fortran>SUBROUTINE Bubble_Sort(a)
REAL, INTENT(in out), DIMENSION(:) :: a REAL :: temp INTEGER :: i, j LOGICAL :: swapped = .TRUE. DO j = SIZE(a)-1, 1, -1 swapped = .FALSE. DO i = 1, j IF (a(i) > a(i+1)) THEN temp = a(i) a(i) = a(i+1) a(i+1) = temp swapped = .TRUE. END IF END DO IF (.NOT. swapped) EXIT END DO
END SUBROUTINE Bubble_Sort</lang>
Groovy
Solution: <lang groovy>def bubbleSort = { list ->
boolean swapped = true while (swapped) { swapped = false (1..<list.size()).each { boolean doSwap = (list[it - 1] > list[it]) swapped |= doSwap if (doSwap) { list[(it - 1)..it] = list[it..(it - 1)] } } } list
}</lang>
Test Program: <lang groovy>def list = [1,6,3,5,2,9,8,4,7,0] println list println bubbleSort(list)</lang>
Output:
[1, 6, 3, 5, 2, 9, 8, 4, 7, 0] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Haskell
This version checks for changes in a separate step for simplicity, because Haskell has no variables to track them with. <lang haskell>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</lang>
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. <lang haskell>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</lang>
J
<lang j>bubbleSort=: |. @: ((([ (>. , <.) {.@]) , }.@])/^:_)</lang>
Test program:
<lang j> ?. 10 $ 10 4 6 8 6 5 8 6 6 6 9
bubbleSort ?. 10 $ 10
4 5 6 6 6 6 6 8 8 9</lang>
For the most part, bubble sort works against J's strengths. However, once a single pass has been implemented as a list operation, ^:_
tells J to repeat this until the result stops changing.
Java
Bubble sorting (ascending) an array of any Comparable type: <lang java>do {
boolean changed = false; for (int a = 0; a < comparable.length - 2; a++) { if (comparable[a].compareTo(comparable[a + 1]) > 0) { int tmp = comparable[a]; comparable[a] = comparable[a + 1]; comparable[a + 1] = tmp; changed = true; } }
} while (!changed);</lang>
For descending, simply switch the direction of comparison: <lang java>if (comparable[a].compareTo(comparable[b]) < 0){
//same swap code as before
}</lang>
JavaScript
<lang 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;
}</lang>
<lang 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; var tmp = this[i - 1]; this[i - 1] = this[i]; this[i] = tmp; } } } return this;
}</lang>
Example: <lang javascript>var my_arr = ["G", "F", "C", "A", "B", "E", "D"]; my_arr.bubblesort(); print(my_arr);</lang>
Output:
A,B,C,D,E,F,G
Lisaac
<lang Lisaac>Section Header
+ name := BUBBLE_SORT;
- external := `#include <time.h>`;
Section Public
- main <- (
+ a : ARRAY[INTEGER];
a := ARRAY[INTEGER].create 0 to 100; `srand(time(NULL))`; 0.to 100 do { i : INTEGER; a.put `rand()`:INTEGER to i; };
bubble a;
a.foreach { item : INTEGER; item.print; '\n'.print; };
);
- bubble a : ARRAY[INTEGER] <- (
+ lower, size, t : INTEGER; + sorted : BOOLEAN; lower := a.lower; size := a.upper - lower + 1; { sorted := TRUE; size := size - 1; 0.to (size - 1) do { i : INTEGER; (a.item(lower + i + 1) < a.item(lower + i)).if { t := a.item(lower + i + 1); a.put (a.item(lower + i)) to (lower + i + 1); a.put t to (lower + i); sorted := FALSE; }; }; }.do_while {!sorted};
);</lang>
Lua
<lang Lua> function bubbleSort(A)
local itemCount=#A local hasChanged repeat hasChanged = false itemCount=itemCount - 1 for i = 1, itemCount do if A[i] > A[i + 1] then A[i], A[i + 1] = A[i + 1], A[i] hasChanged = true end end until hasChanged == false
end </lang>
Example: <lang lua> list = { 5, 6, 1, 2, 9, 14, 2, 15, 6, 7, 8, 97 } for i, j in pairs(list) do
print(j)
end </lang>
Lucid
[1] <lang lucid>bsort(a) = if iseod(first a) then a else
follow(bsort(allbutlast(b)),last(b)) fi where b = bubble(a); bubble(a) = smaller(max, next a) where max = first a fby larger(max, next a); larger(x,y) = if iseod(y) then y elseif x end; follow(x,y) = if xdone then y upon xdone else x fi where xdone = iseod x fby xdone or iseod x; end; last(x) = (x asa iseod next x) fby eod; allbutlast(x) = if not iseod(next x) then x else eod fi; end</lang>
M4
<lang M4>divert(-1)
define(`randSeed',141592653) define(`setRand',
`define(`randSeed',ifelse(eval($1<10000),1,`eval(20000-$1)',`$1'))')
define(`rand_t',`eval(randSeed^(randSeed>>13))') define(`random',
`define(`randSeed',eval((rand_t^(rand_t<<18))&0x7fffffff))randSeed')
define(`set',`define(`$1[$2]',`$3')') define(`get',`defn(`$1[$2]')') define(`new',`set($1,size,0)') dnl for the heap calculations, it's easier if origin is 0, so set value first define(`append',
`set($1,size,incr(get($1,size)))`'set($1,get($1,size),$2)')
dnl swap(<name>,<j>,<name>[<j>],<k>) using arg stack for the temporary define(`swap',`set($1,$2,get($1,$4))`'set($1,$4,$3)')
define(`deck',
`new($1)for(`x',1,$2, `append(`$1',eval(random%100))')')
define(`show',
`for(`x',1,get($1,size),`get($1,x) ')')
define(`for',
`ifelse($#,0,``$0, `ifelse(eval($2<=$3),1, `pushdef(`$1',$2)$4`'popdef(`$1')$0(`$1',incr($2),$3,`$4')')')')
define(`bubbleonce',
`for(`x',1,$2, `ifelse(eval(get($1,x)>get($1,incr(x))),1, `swap($1,x,get($1,x),incr(x))`'1')')0')
define(`bubbleupto',
`ifelse(bubbleonce($1,$2),0, `', `bubbleupto($1,decr($2))')')
define(`bubblesort',
`bubbleupto($1,decr(get($1,size)))')
divert deck(`a',10) show(`a') bubblesort(`a') show(`a')</lang>
Output:
17 63 80 55 90 88 25 9 71 38 9 17 25 38 55 63 71 80 88 90
Mathematica
A rule-based solution is only one line, for large lists this method is not optimal, not so because of the method but because of the usage of patterns in a rule based solution: <lang Mathematica>BubbleSort[input_] := input //. {a___, i_, j_, b___} /; OrderedQ[{j, i}] :> {a, j, i, b}</lang> Example: <lang Mathematica>BubbleSort[{10, 3, 7, 1, 4, 3, 8, 13, 9}]</lang> gives back: <lang Mathematica>{1, 3, 3, 4, 7, 8, 9, 10, 13}</lang>
MAXScript
<lang 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
)</lang>
-- Usage
<lang maxscript>myArr = #(9, 8, 7, 6, 5, 4, 3, 2, 1) myArr = bubbleSort myArr</lang>
Modula-3
<lang modula3>MODULE Bubble;
PROCEDURE Sort(VAR a: ARRAY OF INTEGER) =
VAR sorted: BOOLEAN; temp, len: INTEGER := LAST(a); BEGIN WHILE NOT sorted DO sorted := TRUE; DEC(len); FOR i := FIRST(a) TO len DO IF a[i+1] < a[i] THEN temp := a[i]; a[i] := a[i + 1]; a[i + 1] := temp; END; sorted := FALSE; END; END; END Sort;
END Bubble.</lang>
OCaml
Like the Haskell versions above:
This version checks for changes in a separate step for simplicity. <lang ocaml>let rec bsort s =
let rec _bsort = function | x :: x2 :: xs when x > x2 -> x2 :: _bsort (x :: xs) | x :: x2 :: xs -> x :: _bsort (x2 :: xs) | s -> s in let t = _bsort s in if t = s then t else bsort t</lang>
This version uses the polymorphic option type to designate unchanged lists. (The type signature of _bsort is now 'a list -> 'a list option.) It is slightly faster than the previous one. <lang ocaml>let rec bsort s =
let rec _bsort = function | x :: x2 :: xs when x > x2 -> begin match _bsort (x :: xs) with | None -> Some (x2 :: x :: xs) | Some xs2 -> Some (x2 :: xs2) end | x :: x2 :: xs -> begin match _bsort (x2 :: xs) with | None -> None | Some xs2 -> Some (x :: xs2) end | _ -> None in match _bsort s with | None -> s | Some s2 -> bsort s2</lang>
Octave
<lang octave>function s = bubblesort(v)
itemCount = length(v); do hasChanged = false; itemCount--; for i = 1:itemCount if ( v(i) > v(i+1) )
t = v(i); v(i) = v(i+1); v(i+1) = t; hasChanged = true;
endif endfor until(hasChanged == false) s = v;
endfunction</lang>
<lang octave>v = [9,8,7,3,1,100]; disp(bubblesort(v));</lang>
Perl
<lang 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 @_;
}</lang> <lang perl># usage @a = qw/G F C A B E D/; bubble_sort(@a);</lang>
Alternate "Long Hand" Perl Method
<lang perl>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;
}</lang> <lang perl># usage my @test = (1, 3, 256, 0, 3, 4, -1);
print join(",", Bubble_Sort(@test));</lang>
Pop11
<lang 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 =></lang>
PowerShell
<lang powershell>function bubblesort ($a) {
$l = $a.Length $hasChanged = $true while ($hasChanged) { $hasChanged = $false $l-- for ($i = 0; $i -lt $l; $i++) { if ($a[$i] -gt $a[$i+1]) { $a[$i], $a[$i+1] = $a[$i+1], $a[$i] $hasChanged = $true } } }
}</lang>
Python
<lang python>def bubble_sort(seq):
"""Inefficiently sort the mutable sequence (list) in place. seq MUST BE A MUTABLE SEQUENCE.
As with list.sort() and random.shuffle this does NOT return """ changed = True while changed: changed = False for i in xrange(len(seq) - 1): if seq[i] > seq[i+1]: seq[i], seq[i+1] = seq[i+1], seq[i] changed = True return None
if __name__ == "__main__":
"""Sample usage and simple test suite"""
from random import shuffle
testset = range(100) testcase = testset[:] # make a copy shuffle(testcase) assert testcase != testset # we've shuffled it bubble_sort(testcase) assert testcase == testset # we've unshuffled it back into a copy</lang>
R
<lang R>bubblesort <- function(v) {
itemCount <- length(v) repeat { hasChanged <- FALSE itemCount <- itemCount - 1 for(i in 1:itemCount) { if ( v[i] > v[i+1] ) { t <- v[i] v[i] <- v[i+1] v[i+1] <- t hasChanged <- TRUE } } if ( !hasChanged ) break; } v
}
v <- c(9,8,7,3,1,100) print(bubblesort(v))</lang>
Ruby
This example adds the bubblesort! method to the Array object. Below are two different methods that show four different iterating constructs in ruby.
<lang 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 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 self end
end ary = [3, 78, 4, 23, 6, 8, 6] ary.bubblesort1! p ary
- => [3, 4, 6, 6, 8, 23, 78]</lang>
Scheme
<lang scheme>(define (bubble-sort x gt?)
(letrec ((fix (lambda (f i) (if (equal? i (f i)) i (fix f (f i)))))
(sort-step (lambda (l) (if (or (null? l) (null? (cdr l))) l (if (gt? (car l) (cadr l)) (cons (cadr l) (sort-step (cons (car l) (cddr l)))) (cons (car l) (sort-step (cdr l))))))))
(fix sort-step x)))</lang>
This solution iteratively finds the fixed point of sort-step. A comparison function must be passed to bubblesort. Example usages: <lang scheme>(bubble-sort (list 1 3 5 9 8 6 4 2) >) (bubble-sort (string->list "Monkey") char<?)</lang>
Here is a recursive bubble sort which sorts list 'l' using the comparator 'f':
<lang scheme>(define (bsort f l) (define (dosort l) (cond ((equal? (cdr l) '()) l) ((f (car l) (cadr l)) (cons (cadr l) (dosort (cons (car l) (cddr l))))) (else (cons (car l) (dosort (cdr l)))))) (let ((r (dosort l))) (cond ((equal? l r) l) (else (bsort f r)))))</lang> For example, you could do <lang scheme>(bsort > '(3 2 1)) (1 2 3)</lang>
Seed7
<lang 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);</lang>
Smalltalk
A straight translation from the pseudocode above. Swap is done with a block closure.
<lang smalltalk>|item swap itemCount hasChanged| item := #(1 4 5 6 10 8 7 61 0 -3) copy. swap := [:indexOne :indexTwo| |temp| temp := item at: indexOne. item at: indexOne put: (item at: indexTwo). item at: indexTwo put: temp].
itemCount := item size. [hasChanged := false. itemCount := itemCount - 1. 1 to: itemCount do: [:index | (item at: index) > (item at: index + 1) ifTrue: [swap value: index value: index + 1. hasChanged := true]]. hasChanged] whileTrue.</lang>
Tcl
uses package struct::list
from
<lang tcl>package require Tcl 8.5 package require struct::list
proc bubblesort {A} {
set len [llength $A] set swapped true while {$swapped} { set swapped false for {set i 0} {$i < $len - 1} {incr i} { set j [expr {$i + 1}] if {[lindex $A $i] > [lindex $A $j]} { struct::list swap A $i $j set swapped true } } incr len -1 } return $A
}
puts [bubblesort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
Idiomatic code uses the builtin lsort
instead, which is a stable O(n log n) sort.
Toka
Toka does not have a bubble sort predefined, but it is easy to code a simple one:
<lang toka>#! 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</lang>
UnixPipes
<lang bash>rm -f _sortpass
reset() {
test -f _tosort || mv _sortpass _tosort
}
bpass() {
(read a; read b test -n "$b" -a "$a" && ( test $a -gt $b && (reset; echo $b; (echo $a ; cat) | bpass ) || (echo $a; (echo $b ; cat) | bpass ) ) || echo $a)
}
bubblesort() {
cat > _tosort while test -f _tosort do cat _tosort | (rm _tosort;cat) |bpass > _sortpass done cat _sortpass
}
cat to.sort | bubblesort</lang>
Ursala
The bubblesort function is parameterized by a relational predicate. <lang Ursala>#import nat
bubblesort "p" = @iNX ^=T ^llPrEZryPrzPlrPCXlQ/~& @l ~&aitB^?\~&a "p"?ahthPX/~&ahPfatPRC ~&ath2fahttPCPRC
- cast %nL
example = bubblesort(nleq) <362,212,449,270,677,247,567,532,140,315></lang> output:
<140,212,247,270,315,362,449,532,567,677>
Visual Basic .NET
Platform: .NET
<lang vbnet>Do Until NoMoreSwaps = True
NoMoreSwaps = True For Counter = 1 To (NumberOfItems - 1) If List(Counter) > List(Counter + 1) Then NoMoreSwaps = False Temp = List(Counter) List(Counter) = List(Counter + 1) List(Counter + 1) = Temp End If Next NumberOfItems = NumberOfItems - 1
Loop</lang>
- Programming Tasks
- Sorting Algorithms
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- C
- C++
- C sharp
- Clean
- Clojure
- Common Lisp
- D
- E
- Forth
- Fortran
- Groovy
- Haskell
- J
- Java
- JavaScript
- Lisaac
- Lua
- Lucid
- M4
- Mathematica
- MAXScript
- Modula-3
- OCaml
- Octave
- Perl
- Pop11
- PowerShell
- Python
- R
- Ruby
- Scheme
- Seed7
- Smalltalk
- Tcl
- Tcllib
- Toka
- UnixPipes
- Ursala
- Visual Basic .NET