Last modified on 13 October 2014, at 21:11

Algorithm Implementation/Sorting/Bubble sort

Bubble SortEdit

The bubble sort is also known as the ripple sort. The bubble sort is probably the first, reasonably complex module that any beginning programmer has to write. It is a very simple construct which introduces the student to the fundamentals of how sorting works.

A bubble sort makes use of an array and some sort of "swapping" mechanism. Most programming languages have a built-in function to swap elements of an array. Even if a swapping function does not exist, only a couple of extra lines of code are required to store one array element in a temporary field in order to swap a second element into its place. Then the first element is moved out of the temporary field and back into the array at the second element's position.

Here is a simple example of how a bubble sort works: Suppose you have a row of children's toy blocks with letters on them. They are in random order and you wish to arrange them in alphabetical order from left to right.



Step 1. Begin with the first block. In this case, the letter G. (Fig. 1.)
Fig. 1
Fig. 1
Step 2. Look at the block just to the right of it.



Step 3. If the block to the right should come before the block on the left, swap them so that they are in order (Fig. 2.)
Fig. 2
Fig. 2



If you were doing this by hand, you might just pick the blocks to be moved with one in each hand and cross your arms to swap them. Or you might move the first one out of its position temporarily, move the second one in its place, then move the first one to the now empty position (this is the difference between having a single function to do the swap, or writing some code to do it).



Step 4. Compare the next block in line with the first, and repeat step 3. Do this until you run out of blocks. Then begin step one again with the second block. (Fig. 3,4,5,6)


Fig. 3
Fig. 3 - Pass #2
Fig. 4
Fig. 4 - Pass #3
Fig. 5
Fig. 5 - Pass #4
Fig. 6
Fig. 6 - Completed Sort

Why is it called a bubble sort?Edit

The bubble sort gets its name because elements tend to move up into the correct order like bubbles rising to the surface.

Quick BasicEdit

CLS

DIM NameArray$(1000)

i = 0

' Seed read ...
READ Name$

' Loop through and read names in data ...
DO WHILE Name$ <> "*EOD"
      i = i + 1
      NameArray$(i) = Name$
      READ Name$
LOOP

' The value of i is now the number of names in the array ...
ArraySize = i


' Bubble (or ripple) sort ...
FOR i = 1 TO ArraySize - 1
  FOR j = 1 TO ArraySize - 1
      IF NameArray$(j) > NameArray$(j + 1) THEN
         SWAP NameArray$(j), NameArray$(j + 1)
      END IF
  NEXT j
NEXT i

' Print out the sorted results ...
FOR i = 1 TO ArraySize
        PRINT NameArray$(i)
NEXT i

DATA Crowe,
DATA Adams,
DATA Zimmerman,
DATA Goodhead,
DATA Smith,
DATA Jones,
DATA *EOD

C 1Edit

/**
 * An example of bubble sort written in C.
 * Author: Nebu Pookins (nebu@gta.igs.net)
 *
 * I've tried to keep the "logic" of this program as close to the
 * QuickBasic example as possible.
 */
 
int main(void) {
  const int numberOfElements = 6;
  char arrayOfCharsToSort[numberOfElements];
  //Fill in the array with the unsorted data.
  arrayOfCharsToSort[0] = 'C';
  arrayOfCharsToSort[1] = 'A';
  arrayOfCharsToSort[2] = 'Z';
  arrayOfCharsToSort[3] = 'G';
  arrayOfCharsToSort[4] = 'S';
  arrayOfCharsToSort[5] = 'J';
 
  //Start sorting
  int i, j; //variables used for for loops.
  char temporaryCharHolder; //used to swap values of two array entries
  for (i = 0; i < numberOfElements; i++) {
    for (j = 0; j < numberOfElements - 1; j++) {
      if (arrayOfCharsToSort[j] > arrayOfCharsToSort[j + 1]) {
        temporaryCharHolder = arrayOfCharsToSort[j];
        arrayOfCharsToSort[j] = arrayOfCharsToSort[j + 1];
        arrayOfCharsToSort[j + 1] = temporaryCharHolder;
      }
    }
  }
 
  //Print out the sorted results
  for (i = 0; i < numberOfElements; i++) {
    printf("%c\n", arrayOfCharsToSort[i]);
  }
 
  return 0;
}

C 2Edit

 void bubblesort(int *array, int length)
 {
     int i, j;
     for (i = 0; i < length - 1; ++i) 
     {
 
 	for (j = 0; j < length - i - 1; ++j) 
        {
 	    if (array[j] > array[j + 1]) 
            {
 		int tmp = array[j];
 		array[j] = array[j + 1];
 		array[j + 1] = tmp;
 	    }
 	}
     }
 }

C++Edit

C++ can use the C bubble sort above, or use this for random-access iterators of generic containers and a generic comparison operator:

 #include <algorithm>
 
 template<typename Iterator>
 void bubbleSort(Iterator first, Iterator last)
 {
     Iterator i, j;
     for (i = first; i != last; i++)
         for (j = first; j < i; j++)
             if (*i < *j)
                 std::iter_swap(i, j); // or std::swap(*i, *j);
 }
 
 template<typename Iterator, class StrictWeakOrdering>
 void bubbleSort(Iterator first, Iterator last, StrictWeakOrdering compare)
 {
     Iterator i, j;
     for (i = first; i != last; i++)
         for (j = first; j < i; j++)
             if (compare(*i, *j))
                 std::iter_swap(i, j);
 }
 
template <typename Iterator>
void bubbleSort(Iterator first, Iterator last)
{
    for (Iterator i = first; i != last - 1; ++i)
        for (Iterator j = first; j != (last - 1 - distance(first, i)); ++j)
            if (*j > *(j + 1))
                std::swap(*j, *(j + 1));
}
 
template <typename Iterator, typename StrictWeakOrdering>
void bubbleSort(Iterator first, Iterator last, StrictWeakOrdering compare)
{
    for (Iterator i = first; i != last - 1; ++i)
        for (Iterator j = first; j != (last - 1 - distance(first, i)); ++j)
            if (compare(*j, *(j + 1)))
                std::swap(*j, *(j + 1));
}

DEdit

 void bubbleSort(T)(T[] array) {
     bool swapped;
     T temp = void;
     for (int j, i = array.length - 1; i; swapped = false, i--) {
         for (j = 0; j < i; j++)
             if (array[j] > array[j+1]) {
                 temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
                 swapped = true;
             }
         if (!swapped) break;
     }
 }

C#Edit

 static void BubbleSort(IComparable[] array)
 {
     int i = array.Length - 1;
     while(i > 0)
     {
         int swap = 0;
         for (int j = 0; j < i; j++)
         {
             if (array[j].CompareTo(array[j + 1]) > 0)
             {
                 IComparable temp = array[j];
                 array[j] = array[j + 1];
                 array[j + 1] = temp;
                 swap = j;
             }
         }
         i = swap;
     }
 }

C# 2.0Edit

 static void BubbleSort<T>(IList<T> array) where T : IComparable<T>
 {
     int i, j;
     T temp;
 
     for (i = array.Count - 1; i > 0; i--)
     {
         for (j = 0; j < i; j++)
         {
             if (array[j].CompareTo(array[j + 1]) > 0) 
             {
                 temp = array[j];
                 array[j] = array[j + 1];
                 array[j + 1] = temp;
             }
         }
     }
 }

AdaEdit

Sorts an array of integers.

 type Integer_array is Array (Natural range <>) of Integer;
 
 procedure Bubble_Sort (A : in out Integer_Array) is
    Temp : Integer;
 begin
    for I in reverse A'Range loop
       for J in A'First .. I loop
          if A(I) < A(J) then
             Temp := A(J);
             A(J) := A(I);
             A(I) := Temp;
          end if;
       end loop;
    end loop;
 end Bubble_Sort;

AssemblyEdit

MASM. Sorts an array of DWORDS with len elements.

 bs proc array:DWORD,len:DWORD
 	mov ecx,len
 	mov edx,array
 	bs_o:
 	xor ebp,ebp
 	bs_i:
 	mov eax,DWORD PTR [edx+ebp*4+4]
 	cmp DWORD PTR [edx+ebp*4],eax
 	jb @F
 	xchg eax,DWORD PTR [edx+ebp*4]
 	mov DWORD PTR [edx+ebp*4+4],eax
 	@@:
 	add ebp,1
 	cmp ebp,ecx
 	jb bs_i
 	loop bs_o
 	pop ebp
 	retn 8
 bs endp

AutoItEdit

Sorts an array of variant data types

Func BubbleSort(ByRef $bs_array)
	For $i = UBound($bs_array) - 1 To 1 Step -1
		For $j = 2 To $i
			If $bs_array[$j - 1] > $bs_array[$j] Then
				$temp = $bs_array[$j - 1]
				$bs_array[$j - 1] = $bs_array[$j]
				$bs_array[$j] = $temp
			EndIf
		Next
	Next
	Return $bs_array
EndFunc   ;==>BubbleSort

BASICEdit

 Sub Bubblesort(Array() as Integer, Length as Integer)
    Dim I as Integer
    Dim J as Integer
    Dim Temp as Integer
 
    For I = Length -1 To 1 Step -1
       For J = 0 to I - 1
          IF Array(J)>Array(J+1) THEN  ' Compare neighboring elements
             Temp = Array(j) 
             Array(J) = Array(J+1)
             Array(J+1) = Temp
          End If
       Next J
    Next I
 
 End Sub

BlitzBasicEdit

  unsorted=1
  while unsorted
    unsorted=0
    for x = 1 to 10
      if ar[x]<ar[x-1]
        unsorted=1
        tmp = ar[x]
        ar[x] = ar[x-1]
        ar[x-1] = tmp
      end if
    next
  wend

Common LispEdit

(defun bubble-sort (lst)
  (loop repeat (1- (length lst)) do
    (loop for ls on lst while (rest ls) do
      (when (> (first ls) (second ls))
        (rotatef (first ls) (second ls)))))
  lst)

Emacs LispEdit

(defun bubblesort (list pred)
  "Sort LIST in order of comparison function PRED."
  (let ((i (length list)))
    (while (> i 1)
      (let ((b list))
        (while (cdr b)
          (when (funcall pred (cadr b) (car b))
            (setcar b (prog1 (cadr b)
                        (setcdr b (cons (car b) (cddr b))))))
          (setq b (cdr b))))
      (setq i (1- i)))
    list))

FORTRANEdit

      SUBROUTINE sort (array_x, array_y, datasize)
 Global Definitions
       REAL array_x(*)
       REAL array_y(*)
       INTEGER datasize
 Local
      REAL x_temp
      REAL y_temp      
      LOGICAL inorder      
      inorder = .false.
      do 90 while (inorder.eq..false.)
       inorder = .true.       
       do 91 i=1, (datasize-1)              
 Check Equilivant Points and swap those on Y
       if (array_x(i).eq.array_x(i+1) ) then
        if (array_y(i).lt.array_y(i+1) ) then
         x_temp = array_x(i)
         y_temp = array_y(i)
         array_x(i) = array_x(i+1)
         array_y(i) = array_y(i+1)
         array_x(i+1) = x_temp
         array_y(i+1) = y_temp
         inorder = .false.
        endif
       endif
 If x needs to be swapped, do so 
       if (array_x(i).lt.array_x(i+1) )then
        x_temp = array_x(i)
        y_temp = array_y(i)
        array_x(i) = array_x(i+1)
        array_y(i) = array_y(i+1)
        array_x(i+1) = x_temp
        array_y(i+1) = y_temp
        inorder = .false.
       endif 
 91    continue
 90    continue       
      END SUBROUTINE sort

HaskellEdit

bubbleSort []=[]
bubbleSort x=
   (iterate swapPass x) !! ((length x)-1)
   where
      swapPass [x]=[x]
      swapPass (x:y:zs)
         | x>y = y:swapPass (x:zs)
         | otherwise = x:swapPass (y:zs)

JavaEdit

public static int[] bubblesort(int[] numbers) {
    boolean swapped = true;
    for(int i = numbers.length - 1; i > 0 && swapped; i--) {
        swapped = false;
        for (int j = 0; j < i; j++) {
            if (numbers[j] > numbers[j+1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
                swapped = true;
            }
        }
    }
    return numbers;
}

JavaScriptEdit

JavaScript Implementation with simple HTML test page

<html>
<head>
<script type="text/javascript">
// GLOBAL FUNCTION
Array.prototype.bubble_sort = function() {
    var i, j;
    var newarray = this.slice(0);
    var swap = function(j, k) {
      var temp = newarray[j];
      newarray[j] = newarray[k];
      newarray[k] = temp;
      return(true);
    }
    var swapped = false;
    for(i=1; i<newarray.length; i++) {
      for(j=0; j<newarray.length - i; j++) {
        if (newarray[j+1] < newarray[j]) {
          swapped = swap(j, j+1);
        }
      }
      if (!swapped) break;
    }
    return(newarray)
}
 
// LOCAL FUNCTION
show = function (inarray, title) {
  document.writeln("<h4>"+title+":</h4>");
  document.writeln(inarray.join(", ")+"<br />");
} 
</script>
</head>
<body>
<script>
// MAIN
// test bubble_sort function
sorted_array = [1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1].bubble_sort();
show(sorted_array, "Sorted Array");
// result: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7]
</script>
</body>
</html>

OCamlEdit

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>

PascalEdit

Procedure BubbleSort:

const
  MAXINTARRAY    : 1000; { Set this value to fit your data needs for max array size }
  STARTINTARRAY  : 1;    { Set 1 _or_ 0; indicates the lower index of the array }
Type
  IntArray : Array[STARTINTARRAY..MAXINTARRAY] of integer;

BubbleSort is an all purpose sorting procedure that is passed an array of
integers and returns that same array with the array elements sorted as desired.

Parameters are used to control the sorting operation:

If you want to sort the entire array, pass a value in Count that signals the number
of elements you want sorted. BubbleSort will then sort Count number of elements starting 
with the first element in the array. 

If you want to sort a subset of elements within the array, pass 0 in Count and pass
a beginning and ending subset index number in First and Last, respectively.

The sort will be either ascending or descending as controlled by the parameter Ascend:

Pass True in Ascend and the sort will be ascending. Pass False and the sort will be 
descending.

Data: The array to be sorted.

NOTE: Sample is a var and will be modified by BubbleSort, unless the array is 
already in a sorted state.

Count:  0 _or_ the number of elements to be sorted, starting with the first element.

First:  The first element to be sorted in a subset of the array.

Last:   The last element to be sorted in a subset of the array.

Ascend:  Flag to indicate the sort order. True is ascending order. False is descending.

Succ:   Flag returns result of BubbleSort

0 = success.

1 = Failed. Parameter First has value below allowed first index value.

2 = Failed. Parameter Last has value above allowed last index value.

3 = Failed. Parameter Last has value below allowed first index value.

===================================================================================*)
 Procedure BubbleSort( 
                       Var Data : IntArray;
                       Count    : integer;
                       First    : integer;
                       Last     : integer;
                       Acend    : boolean;
                       Var Succ : integer );
 
 var 
   i,
   temp, 
   s_begin, 
   s_end,
   numsort : integer;
   sorted  : boolean;
 
 Begin
   { initialize for full array sort }
   s_begin := STARTINTARRAY;
   s_end   := STARTINTARRAY + count - 1 ;
   numsort := Count;
   Succ    := 0;    { assume success }
 
   { check for a subset sort; check parameters for correctness }
   if (Count = 0) then 
     Begin
       If (First < STARTINTARRAY) then 
       Begin { error: sort start index too low }
         Succ := 1;
         Exit;
       End;
       If (Last > MAXINTARRAY) then
       Begin { error: sort end index too high }
         Succ := 2;
         Exit;
       End;
       if (Last < STARTINTARRAY) then 
       Begin { error: sort end index too low }
         Succ := 3;
         Exit;
       End;
       s_begin := First;
       s_end   := Last;
       numsort := Last - First + 1;
     End;
   If numsort <= 1 then Exit; { only one element, so exit }
 
   If Acend then
   Begin { do the ascending sort }
     Repeat
       sorted := true; { flag default is true }
       For i := s_begin to s_end -1 do
         if (Data[i] < Data[i+1]) then
         Begin
           { swap contents of Data[i] and Data[i+1] }
           temp      := Data[i];
           Data[i]   := Data[i+1];
           Data[i+1] := temp;
           { set flag to indicate a swap occured; i.e., sort may not be completed }
           sorted := false;
         End;
     Until sorted;
   End Else
   Begin { do the descending sort }
     Repeat
       sorted := true; { flag default is true }
       For i := s_begin to s_end -1 do
         if (Data[i] < Data[i+1]) then
         Begin
           { swap contents of Data[i] and Data[i+1] }
           temp      := Data[i];
           Data[i]   := Data[i+1];
           Data[i+1] := temp;
           { set flag to indicate a swap occured; i.e., sort may not be completed }
           sorted := false;
         End;
     Until sorted;
   End;
 End;

A simplified version:

 Procedure BubbleSort(var a:IntArray; size:integer);
  var i,j,temp: integer;
  begin
   for i:=1 to size-1 do
    for j:=i + 1 to size do
     if a[i]>a[j] then
        begin
         temp:=a[j]; a[j]:=a[i]; a[i]:=temp;
        end;
  end;

PerlEdit

 sub swap {
   @_[0, 1] = @_[1, 0];
 }
 
 sub bubble_sort {
   for ($i=$[; $i < $#_; ++$i) {
     for ($j=$[; $j < $#_; ++$j) {
       ($_[$j] > $ _[$j+1]) and swap($_[$j], $_[$j+1]);
     }
   }
 }

PHPEdit

 function bubbleSort ($items) {
     $size = count($items);
     for ($i=0; $i<$size; $i++) {
          for ($j=0; $j<$size-1-$i; $j++) {
               if ($items[$j+1] < $items[$j]) {
                   arraySwap($items, $j, $j+1);
               }
          }
     }
     return $items;
 }
 function arraySwap (&$arr, $index1, $index2) {
     list($arr[$index1], $arr[$index2]) = array($arr[$index2], $arr[$index1]);
 }

PythonEdit

 def bubblesort(lst):
     "Sorts lst in place and returns it."
     for passesLeft in range(len(lst)-1, 0, -1):
         for index in range(passesLeft):
             if lst[index] > lst[index + 1]:
                lst[index], lst[index + 1] = lst[index + 1], lst[index]
     return lst

RubyEdit

module BubbleSort
  def self.sort(keys)
    sort!(keys.clone)
  end
 
  def self.sort!(keys)
    0.upto(keys.size-1) do |i|
      (keys.size-1).downto(i+1) do |j|
        (keys[j], keys[j-1] = keys[j-1], keys[j]) if keys[j] < keys[j-1]
      end
    end
    keys
  end
end

SchemeEdit

 (define (bubblesort l)
  (define (swap-pass l)
    (if (NULL? l)  ;to handle empty list
        l
        (let ((fst (car l))(snd (cadr l))(rest (cddr l)))
          (if (> fst snd) 
              (cons snd (swap-pass (cons fst rest)))
              (cons fst (swap-pass (cons snd rest)))))))
  (let for ((times (length l))
            (val l))
    (if (> times 1)
        (for (- times 1)(swap-pass val))
        (swap-pass val))))

Standard MLEdit

fun bubble_select [] lessThan =[]
  | bubble_select [a] lessThan =[a]
  | bubble_select (a::b::xs) lessThan =
    if lessThan b a then b::(bubble_select(a::xs) lessThan) else a::(bubble_select(b::xs) lessThan)
 
 
 
fun bubblesort [] lessthan =[]
  | bubblesort (x::xs) lessthan =bubble_select (x::(bubblesort xs lessthan)) lessthan

VBAEdit

 
 Private Sub bubble(N as integer, array() as integer)
 
 'N is the number of integers in the array'
 '0 to N-1'
  
 Dim I, J, P, Temp as Integer
 
 For I = n - 1 To 0 Step -1
     P=0
     For J = 0 To I
          If array(J) > array(J + 1) Then
             Temp = array(J)
             array(J) = array(J + 1)
             array(J + 1) = Temp
          Else
             P=P+1
          End If
          If P=I then GoTo premend
     Next J
 Next I
 
 'premend = premature ending = all integers are allready sorted'
 premend:
 
 End Sub

see discussion for possible mistake

Visual BasicEdit

  Public Sub BubbleSort(ByRef ArrayIn() As Long)
    Dim i, j    As Integer
    Dim t       As Long
    For i = UBound(ArrayIn) To 0 Step -1 
      For j = 0 To i - 1 
          If ArrayIn(j) > ArrayIn(j + 1) Then
              Call swap(ArrayIn(j), ArrayIn(j + 1))
          End If
      Next j
    Next i
  End Sub
 
  Private Sub swap(ByRef data1 As Long, ByRef data2 As Long)
    Dim temp As Long
    temp = data1
    data1 = data2
    data2 = temp
  End Sub

MELEdit

global proc int[] SortList(int $list[])
{
        int $i;
        int $j;
        int $temp;
        int $flag;
        int $n = `size($list)`;

        for($i=$n-1; $i>0; $i--)
        {
                $flag = 1;
                for($j=0; $i>$j; $j++)
                {
                        if($list[$j]>$list[$j+1])
                        {
                                $flag = 0;
                                $temp = $list[$j];
                                $list[$j] = $list[$j+1];
                                $list[$j+1] = $temp;
                        }
                }
                if($flag) {
                        break;
                }
        }
        
        return $list;
}

COBOLEdit

If you are dealing with a large volume of data, use the COBOL SORT using sequential files. For sorting a WORKING STORAGE table, the following example assumes that the table is already loaded. The literals "a" indicates the size of the row, and "b" how many rows in the table.

       WORKING-STORAGE SECTION.
      *
       01  WS-SORT-AREA.
           05  WS-SORT-TABLE.
               10  WS-SORT-ROW PIC X(''a'') OCCURS ''b''.
           05  WS-TEMP-ROW     PIC X(''a'').
           05  WS-ROW-MAX      PIC S9(4) COMP VALUE ''b''.
           05  WS-SORT-MAX     PIC S9(4) COMP.
           05  WS-SORT-UP      PIC S9(4) COMP.
           05  WS-SORT-DOWN    PIC S9(4) COMP.
           05  WS-SORT-INCR    PIC S9(4) COMP.
           05  WS-SORT-TEST    PIC S9(4) COMP.
      *
        PROCEDURE DIVISION.
      *
        MY-SORT SECTION.
        MY-SORT-START.
      *
      * find the last entry
      *
           PERFORM VARYING WS-SORT-MAX FROM WS-ROW-MAX BY -1
               UNTIL WS-SORT-MAX = ZERO
               OR    WS-SORT-ROW (WS-SORT-MAX) NOT = SPACES
           END-PERFORM.
      *
      * bubble sort into required sequence
      *
           PERFORM VARYING WS-SORT-UP FROM WS-SORT-MAX BY -1
               UNTIL WS-SORT-UP = ZERO
      *
               MOVE ZERO TO WS-SORT-TEST
      *
               PERFORM VARYING WS-SORT-DOWN FROM 1 BY 1
                   UNTIL WS-SORT-DOWN = WS-SORT-UP
      *
                   ADD 1 TO WS-SORT-DOWN GIVING WS-SORT-INCR
      *
                   IF  WS-SORT-ROW (W30-SORT-DOWN)
                     > WS-SORT-ROW (W30-SORT-INCR)
      *
                       MOVE WS-SORT-ROW (WS-SORT-DOWN)
                         TO WS-TEMP-ROW
                       MOVE WS-SORT-ROW (WS-SORT-INCR)
                         TO WS-SORT-ROW (WS-SORT-DOWN)
                       MOVE WS-TEMP-ROW
                         TO WS-SORT-ROW (WS-SORT-INCR)
                       ADD 1 TO WS-SORT-TEST
                   END-IF
               END-PERFORM
      *
               IF  WS-SORT-TEST = ZERO
                   NEXT SENTENCE
               END-IF
           END-PERFORM.
      *
       MY-SORT-EXIT.
           EXIT.