Sorting algorithms/Bubble sort

From Rosetta Code

(Redirected from Bubble 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(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

[edit] 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;
}

[edit] Ada

Works with: GCC version 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;

[edit] 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

[edit] 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
}

[edit] AWK

Sort the standard input and print it to standard output.

{ # 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]
  }
}

[edit] BASIC

Works with: QuickBasic version 4.5

Translation of: Java Assume numbers are in a DIM of size "size" called "nums".

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)

[edit] 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);
}

[edit] C++

Works with: g++ version 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 ;
}

[edit] C#

Works with: C# version 3.0+

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 + " ");
        }
    }
}

[edit] 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]}

[edit] 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.

(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])))

Purely functional version working on Clojure sequences:

(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]))

[edit] Common Lisp

Bubble sort an sequence in-place, using the < operator for comparison if no comaprison function is provided

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

(bubble-sort (list 5 4 3 2 1))

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.

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

[edit] D

Works with: DMD version 1.025

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);
}

[edit] 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.)

[edit] 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! ;

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

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

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 }

[edit] 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

[edit] 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

[edit] Groovy

Solution:

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
}

Test Program:

def list = [1,6,3,5,2,9,8,4,7,0]
println list
println bubbleSort(list)

Output:

[1, 6, 3, 5, 2, 9, 8, 4, 7, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[edit] 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.

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

[edit] J

bubbleSort=:  (([ (<. , >.) {.@]) , }.@])/^:_

Test program:

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

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.

[edit] Java

Bubble sorting (ascending) an array of any Comparable type:

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

For descending, simply switch the direction of comparison:

if (comparable[a].compareTo(comparable[b]) < 0){
   //same swap code as before
}

[edit] 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;
}

Works with: SEE version 3.0 Works with: OSSP js version 1.6.20070208

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

Example:

var my_arr = ["G", "F", "C", "A", "B", "E", "D"];
my_arr.bubblesort();
print(my_arr);

Output:

A,B,C,D,E,F,G

[edit] 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};
);

[edit] 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

Example:

 
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

[edit] Lucid

[1]

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

[edit] 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')

Output:

17 63 80 55 90 88 25 9 71 38

9 17 25 38 55 63 71 80 88 90

[edit] 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:

BubbleSort[input_] := input //. {a___, i_, j_, b___} /; OrderedQ[{j, i}] :> {a, j, i, b}

Example:

BubbleSort[{10, 3, 7, 1, 4, 3, 8, 13, 9}]

gives back:

{1, 3, 3, 4, 7, 8, 9, 10, 13}

[edit] 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

[edit] Modula-3

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.

[edit] OCaml

Like the Haskell versions above:

This version checks for changes in a separate step for simplicity.

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

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.

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

[edit] 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

v = [9,8,7,3,1,100];
disp(bubblesort(v));

[edit] Oz

In-place sorting of mutable arrays:

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}

Purely-functional sorting of immutable lists:

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

[edit] 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];
        }
    }
}

Usage:

my @a = (39, 25, 30, 28, 36, 72, 98, 25, 43, 38);
bubble_sort(@a);

[edit] Perl 6

Works with: Rakudo version #24 "Seoul"

sub bubble_sort (@a is rw) {
    for ^@a -> $i {
        for $i ^..^ @a -> $j {
            @a[$j] < @a[$i] and @a[$i, $j] = @a[$j, $i];
        }
    }
}

[edit] 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;

[edit] 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 =>

[edit] 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
            }
        }
    }
}

[edit] 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

[edit] 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

[edit] 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))

[edit] Ruby

Though this task should probably be done in Ruby using Array.sort!, the following code demonstrates a particular method that may be less efficient, but fits better with 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.

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]

[edit] 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)))

This solution iteratively finds the fixed point of sort-step. A comparison function must be passed to bubblesort. Example usages:

(bubble-sort (list 1 3 5 9 8 6 4 2) >)
(bubble-sort (string->list "Monkey") char<?)

Here is a recursive bubble sort which sorts list 'l' using the comparator 'f':

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

For example, you could do

(bsort > '(3 2 1))
(1 2 3)

[edit] 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);

[edit] Smalltalk

A straight translation from the pseudocode above. Swap is done with a block closure.

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

[edit] 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

[edit] Tcl

uses package struct::list from Library: tcllib

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

Idiomatic code uses the builtin lsort instead, which is a stable O(n log n) sort.

[edit] 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

[edit] UnixPipes

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

[edit] Ursala

The bubblesort function is parameterized by a relational predicate.

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

output:

<140,212,247,270,315,362,449,532,567,677>

[edit] 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.

[edit] Implementation

 
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

[edit] Invocation

 
dim a
a = array( "great eastern", "roe", "stirling", "albany", "leach")
wscript.echo join(a,", ")
bubbleSort a
wscript.echo join(a,", ")

[edit] Output

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

[edit] Visual Basic .NET

Platform: .NET

Works with: Visual Basic .NET version 9.0+

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

Sorting algorithms/Bubble sort

From Rosetta Code

Contents

[edit] ActionScript

[edit] Ada

[edit] ALGOL 68

[edit] AutoHotkey

[edit] AWK

[edit] BASIC

[edit] C

[edit] C++

[edit] C#

[edit] Clean

[edit] Clojure

[edit] Common Lisp

[edit] D

[edit] E

[edit] Factor

[edit] Forth

[edit] Fortran

[edit] Groovy

[edit] Haskell

[edit] J

[edit] Java

[edit] JavaScript

[edit] Lisaac

[edit] Lua

[edit] Lucid

[edit] M4

[edit] Mathematica

[edit] MAXScript

[edit] Modula-3

[edit] OCaml

[edit] Octave

[edit] Oz

[edit] Perl

[edit] Perl 6

[edit] PL/I

[edit] Pop11

[edit] PowerShell

[edit] PureBasic

[edit] Python

[edit] R

[edit] Ruby

[edit] Scheme

[edit] Seed7

[edit] Smalltalk

[edit] TI-83 BASIC

[edit] Tcl

[edit] Toka

[edit] UnixPipes

[edit] Ursala

[edit] VBScript

[edit] Implementation

[edit] Invocation

[edit] Output

[edit] Visual Basic .NET

Views

Personal tools

Browse

Participate

Community

Google AdSense

Search

Toolbox