Bubble sort
From CodeCodex
| Related content: |
[edit] Implementation
[edit] Pseudocode
function bubblesort (A : list[1..n]) {
var int i, j;
for i from n downto 1 {
for j from 1 to i-1 {
if (A[j] > A[j+1])
swap(A[j], A[j+1])
}
}
}
kempot jancok
[edit] Ada
Ada implementation, using user-defined type Data_T holding the values, each having type Item_T.
procedure Bubble_Sort (Data : in out Data_T) is
procedure Swap(A : in out Item_T; B : in out Item_T) is
T : constant Item_T := A;
begin
A := B;
B := T;
end Swap;
Finished : Boolean;
Top : Integer := Data'Last;
begin
loop
Finished := True;
Top := Top - 1;
for I in Data'First..Top loop
if Data(I) > Data(I + 1) then
Swap (Data(I), Data(I + 1));
Finished := False;
end if;
end loop;
exit when Finished;
end loop;
end Bubble_Sort;
[edit] Assembly
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
[edit] VISUAL BASIC
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
Next
End Sub
mölf
[edit] Pascal
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;
[edit] BLITZBASIC
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
[edit] C
1:
void bubbleSort(int *array, int length)
{
int i, j, temp;
int test; /*use this only if unsure whether the list is already sorted or not*/
for(i = length - 1; i > 0; i--)
{
test=0;
for(j = 0; j < i; j++)
{
if(array[j] > array[j+1]) /* compare neighboring elements */
{
temp = array[j]; /* swap array[j] and array[j+1] */
array[j] = array[j+1];
array[j+1] = temp;
test=1;
}
} /*end for j*/
if(test==0) break; /*will exit if the list is sorted!*/
} /*end for i*/
}/*end bubbleSort*/
2:
void bubbleSort_flag(int a[], int n)
{
int i, j, temp, flag;
for(i=n-1; i>0; i--)
{
flag = 1;
for(j=0; i>j; j++)
{
if(a[j]>a[j+1])
{
flag = 0;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
//out this block when flag is true
//i.e. inner loop performed no swaps, so the list is already sorted
if(flag)
break;
}
}
3:
void sort_len(int *tab, int len)
{
int tmp;
int again;
int i;
for (again = 1; again;)
for (again = 0, i = 0; i < (len - 1); i++)
{
if (tab[i] > tab[i + 1])
{
tmp = tab[i];
tab[i] = tab[i + 1];
tab[i + 1] = tmp;
again = 1;
}
}
}
[edit] 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);
}
[edit] 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;
}
}
}
}
[edit] 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;
}
}
}
}
[edit] 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)
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.
[edit] 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
[edit] Haskell
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)
[edit] 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;
}
[edit] 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;
}
[edit] 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]
[edit] F#
let rec bubble_sort(x) = match x with | h1::h2::t when h1 > h2 -> bubble_sort(h2::bubble_sort(h1::t)) | h::t -> h::(bubble_sort t) | [] -> [];;
Above solution doesn't work (try with [ 33; 98; 74; 13; 55; 20; 77; 45; 64; 83 ] and you'll see). This does work:
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)
[edit] 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);
[edit] 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.
[edit] Python
def bubblesort(lst):
"Sorts list 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
-- another method --
def bubble_sort(el):
while True:
for i in range(len(el)-1):
if el[i+1] < el[i]:
el[i], el[i+1] = el[i+1], el[i]
break
else: # not swapped
break
return el
[edit] Ruby
def bubble_sort(list)
list = list.clone # we should not modify original list
for i in 0..(list.length - 1)
for j in 0..(list.length - i - 2)
list[j], list[j + 1] = list[j + 1], list[j] if ( list[j + 1] <=> list[j] ) == -1
end
end
return list
end
[edit] 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)))))))
[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;
[edit] SWI-Prolog
bs(L,S) :-
append(P, [A, B|T], L),
B < A ->
append(P, [B, A|T], R),
bs(R, S)
; S = L.
[edit] 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
}
[edit] 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
[edit] 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
[edit] 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;}
}
}
[edit] References
- Wikipedia Bubble Sort
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging.
[edit] External links
- Bubble Sort Applet
- Bubble Sort Demo
- Bubble Sort Demonstration
- Lafore's Bubble Sort
- Illustrated bubble sort tutorial. Java and C++ implementations.
- Sorting Applets in C++
- Downloadable .NET Implementation of bubble sort and several other algorithms
Categories: Sort algorithms | Pseudocode | Assembly | BASIC | Blitz BASIC | C | C++ | C sharp | COBOL | Fortran | Haskell | Java | Maya Embedded Language | Objective Caml | Pascal | Perl | PHP | Progress ABL/4GL | Python | Ruby | Scheme | Seed7 | Turing | VBA
