# Difference between revisions of "Bubble sort"

 Related content:

## Implementation

### Pseudocode

prozedur bubbleSort( A : Liste sortierbarer Elemente )

n := Länge( A )
wiederhole
vertauscht := falsch
für jedes i von 1 bis n - 1 wiederhole
falls A[ i ] > A[ i + 1 ] dann
vertausche( A[ i ], A[ i + 1 ] )
vertauscht := wahr
ende falls
ende für
n := n - 1
solange vertauscht und n > 1

prozedur ende

No complaints on this end, simlpy a good piece.

### AutoIt

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

### Blitz BASIC

Function BubbleSortArray( Array[ MaxIndices ] , IndicesUsed = MaxIndices )
Local Bwd,Fwd
Local Swapped = True

For Bwd = IndicesUsed To 1 Step -1
Swapped = False
For Fwd = 1 To Bwd-1
If Array[ Fwd ] > Array[ Fwd+1 ]
; Swap indices using XOR
Array[ Fwd   ] = Array[ Fwd ] Xor Array[ Fwd+1 ]
Array[ Fwd+1 ] = Array[ Fwd ] Xor Array[ Fwd+1 ]
Array[ Fwd   ] = Array[ Fwd ] Xor Array[ Fwd+1 ]
Swapped = True
Endif
Next
If Not Swapped
Exit
Endif
Next
End Function

### C++

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

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

### C#

static void BubbleSort(IComparable[] array)
{
int i, j;
IComparable temp;
for (i = array.Length - 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;
}
}
}
}

### C# 2.0

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

### COBOL

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)
END-IF
END-PERFORM
*
IF  WS-SORT-TEST = ZERO
NEXT SENTENCE
END-IF
END-PERFORM.
*
MY-SORT-EXIT.
EXIT.

### D

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

### Erlang

bubble_sort([]) -> [];
bubble_sort(List) when is_list(List) ->
bubble_sort(List, []).

bubble_sort([X], Sorted) -> [X | Sorted];
bubble_sort(List, Sorted) ->
[Max | Rest] = bubble_move(List, []),
bubble_sort(Rest, [Max | Sorted]).

bubble_move([X], Rest) -> [X | Rest];
bubble_move([X, Y | T], Rest) ->
if X > Y -> bubble_move([X | T], [Y | Rest]);
true -> bubble_move([Y | T], [X | Rest])
end.

### F#

let rec bubbleSort ls =
let rec bs ls =
match ls with
| [] -> []
| x::y::z when x > y -> y::(bs (x::z))
| x::y -> x::(bs y)
let rec go ls n =
match n with
| 0 -> ls
| x -> go (bs ls) (x - 1)
go ls (Seq.length ls)

### Fortran

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

### GML

//Arg0 = number of items; Arg1+ = items;

//Variable declarations
var inum,swapped;
items=0;
inum=argument0;
swapped=0;

//To collect the items into an array
for (i=0;i<inum;i+=1) {
items[i]=argument[i+1];
}

//Main bubble sort loop
while (swapped < inum-1) {
for (i=0;i<inum-1;i+=1) {
if items[i] > items[i + 1] {
var k;
k=items[i];
items[i]=items[i+1];
items[i+1]=k;
}
else {swapped+=1;}
}
}

### Go

func BubbleSort(nums []int) {
unsorted := true
for unsorted {
unsorted = false
for i := len(nums) - 1; i > 0; i-- {
if nums[i] < nums[i-1] {
nums[i], nums[i-1] = nums[i-1], nums[i]
unsorted = true
}
}
}
}

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

### Java

1.

//Sorts an integer array in ascending order.
//Parameters:
//   data - reference to the integer array to sort, must not be null
//Postcondition:
//   The array is sorted in ascending order.

public static void bubbleSort(int[] data)
{
for (int k = 0; k < data.length - 1; k++)
{
boolean isSorted = true;

for (int i = 1; i < data.length - k; i++)
{
if (data[i] < data[i - 1])
{
int tempVariable = data[i];
data[i] = data[i - 1];
data[i - 1] = tempVariable;

isSorted = false;

}
}

if (isSorted)
break;
}
}

2:

// another possibility
static int[] BubbleSort(int[] nums)
{
boolean unsorted = true;
while (unsorted)
{
unsorted = false;
for (int i = nums.length - 1; i > 0; i--)
{
if (nums[i] < nums[i-1])
{
int temp = nums[i];
nums[i] = nums[i-1];
nums[i-1] = temp;
unsorted = true;
}
}
}
return nums;
}

### JavaScript

JavaScript Implementation with simple HTML test page

<html>
<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>
<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>
I just dont get this

### Maya Embedded Language

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

### MEL

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

### OCaml

When two adjacent elements are in the wrong order, reverse them and recurse:

let rec sweep = function
h1 :: h2 :: t when h1 > h2 -> h2 :: sweep (h1 :: t)
| h1 :: t -> h1 :: sweep t
| [] -> [];;
let rec bubble l =
let l' = sweep l in
if l <> l' then bubble l'
else l;;

For example:

# bubble [1;9;2;8;3;7;4;6;5];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

That's a smart answer to a dififcult question.

### Perl

1:

sub bubbleSort {
my @list   = @_;
my \$sorted = 0;

while ( not \$sorted ) {
\$sorted = 1; # Innocent until proven guilty.

for my \$current ( 1 .. \$#list ) {
my \$previous = \$current - 1;

if ( \$list[\$current] < \$list[\$previous] ) {
(\$list[\$current], \$list[\$previous]) = (\$list[\$previous], \$list[\$current]);

\$sorted = 0;
}
}
}

return @list;
}

my @unsorted = qw( 1 7 6 3 83 64 8281 0 38 1 );
my @sorted = bubbleSort(@unsorted);

2:

sub bubble_sort {
my @a = @_;
for my \$ii (0 .. \$#a) {
for my \$jj (\$ii + 1 .. \$#a) {
@a[\$ii, \$jj] = @a[\$jj, \$ii] if \$a[\$jj] < \$a[\$ii];
};
};
return @a;
};

print bubble_sort qw(6 5 3 8 7 4);

### PHP

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

### Progress ABL/4GL

FUNCTION BubbleSort RETURNS CHARACTER
(INPUT pcArray AS CHARACTER):

DEFINE VARIABLE cTempArray AS CHARACTER NO-UNDO.
DEFINE VARIABLE i          AS INTEGER   NO-UNDO.
DEFINE VARIABLE j          AS INTEGER   NO-UNDO.
DEFINE VARIABLE iEntries   AS INTEGER   NO-UNDO.

iEntries = NUM-ENTRIES(pcArray).

DO i = iEntries TO 1 BY -1:
DO j = 1 TO i - 1:
IF ENTRY(j, pcArray) > ENTRY(j + 1, pcArray) THEN
DO:
cTempArray            = ENTRY(j, pcArray).
ENTRY(j, pcArray)     = ENTRY(j + 1, pcArray).
ENTRY(j + 1, pcArray) = cTempArray.
END.
END.
END.

RETURN pcArray.

END FUNCTION.

### Python

def BubbleSort(lst):
lst = list(lst) #copy collection to list
for passesLeft in range(len(lst)-1, 0, -1):
for i in range(passesLeft):
if lst[i] < lst[i + 1]:
lst[i], lst[i + 1] = lst[i + 1], lst[i]
return lst

Another method

def BubbleSort2(lst):
lst = list(lst)
swapped = True
while swapped:
swapped = False
for i in range(len(lst)-1):
if lst[i] > lst[i+1]:
lst[i], lst[i+1] = lst[i+1], lst[i]
swapped = True
return lst

### QuickBASIC

CLS

DIM NameArray\$(1000)

i = 0

' Loop through and read names in data ...
DO WHILE Name\$ <> "*EOD"
i = i + 1
NameArray\$(i) = 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 Zimmerman,
DATA Smith,
DATA Jones,
DATA *EOD

### Ruby

def bubble_sort(list)
list = list.dup   # we should not modify original list
for i in 0...list.length
for j in 0..(list.length - i - 2)
list[j], list[j + 1] = list[j + 1], list[j]  if list[j + 1] < list[j]
end
end
return list
end

### Scheme

1: Using a recursive procedure:

(define (bubble-sort vector key <<? ==?)
(define (bubble-swap vector idx1 idx2)
(let ((temp (vector-ref vector idx1)))
(vector-set! vector idx1 (vector-ref vector idx2))
(vector-set! vector idx2 temp)
#t))
(define (bubble-up outer-idx inner-idx has-changed)
(if (<= inner-idx outer-idx)
(bubble-up outer-idx
(+ inner-idx 1)
(if (<<? (key (vector-ref vector (+ inner-idx 1)))
(key (vector-ref vector inner-idx)))
(bubble-swap vector inner-idx (+ inner-idx 1))
has-changed))
has-changed))
(define (bubble-sort-iter unsorted-idx)
(if (>= unsorted-idx 0)
(if (bubble-up unsorted-idx 0 #f)
(bubble-sort-iter (- unsorted-idx 1)))))
(bubble-sort-iter (- (vector-length vector) 2)))

2: Using the do-loop:

(define (bubble-sort vector key <<? ==?)
(define (bubble-swap vector idx1 idx2)
(let ((temp (vector-ref vector idx1)))
(vector-set! vector idx1 (vector-ref vector idx2))
(vector-set! vector idx2 temp)
#t))
(do ((unsorted-idx (- (vector-length vector) 2) (- unsorted-idx 1)))
((or (< unsorted-idx 0)
(not (do ((inner-idx
0
(+ inner-idx 1))
(has-changed
#f
(if (<<? (key (vector-ref vector (+ inner-idx 1)))
(key (vector-ref vector inner-idx)))
(bubble-swap vector inner-idx (+ inner-idx 1))
has-changed)))
((> inner-idx unsorted-idx) has-changed)
'()))))
'()))

3: Again using DO, but this time implementing the same algorithm as the Python code above, which is much simpler than the other Scheme examples.

(define (bubblesort! v)
(do ((passes-left (- (vector-length v)
1)
(- passes-left 1)))
((= passes-left 0))
(do ((index 0 (+ index 1)))
((= index (- (vector-length v)
1)))
(if (< (vector-ref v index)
(vector-ref v (+ index 1)))
(vector-swap! v index (+ index 1)))))
v)
;; VECTOR-SWAP! is available in SRFI 43.
;; If your Scheme system does not provide SRFI 43, here is a quick
;; definition:
(define (vector-swap! v i j)
(let ((t (vector-ref v i)))
(vector-set! v i (vector-ref v j))
(vector-set! v j t)))

4: Written in a non-ugly way

(define (bubble-sort list)
(define (swap index1 index2)
(let ((item1 (list-ref list index1))
(item2 (list-ref list index2)))
(set-car! (list-tail list index1) item2)
(set-car! (list-tail list index2) item1)))
(let float ((index 0))
(cond ((= (+ index 1) (length list)) list)
((< (list-ref list index)
(list-ref list (+ index 1)))
(float (+ index 1)))
((= (list-ref list index)
(list-ref list (+ index 1)))
(float (+ index 1)))
(else
(swap index (+ index 1))
(float (if (= index 0) 0 (- index 1)))))))

### Seed7

const proc: bubbleSort (inout array elemType: arr) is func
local
var boolean: swapped is FALSE;
var integer: i is 0;
var elemType: help is elemType.value;
begin
repeat
swapped := FALSE;
for i range 1 to length(arr) - 1 do
if arr[i] > arr[i + 1] then
help := arr[i];
arr[i] := arr[i + 1];
arr[i + 1] := help;
swapped := TRUE;
end if;
end for;
until not swapped;
end func;

Original source: [1]

### SWI-Prolog

bs(L,S) :-
append(P, [A, B|T], L),
B < A ->
append(P, [B, A|T], R),
bs(R, S)
; S = L.

### TCL

proc bubble_sort {a} {
if {[llength \$a] >= 2} {
for {set i [expr [llength \$a]-1]} {\$i > 0} {incr i -1} {
set has_swapped "FALSE"
for {set j 0} {\$j < \$i} {incr j} {
if {[lindex \$a \$j] > [lindex \$a [expr \$j + 1]]} {
set temp [lindex \$a \$j]
set a [lreplace \$a \$j \$j [lindex \$a [expr \$j + 1]]]
set a [lreplace \$a [expr \$j + 1] [expr \$j + 1] \$temp]
set has_swapped "TRUE"
}
}
if {\$has_swapped == "FALSE"} {
break
}
}
}
return \$a
}

### Turing

var nombres, limit : int
get nombres
get limit
var g : int := 0
var last : int := limit
var sure : boolean := false
var rann : array 1 .. nombres of int
for i : 1 .. nombres
rann (i) := Rand.Int (0, limit)
end for
loop
for d : 1 .. nombres - 1
if rann (d) > rann (d + 1) then
g := rann (d)
rann (d) := rann (d + 1)
rann (d + 1) := g
sure := false
end if
end for
exit when sure
sure := true
end loop
for b : 1 .. upper (rann)
put " ", rann (b) ..
end for

### VBA

Option Base 1

Private Sub bubble(N as integer, array() as integer)

'N is the number of integers in the array'

Dim I as Integer
Dim J as Integer
Dim P as Integer
Dim Temp as Integer

For I = n - 1 To 1 Step -1
P=0
For J = 1 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

### Visual Basic

Sub Bubblesort(Array() as Integer, Length as Integer)
Dim I As Integer
Dim J As Integer
Dim Temp As Integer
Dim Length As Integer
Dim Array() As String = {}

For I = Length - 1 To 1 Step -1 'the last element on the array does not get sorted.
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
Next
End Sub