Sorting algorithms/Bubble sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 17:38, 10 April 2010

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(n²) 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

Works with: GCC version 4.1.2

<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

Works with: QuickBasic version 4.5

Translation of: Java

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++

Works with: g++ version 4.0.2

<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#

Works with: C# version 3.0+

<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 clojure>(ns bubblesort

 (:import java.util.ArrayList))

(defn bubble-sort

 "Sort in-place.
 arr must implement the Java List interface and should support
 random access, e.g. an ArrayList."
 ([arr] (bubble-sort compare arr))
 ([cmp 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 (pos? (cmp (.get arr i) (.get arr (inc i))))
                          (do
                            (swap! i (inc i))
                            (reset! changed true))))
                      @changed))]
      (doseq [stop-i (range (dec (.size arr)) -1 -1)
              :while (sorter stop-i)])
      arr)))

(println (bubble-sort (ArrayList. [10 9 8 7 6 5 4 3 2 1])))</lang>

Purely functional version working on Clojure sequences: <lang clojure>(defn- bubble-step

 "was-changed: whether any elements prior to the current first element
 were swapped;
 returns a two-element vector [partially-sorted-sequence is-sorted]"
[less? xs was-changed]
 (if (< (count xs) 2)
   [xs (not was-changed)]
   (let [[x1 x2 & xr] xs

first-is-smaller (less? x1 x2) is-changed (or was-changed (not first-is-smaller)) [smaller larger] (if first-is-smaller [x1 x2] [x2 x1]) [result is-sorted] (bubble-step less? (cons larger xr) is-changed)]

     [(cons smaller result) is-sorted])))

(defn bubble-sort

 "Takes an optional less-than predicate and a sequence.
 Returns the sorted sequence.
 Very inefficient (O(n²))"
 ([xs] (bubble-sort <= xs))
 ([less? xs] 
    (let [[result is-sorted] (bubble-step less? xs false)]
      (if is-sorted

result (recur less? result)))))

(println (bubble-sort [10 9 8 7 6 5 4 3 2 1]))</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

Works with: DMD version 1.025

<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.)

Factor

<lang factor>USING: fry kernel locals math math.order sequences sequences.private ; IN: rosetta.bubble

<PRIVATE

?exchange ( i seq quot -- ? )

   i i 1 + [ seq nth-unsafe ] bi@ quot call +gt+ = :> doit?
   doit? [ i i 1 + seq exchange ] when
   doit? ; inline

1pass ( seq quot -- ? )

   [ [ length 1 - iota ] keep ] dip
   '[ _ _ ?exchange ] [ or ] map-reduce ; inline

PRIVATE>

sort! ( seq quot -- )

   over empty?
   [ 2drop ] [ '[ _ _ 1pass ] loop ] if ; inline

natural-sort! ( seq -- )

   [ <=> ] sort! ;</lang>

It is possible to pass your own comparison operator to sort!, so you can f.e. sort your sequence backwards with passing [ >=< ] into it.

<lang factor>10 [ 10000 random ] replicate [ "Before: " write . ] [ "Natural: " write [ natural-sort! ] keep . ] [ "Reverse: " write [ [ >=< ] sort! ] keep . ] tri</lang>

Before:  { 3707 5045 4661 1489 3140 7195 8844 6506 6322 3199 }
Natural: { 1489 3140 3199 3707 4661 5045 6322 6506 7195 8844 }
Reverse: { 8844 7195 6506 6322 5045 4661 3707 3199 3140 1489 }

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>import Data.Maybe (fromMaybe) import Control.Monad

bsort :: Ord a => [a] -> [a] bsort s = maybe s bsort $ _bsort s

 where _bsort (x:x2:xs) = if x > x2
           then Just $ x2 : fromMaybe (x:xs) (_bsort $ x:xs)
           else liftM (x:) $ _bsort (x2:xs)
       _bsort _         = Nothing</lang>

HicEst

<lang fortran>SUBROUTINE Bubble_Sort(a)

 REAL :: a(1)

 DO j = LEN(a)-1, 1, -1
   swapped = 0
   DO i = 1, j
     IF (a(i) > a(i+1)) THEN
       temp = a(i)
       a(i) = a(i+1)
       a(i+1) = temp
       swapped = 1
     ENDIF
   ENDDO
   IF (swapped == 0) RETURN
 ENDDO

END</lang>

Icon

While bubble sort is a basic algorithm it also illustrates a difference in the way Icon handles types. The built-in operators for comparing data types make a syntactic distinction between numeric and string types. Consequently, when writing something like a bubble sort you must (a) write two versions, (b) have the sort figure it out dynamically as in this example. <lang Icon>procedure bubblesort(X,op) #: simple bubble sort local i,sorted

op := case op of { # select how to sort

  "<<"|">>"|"<<="|">>="|"<"|">"|"<="|">=": proc(op,2)
  "string":    proc("<<",2)
  "numeric":  proc("<",2)
  &null: if type(X[1]) == "string" then proc("<<",2)
         else proc("<",2)
  default: runerr(123,op)
  }

while /sorted := 1 do # the sort

  every  i := 2 to *X do  
     if op(X[i],X[i-1]) then {  
       X[i-1] :=: X[i]
       sorted := &null 
       }

return X end</lang>

This code will demonstrate the bubble sort using arguments supplied as arguments. The last sort call on a string rather than a list illustrates how many Icon operators work on different types. The example could be made more general to deal with coercion of types like cset to sting (admittedly an uninteresting example as csets are already sorted).

procedure main(l2)              #: demo bubblesort

l1 := copy(l2)                  # list of strings
l2[1] := numeric(l2[1])         # force list with leading numeric

displaysort(copy(l1))           # default string sort
displaysort(copy(l2))           # default numeric sort
displaysort(copy(l2),"string")  # explicit string sort
displaysort(copy(l1),"numeric") # explicit numeric sort
displaysort(copy(l2),"<<")      # descending string sort
displaysort(copy(l2),"<")       # descending numeric sort

displaysort("qwerty")           # sort characters in a string
end

procedure displaysort(X,op)     #: show bubblesort behavior
write("--- bubblesort ---")
write("op = ",image(op))
writex("before = ",X)
writex("after = ",bubblesort(X,op))
write()
return
end

procedure writex(tag,X)         #: helper for displaysort
writes(\tag)
if type(X) == "string" then write(image(X))
else {
   writes("[")
   every writes(" ",image(!X))
   write(" ]")
   }
return
end

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>

Works with: SEE version 3.0

Works with: OSSP js version 1.6.20070208

<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

Io

<lang Io> List do(

 bubblesort := method(
   t := true
   while( t,
     t := false
     for( j, 0, self size - 2,
       if( self at( j ) start > self at( j+1 ) start,
         self swapIndices( j,j+1 )
         t := true
       )
     )
   )
   return( self )
 )

) </lang>

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 } bubbleSort(list) 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>

Oz

In-place sorting of mutable arrays: <lang oz>declare

 proc {BubbleSort Arr}
    proc {Swap I J}
       Arr.J := (Arr.I := Arr.J) %% assignment returns the old value
    end
    IsSorted = {NewCell false}
    MaxItem = {NewCell {Array.high Arr}-1}
 in
    for until:@IsSorted do
       IsSorted := true
       for I in {Array.low Arr}..@MaxItem do
          if Arr.I > Arr.(I+1) then
             IsSorted := false
             {Swap I I+1}
          end
       end
       MaxItem := @MaxItem - 1
    end
 end
 Arr = {Tuple.toArray unit(10 9 8 7 6 5 4 3 2 1)}

in

 {BubbleSort Arr}
 {Inspect Arr}</lang>

Purely-functional sorting of immutable lists: <lang oz>declare

 local
    fun {Loop Xs Changed ?IsSorted}
       case Xs
       of X1|X2|Xr andthen X1 > X2 then
          X2|{Loop X1|Xr true IsSorted}
       [] X|Xr then
          X|{Loop Xr Changed IsSorted}
       [] nil then
          IsSorted = {Not Changed}
          nil
       end
    end
 in
    fun {BubbleSort Xs}
       IsSorted
       Result = {Loop Xs false ?IsSorted}
    in
       if IsSorted then Result
       else {BubbleSort Result}
       end
    end
 end

in

 {Show {BubbleSort [3 1 4 1 5 9 2 6 5]}}</lang>

Perl

<lang perl># Sorts an array in place sub bubble_sort {

   for my $i (0 .. $#_){
       for my $j ($i + 1 .. $#_){
           $_[$j] < $_[$i] and @_[$i, $j] = @_[$j, $i];
       }
   }

}</lang>

Usage:

<lang perl>my @a = (39, 25, 30, 28, 36, 72, 98, 25, 43, 38); bubble_sort(@a);</lang>

Perl 6

Works with: Rakudo version #24 "Seoul"

<lang perl6>sub bubble_sort (@a is rw) {

   for ^@a -> $i {
       for $i ^..^ @a -> $j {
           @a[$j] < @a[$i] and @a[$i, $j] = @a[$j, $i];
       }
   }

}</lang>

PHP

<lang php>function bubbleSort( array &$array ) { do { $swapped = false; for( $i = 0, $c = count( $array ) - 1; $i < $c; $i++ ) { if( $array[$i] > $array[$i + 1] ) { list( $array[$i + 1], $array[$i] ) = array( $array[$i], $array[$i + 1] ); $swapped = true; } } } while( $swapped ); }</lang>

PL/I

<lang PL/I> /* A primitive bubble sort */ bubble_sort: procedure (A);

  declare A(*) fixed binary;
  declare temp fixed binary;
  declare i fixed binary, no_more_swaps bit (1) aligned;

  do until (no_more_swaps);
     no_more_swaps = true;
     do i = lbound(A,1) to hbound(A,1)-1;
        if A(i) > A(i+1) then
           do; temp = A(i); A(i) = A(i+1); A(i+1) = temp;
               no_more_swaps = false;
           end;
     end;
  end;

end bubble_sort; </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>

PureBasic

<lang PureBasic>Procedure bubbleSort(Array a(1))

 Protected i, itemCount, hasChanged
 
 itemCount = ArraySize(a())
 Repeat
   hasChanged = #False
   itemCount - 1
   For i = 0 To itemCount
     If a(i) > a(i + 1)
       Swap a(i), a(i + 1)
       hasChanged = #True
     EndIf 
   Next  
 Until hasChanged = #False

EndProcedure</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

Generally, this task should be accomplished in Ruby using Array.sort!. Here we take an approach that's more comparable with the other examples on this page.

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>

Scala

This slightly more complex version of Bubble Sort avoids errors with indices.

<lang scala>def bubbleSort[T](arr: Array[T])(implicit o: Ordering[T]) {

 import o._
 val consecutiveIndices = (arr.indices, arr.indices drop 1).zipped
 var hasChanged = true
 do {
   hasChanged = false
   consecutiveIndices foreach { (i1, i2) =>
     if (arr(i1) > arr(i2)) {
       hasChanged = true
       val tmp = arr(i1)
       arr(i1) = arr(i2)
       arr(i2) = tmp
     }
   }
 } while(hasChanged)

}</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>

TI-83 BASIC

Input your data into L₁ and run this program to organize it.

:L₁→L₂
:1+dim(L₂
:For(D,1,dim(L₂)
:N-1→N
:0→I
:For(C,1,dim(L₂-2)
:For(A,dim(L₂)-N+1,dim(L₂)-1)
:If L₂(A)>L₂(A_1)
:Then
:1→I
:L₂(A)→B
:L₂(A+1)→L₂(A)
:B→L₂(A+1)
:End
:End
:End
:If I=0
:Goto C
:End
:Lbl C
:If L₂(1)>L₂(2)
:Then
:L₂(1)→B
:L₂(2)→L₂(1)
:B→L₂(2)
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:DelVar N
:DelVar I
:Return

Odd-Even Bubble Sort (same IO):

:"ODD-EVEN"
:L₁→L₂(
:1+dim(L₂)→N
:For(D,1,dim(L₂))
:N-1→N
:0→O
:For(C,1,dim(L₂)-2)
:For(A,dim(L₂)-N+2,dim(L₂)-1,2)
:If L₂(A)>L₂(A+1)
:Then
:1→O
:L₂(A)→B
:L₂(A+1)→L₂(A)
:B→L₂(A+1)
:End
:End
:For(A,dim(L₂)-N+1,dim(L₂)-1,2)
:If L₂(A)>L₂(A+1)
:Then
:1→O
:L₂(A)→B
:L₂(A+1)→L₂(A)
:B→L₂(A+1)
:End
:End
:End
:If O=0
:Goto C
:End
:Lbl C
:If L₂(1)>L₂(2)
:Then
:L₂(1)→B
:L₂(2)→L₂(1)
:B→L₂(2)
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:DelVar N
:DelVar O
:Return

Tcl

uses package struct::list from

Library: tcllib

<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>

Unicon

See Icon.

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>

VBScript

Doing the decr and incr thing is superfluous, really. I just had stumbled over the byref thing for swap and wanted to see where else it would work.

For those unfamiliar with Perth, WA Australia, the five strings being sorted are names of highways.

Implementation

<lang vb> sub decr( byref n ) n = n - 1 end sub

sub incr( byref n ) n = n + 1 end sub

sub swap( byref a, byref b) dim tmp tmp = a a = b b = tmp end sub

function bubbleSort( a ) dim changed dim itemCount itemCount = ubound(a) do changed = false decr itemCount for i = 0 to itemCount if a(i) > a(i+1) then swap a(i), a(i+1) changed = true end if next loop until not changed bubbleSort = a end function </lang>

Invocation

<lang vb> dim a a = array( "great eastern", "roe", "stirling", "albany", "leach") wscript.echo join(a,", ") bubbleSort a wscript.echo join(a,", ") </lang>

Output

great eastern, roe, stirling, albany, leach
albany, great eastern, leach, roe, stirling

Visual Basic .NET

Platform: .NET

Works with: Visual Basic .NET version 9.0+

<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>