Sorting algorithms/Bubble sort

Sorting algorithms/Bubble sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) 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(n²) performance, it is never used anywhere else.

The bubble sort works by passing sequentially over a list, comparing each value to the one immediately after it. If the first value is greater than the second, their positions are switched. Over a number of passes, at most equal to the number of elements in the list, all of the values drift into their correct positions (large values "bubble" rapidly toward the end, pushing others down around them). Because each pass finds the maximum item and puts it at the end, the portion of the list to be sorted can be reduced at each pass. A boolean variable is used to track whether any changes have been made in the current pass; when a pass completes without changing anything, the algorithm exits.

This can be expressed in pseudocode as follows (assuming 1-based indexing):

repeat
    set hasChanged to false
    decrement itemCount
    repeat with index from 1 to itemCount
        if (item at index) > (item at (index + 1))
            swap (item at index) with (item at (index + 1))
            set hasChanged to true
until hasChanged is false

Ada

Works with: GCC version 4.1.2

<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;</ada>

ALGOL 68

MODE DATA = INT; 

PROC swap = (REF[]DATA slice)VOID:
(
  DATA tmp = slice[1];
  slice[1] := slice[2];
  slice[2] := tmp
);

PROC sort = (REF[]DATA array)VOID:
(
  BOOL sorted;
  INT shrinkage := 0;
  FOR size FROM UPB array - 1 BY -1 WHILE
    sorted := TRUE;
    shrinkage +:= 1;
    FOR i FROM LWB array TO size DO
      IF array[i+1] < array[i] THEN
        swap(array[i:i+1]);
        sorted := FALSE
      FI
    OD;
    NOT sorted
  DO SKIP OD
);

main:(
  [10]INT random := (1,6,3,5,2,9,8,4,7,0); 

  printf(($"Before: "10(g(3))l$,random));
  sort(random);
  printf(($"After: "10(g(3))l$,random))
)

Output:

Before:  +1 +6 +3 +5 +2 +9 +8 +4 +7 +0
After:  +0 +1 +2 +3 +4 +5 +6 +7 +8 +9

BASIC

Works with: QuickBasic version 4.5

Translation of: Java

Assume numbers are in a DIM of size "size" called "nums". <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)</qbasic>

C

void swap(int *p)
{
  int t = p[0];
  p[0] = p[1];
  p[1] = t;
}
void sort(int *a, int size)
{
  int i,sorted;
  do {
    sorted = 1;
    --size;
    for (i=0; i<size; i++)
      if (a[i+1] < a[i])
      {
        swap(a+i);
        sorted = 0;
      }
  } while (!sorted);
}

C++

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

C#

Works with: C# version 3.0+

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

}</csharp>

Clean

Bubble sorting an array in-situ (using destructive updates), using Clean's uniqueness typing. We specified the type of sweep using strictness annotations to improve performance.

import StdEnv

bsort :: *(a e) -> *(a e) | Array a e & < e
bsort array
    # (done, array) = sweep 1 True array
    = if done array (bsort array)
where
    sweep :: !Int !Bool !*(a e) -> (!Bool, !*(a e)) | Array a e & < e
    sweep i done array
        | i >= size array = (done, array)
        # (e1, array) = array![i - 1]
          (e2, array) = array![i]
        | e1 > e2 = sweep (i + 1) False {array & [i - 1] = e2, [i] = e1}
        = sweep (i + 1) done array

Using it to sort an array of a hundred numbers:

Start :: {Int}
Start = bsort {x \\ x <- [100,99..1]}

D

Works with: DMD version 1.025

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

} </d>

E

def bubbleSort(target) {
  __loop(fn {
    var changed := false
    for i in 0..(target.size() - 2) {
      def [a, b] := target(i, i + 2)
      if (a > b) {
        target(i, i + 2) := [b, a]
        changed := true
      }
    }
    changed
  })
}

(Uses the primitive __loop directly because it happens to map to the termination test for this algorithm well.)

Forth

Sorts the 'cnt' cells stored at 'addr' using the test stored in the deferred word 'bubble-test'. Uses forth local variables for clarity.

defer bubble-test
' > is bubble-test

: bubble { addr cnt -- }
  cnt 1 do
    addr cnt i - cells bounds do
      i 2@ bubble-test if i 2@ swap i 2! then
    cell +loop
  loop ;

This is the same algorithm done without the local variables:

: bubble ( addr cnt -- )
  dup 1 do
    2dup i - cells bounds do
      i 2@ bubble-test if i 2@ swap i 2! then
    cell +loop
  loop ;

Version with O(n) best case:

: bubble ( addr len -- )
  begin
    1- 2dup  true -rot  ( sorted addr len-1 )
    cells bounds ?do
      i 2@ bubble-test if
        i 2@ swap i 2!
        drop false   ( mark unsorted )
      then
    cell +loop  ( sorted )
  until 2drop ;

Test any version with this:

create test
8 , 1 , 4 , 2 , 10 , 3 , 7 , 9 , 6 , 5 ,
here test - cell / constant tcnt

test tcnt cells dump
' > is bubble-test
test tcnt bubble
test tcnt cells dump
' < is bubble-test
test tcnt bubble
test tcnt cells dump

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

Haskell

This version checks for changes in a separate step for simplicity, because Haskell has no variables to track them with.

bsort :: Ord a => [a] -> [a]
bsort s = case _bsort s of
               t | t == s    -> t
                 | otherwise -> bsort t
  where _bsort (x:x2:xs) | x > x2    = x2:(_bsort (x:xs))
                         | otherwise = x:(_bsort (x2:xs))
        _bsort s = s

This version uses the polymorphic Maybe type to designate unchanged lists. (The type signature of _bsort is now Ord a => [a] -> Maybe [a].) It is slightly faster than the previous one.

bsort :: Ord a => [a] -> [a]
bsort s = case _bsort s of
               Nothing -> s
               Just s2 -> bsort s2
  where _bsort (x:x2:xs) | x > x2    = case _bsort (x:xs) of
                                            Nothing  -> Just $ x2:x:xs
                                            Just xs2 -> Just $ x2:xs2
                         | otherwise = case _bsort (x2:xs) of
                                            Nothing  -> Nothing
                                            Just xs2 -> Just $ x:xs2
        _bsort _ = Nothing

Java

Bubble sorting (ascending) an array of any Comparable type: <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);</java>

For descending, simply switch the direction of comparison: <java>if(comparable[a].compareTo(comparable[b]) < 0){

  //same swap code as before

}</java>

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

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

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

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

Perl

Works with: Perl version 5.8.8

# Sorts an array in place and returns a copy
sub bubble_sort (@) {
    my $len = @_ - 1;
    for my $i (0 .. $len - 1){
        for my $j ($i + 1 .. $len){
            if ($_[$j] lt $_[$i]) {
                @_[$i, $j] = @_[$j, $i];
            }
        }
    }
    return @_;
}

# usage
@a = qw/G F C A B E D/; 
bubble_sort(@a);

Alternate "Long Hand" Perl Method

sub Bubble_Sort {
    my @list = @_;
    my $temp = 0;
    my $done = 0;
    my $elements = $#list;

    while ($done == 0) {
        $done = 1;
        $elements--;
        for (my $i = 0; $i < $elements; $i++) {
            if ($list[$i] > $list[$i + 1]) {
                $done = 0;
                $temp = $list[$i];
                $list[$i] = $list[$i + 1];
                $list[$i + 1] = $temp;
            }
        }
    }
  
    return @list;
}

# usage
my @test = (1, 3, 256, 0, 3, 4, -1);
print join(",", Bubble_Sort(@test));

Pop11

define bubble_sort(v);
lvars n=length(v), done=false, i;
while not(done) do
   true -> done;
   n - 1 -> n;
   for i from 1 to n do
      if v(i) > v(i+1) then
         false -> done;
         ;;; Swap using multiple assignment
         (v(i+1), v(i)) -> (v(i), v(i+1));
      endif;
   endfor;
endwhile;
enddefine;

;;; Test it
vars ar = { 10 8 6 4 2 1 3 5 7 9};
bubble_sort(ar);
ar =>

Python

<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   

</python>

Ruby

Although the native Ruby sort method for Arrays if much faster (O(n*log(n)) versus O(n**2)), you can find a Ruby version of Bubble sort hereunder. It adds the bubblesort! method to the Array object. Below are two different methods that show four different iterating constructs in ruby.

 class Array
   def bubblesort1!
     length.times do |j|
       for i in 1...(length - j)
         if self[i] < self[i - 1]
           self[i], self[i - 1] = self[i - 1], self[i]
         end
       end
     end
   
     return self
   end

   def bubblesort2!
     each_index do |index|
       (length - 1).downto( index ) do |i|
         a, b = self[i-1], self[i]
         a, b = b, a if b < a
       end
     end
   
     return self
   end
 end

 puts [3, 78, 4, 23, 6, 8, 6].bubblesort1!
 # => [3, 4, 6, 6, 8, 23, 78]

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

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

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.

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

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