Sorting algorithms/Bubble sort: Difference between revisions
→{{header|C}}: there is no point in making a local variable const |
|||
Line 227: | Line 227: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<lang c>void bubble_sort(int *a, int n) { |
<lang c>void bubble_sort(int *a, int n) { |
||
int |
int j, t = 1; |
||
while (n-- && t) |
|||
for (j = t = 0; j < |
for (j = t = 0; j < n; j++) { |
||
if (a[j] <= a[j + 1]) continue; |
if (a[j] <= a[j + 1]) continue; |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
} |
|||
} |
} |
||
Revision as of 02:48, 25 August 2011
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:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) 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(n2) 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
- References
- The article on Wikipedia.
- Dance interpretation.
ActionScript
<lang 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; }</lang>
Ada
<lang 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;</lang>
ALGOL 68
<lang algol68>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))
)</lang> Output:
Before: +1 +6 +3 +5 +2 +9 +8 +4 +7 +0 After: +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
AutoHotkey
<lang 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
}</lang>
AWK
Sort the standard input and print it to standard output. <lang awk>{ # 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] }
}</lang>
BASIC
Assume numbers are in a DIM of size "size" called "nums". <lang 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)</lang>
BBC BASIC
The Bubble sort is very inefficient for 99% of cases. This subroutine uses a couple of 'tricks' to try and mitigate the inefficiency to a limited extent. <lang bbcbasic>DEF PROC_BubbleSort(Size%)
I%=Size%+1 REPEAT
I%-=1 LastChange%=2 FOR J% = 2 TO I% IF data%(J%-1) > data%(J%) THEN SWAP data%(J%-1),data%(J%) LastChange%=J% ENDIF NEXT J% I%=LastChange%
UNTIL I% = 2
ENDPROC</lang>
C
<lang c>void bubble_sort(int *a, int n) { int j, t = 1; while (n-- && t) for (j = t = 0; j < n; j++) { if (a[j] <= a[j + 1]) continue; t = a[j], a[j] = a[j + 1], a[j + 1] = t; t=1; } }
int main(void) { int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1}; bubble_sort(a, sizeof(a) / sizeof(a[0]));
return 0; }</lang>
C++
<lang cpp>#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; std::swap(array[i], array[i+1]); } } size--; }
}
template< typename TYPE > void print(TYPE val) {
std::cout << val << " ";
}
int main() {
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;
}</lang>
C#
<lang 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 + " "); } }
}</lang>
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. <lang clean>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</lang>
Using it to sort an array of a hundred numbers: <lang clean>Start :: {Int} Start = bsort {x \\ x <- [100,99..1]}</lang>
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.
<lang clojure>(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])))</lang>
Purely functional version working on Clojure sequences: <lang clojure>(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]))</lang>
COBOL
This is a complete program that reads in a file of integers and sorts them. <lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. BUBBLESORT. AUTHOR. DAVE STRATFORD. DATE-WRITTEN. MARCH 2010. INSTALLATION. HEXAGON SYSTEMS LIMITED.
ENVIRONMENT DIVISION. CONFIGURATION SECTION. SOURCE-COMPUTER. ICL VME. OBJECT-COMPUTER. ICL VME.
INPUT-OUTPUT SECTION. FILE-CONTROL. SELECT FA-INPUT-FILE ASSIGN FL01. SELECT FB-OUTPUT-FILE ASSIGN FL02.
DATA DIVISION. FILE SECTION.
FD FA-INPUT-FILE. 01 FA-INPUT-REC. 03 FA-DATA PIC S9(6).
FD FB-OUTPUT-FILE. 01 FB-OUTPUT-REC PIC S9(6).
WORKING-STORAGE SECTION. 01 WA-IDENTITY. 03 WA-PROGNAME PIC X(10) VALUE "BUBBLESORT". 03 WA-VERSION PIC X(6) VALUE "000001".
01 WB-TABLE. 03 WB-ENTRY PIC 9(8) COMP SYNC OCCURS 100000 INDEXED BY WB-IX-1.
01 WC-VARS. 03 WC-SIZE PIC S9(8) COMP SYNC. 03 WC-TEMP PIC S9(8) COMP SYNC. 03 WC-END PIC S9(8) COMP SYNC. 03 WC-LAST-CHANGE PIC S9(8) COMP SYNC.
01 WF-CONDITION-FLAGS. 03 WF-EOF-FLAG PIC X. 88 END-OF-FILE VALUE "Y". 03 WF-EMPTY-FILE-FLAG PIC X. 88 EMPTY-FILE VALUE "Y".
PROCEDURE DIVISION. A-MAIN SECTION. A-000. PERFORM B-INITIALISE. IF NOT EMPTY-FILE PERFORM C-SORT. PERFORM D-FINISH.
A-999. STOP RUN.
B-INITIALISE SECTION. B-000. DISPLAY "*** " WA-PROGNAME " VERSION " WA-VERSION " STARTING ***".
MOVE ALL "N" TO WF-CONDITION-FLAGS. OPEN INPUT FA-INPUT-FILE. SET WB-IX-1 TO 0.
READ FA-INPUT-FILE AT END MOVE "Y" TO WF-EOF-FLAG WF-EMPTY-FILE-FLAG.
PERFORM BA-READ-INPUT UNTIL END-OF-FILE.
CLOSE FA-INPUT-FILE.
SET WC-SIZE TO WB-IX-1.
B-999. EXIT.
BA-READ-INPUT SECTION. BA-000. SET WB-IX-1 UP BY 1. MOVE FA-DATA TO WB-ENTRY(WB-IX-1).
READ FA-INPUT-FILE AT END MOVE "Y" TO WF-EOF-FLAG.
BA-999. EXIT.
C-SORT SECTION. C-000. DISPLAY "SORT STARTING".
MOVE WC-SIZE TO WC-END. PERFORM E-BUBBLE UNTIL WC-END = 1.
DISPLAY "SORT FINISHED".
C-999. EXIT.
D-FINISH SECTION. D-000. OPEN OUTPUT FB-OUTPUT-FILE. SET WB-IX-1 TO 1.
PERFORM DA-WRITE-OUTPUT UNTIL WB-IX-1 > WC-SIZE.
CLOSE FB-OUTPUT-FILE.
DISPLAY "*** " WA-PROGNAME " FINISHED ***".
D-999. EXIT.
DA-WRITE-OUTPUT SECTION. DA-000. WRITE FB-OUTPUT-REC FROM WB-ENTRY(WB-IX-1). SET WB-IX-1 UP BY 1.
DA-999. EXIT.
E-BUBBLE SECTION. E-000. MOVE 1 TO WC-LAST-CHANGE.
PERFORM F-PASS VARYING WB-IX-1 FROM 1 BY 1 UNTIL WB-IX-1 = WC-END.
MOVE WC-LAST-CHANGE TO WC-END.
E-999. EXIT.
F-PASS SECTION. F-000. IF WB-ENTRY(WB-IX-1) > WB-ENTRY(WB-IX-1 + 1) SET WC-LAST-CHANGE TO WB-IX-1 MOVE WB-ENTRY(WB-IX-1) TO WC-TEMP MOVE WB-ENTRY(WB-IX-1 + 1) TO WB-ENTRY(WB-IX-1) MOVE WC-TEMP TO WB-ENTRY(WB-IX-1 + 1).
F-999. EXIT.</lang>
Common Lisp
Bubble sort an sequence in-place, using the < operator for comparison if no comaprison function is provided <lang lisp>(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)))))</lang>
<lang lisp>(bubble-sort (list 5 4 3 2 1))</lang>
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.
<lang lisp>(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))))</lang>
D
<lang d>import std.stdio, std.algorithm;
void bubbleSort(Range)(Range data) {
int itemCount = data.length; bool hasChanged = false;
do { hasChanged = false; itemCount--; foreach (i; 0 .. itemCount) if (data[i] > data[i + 1]) { swap(data[i], data[i + 1]); hasChanged = true; } } while (hasChanged);
}
void main() {
auto array = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4]; array.bubbleSort(); writeln(array);
}</lang> Output:
[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]
Delphi
Dynamic array is a 0-based array of variable length
Static array is an arbitrary-based array of fixed length <lang Delphi>program TestBubbleSort;
{$APPTYPE CONSOLE}
{.$DEFINE DYNARRAY} // remove '.' to compile with dynamic array
type
TItem = Integer; // declare ordinal type for array item
{$IFDEF DYNARRAY}
TArray = array of TItem; // dynamic array
{$ELSE}
TArray = array[0..15] of TItem; // static array
{$ENDIF}
procedure BubbleSort(var A: TArray); var
Item: TItem; K, L, J: Integer;
begin
L:= Low(A) + 1; repeat K:= High(A); for J:= High(A) downto L do begin if A[J - 1] > A[J] then begin Item:= A[J - 1]; A[J - 1]:= A[J]; A[J]:= Item; K:= J; end; end; L:= K + 1; until L > High(A);
end;
var
A: TArray; I: Integer;
begin {$IFDEF DYNARRAY}
SetLength(A, 16);
{$ENDIF}
for I:= Low(A) to High(A) do A[I]:= Random(100); for I:= Low(A) to High(A) do Write(A[I]:3); Writeln; BubbleSort(A); for I:= Low(A) to High(A) do Write(A[I]:3); Writeln; Readln;
end.</lang> Output:
0 3 86 20 27 67 31 16 37 42 8 47 7 84 5 29 0 3 5 7 8 16 20 27 29 31 37 42 47 67 84 86
E
<lang 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 })
}</lang>
(Uses the primitive __loop directly because it happens to map to the termination test for this algorithm well.)
Eiffel
This solution is presented in two classes. The first is a simple application that creates a set, an instance of MY_SORTED_SET
, and adds elements to the set in unsorted order. It iterates across the set printing the elements, then it sorts the set, and reprints the elements.
<lang eiffel>class
APPLICATION
create
make
feature
make -- Create and print sorted set do create my_set.make my_set.put_front (2) my_set.put_front (6) my_set.put_front (1) my_set.put_front (5) my_set.put_front (3) my_set.put_front (9) my_set.put_front (8) my_set.put_front (4) my_set.put_front (10) my_set.put_front (7) print ("Before: ") across my_set as ic loop print (ic.item.out + " ") end print ("%NAfter : ") my_set.sort across my_set as ic loop print (ic.item.out + " ") end end
my_set: MY_SORTED_SET [INTEGER] -- Set to be sorted
end</lang>
The second class is MY_SORTED_SET
.
<lang eiffel>class
MY_SORTED_SET [G -> COMPARABLE]
inherit
TWO_WAY_SORTED_SET [G] redefine sort end
create
make
feature
sort -- Sort with bubble sort local l_unchanged: BOOLEAN l_item_count: INTEGER l_temp: G do from l_item_count := count until l_unchanged loop l_unchanged := True l_item_count := l_item_count - 1 across 1 |..| l_item_count as ic loop if Current [ic.item] > Current [ic.item + 1] then l_temp := Current [ic.item] Current [ic.item] := Current [ic.item + 1] Current [ic.item + 1] := l_temp l_unchanged := False end end end end
end</lang>
This class inherits from the Eiffel library class TWO_WAY_SORTED_SET
, which implements sets whose elements are comparable. Therefore, the set can be ordered and in fact is kept so under normal circumstances.
MY_SORTED_SET
redefines only the routine sort
which contains the implementation of the sort algorithm. The implementation in the redefined version of sort
in MY_SORTED_SET
uses a bubble sort.
Output:
Before: 7 10 4 8 9 3 5 1 6 2 After : 1 2 3 4 5 6 7 8 9 10
TWO_WAY_SORTED_SET
is implemented internally as a list. For this example, we use the feature put_front
which explicitly adds each new element to the beginning of the list, allowing us to show that the elements are unordered until we sort them. It also causes, in the "Before" output, the elements to be printed in the reverse of the order in which they were added. Under normal circumstances, we would use the feature extend
(rather than put_front
) to add elements to the list. This would assure that the order was maintained even as elements were added.
Euphoria
<lang euphoria>function bubble_sort(sequence s)
object tmp integer changed for j = length(s) to 1 by -1 do changed = 0 for i = 1 to j-1 do if compare(s[i], s[i+1]) > 0 then tmp = s[i] s[i] = s[i+1] s[i+1] = tmp changed = 1 end if end for if not changed then exit end if end for return s
end function
include misc.e constant s = {4, 15, "delta", 2, -31, 0, "alfa", 19, "gamma", 2, 13, "beta", 782, 1}
puts(1,"Before: ") pretty_print(1,s,{2}) puts(1,"\nAfter: ") pretty_print(1,bubble_sort(s),{2})</lang>
Output:
Before: { 4, 15, "delta", 2, -31, 0, "alfa", 19, "gamma", 2, 13, "beta", 782, 1 } After: { -31, 0, 1, 2, 2, 4, 13, 15, 19, 782, "alfa", "beta", "delta", "gamma" }
Factor
<lang 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! ;</lang>
It is possible to pass your own comparison operator to sort!
, so you can f.e. sort your sequence backwards with passing [ >=< ]
into it.
<lang factor>10 [ 10000 random ] replicate [ "Before: " write . ] [ "Natural: " write [ natural-sort! ] keep . ] [ "Reverse: " write [ [ >=< ] sort! ] keep . ] tri</lang>
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 }
Forth
Sorts the 'cnt' cells stored at 'addr' using the test stored in the deferred word 'bubble-test'. Uses forth local variables for clarity.
<lang forth>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 ;</lang>
This is the same algorithm done without the local variables:
<lang forth>: 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 ;</lang>
Version with O(n) best case: <lang forth>: 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 ;</lang>
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
<lang 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</lang>
Go
Per task pseudocode: <lang go>package main
import "fmt"
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84} fmt.Println("unsorted:", list)
bubblesort(list) fmt.Println("sorted! ", list)
}
func bubblesort(a []int) {
for itemCount := len(a) - 1; ; itemCount-- { hasChanged := false for index := 0; index < itemCount; index++ { if a[index] > a[index+1] { a[index], a[index+1] = a[index+1], a[index] hasChanged = true } } if hasChanged == false { break } }
}</lang>
More generic version that can sort anything that implements sort.Interface
:
<lang go>package main
import (
"sort" "fmt"
)
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84} fmt.Println("unsorted:", list)
bubblesort(sort.IntArray(list)) fmt.Println("sorted! ", list)
}
func bubblesort(a sort.Interface) {
for itemCount := a.Len() - 1; ; itemCount-- { hasChanged := false for index := 0; index < itemCount; index++ { if a.Less(index+1, index) { a.Swap(index, index+1) hasChanged = true } } if hasChanged == false { break } }
}</lang>
Groovy
Solution: <lang groovy>def makeSwap = { a, i, j = i+1 -> print "."; ai,j = aj,i }
def checkSwap = { a, i, j = i+1 -> [(a[i] > a[j])].find { it }.each { makeSwap(a, i, j) } }
def bubbleSort = { list ->
boolean swapped = true while (swapped) { swapped = (1..<list.size()).any { checkSwap(list, it-1) } } list
}</lang>
Test Program: <lang groovy>println bubbleSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]) println bubbleSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])</lang>
Output:
..............................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99] .........................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
Haskell
This version checks for changes in a separate step for simplicity, because Haskell has no variables to track them with. <lang haskell>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</lang>
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.
<lang haskell>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</lang>
HicEst
<lang fortran>SUBROUTINE Bubble_Sort(a)
REAL :: a(1) DO j = LEN(a)-1, 1, -1 swapped = 0 DO i = 1, j IF (a(i) > a(i+1)) THEN temp = a(i) a(i) = a(i+1) a(i+1) = temp swapped = 1 ENDIF ENDDO IF (swapped == 0) RETURN ENDDO
END</lang>
Icon and Unicon
Icon/Unicon implementation of a bubble sort <lang Icon>procedure main() #: demonstrate various ways to sort a list and string
demosort(bubblesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
procedure bubblesort(X,op) #: return sorted list local i,swapped
op := sortop(op,X) # select how and what we sort swapped := 1 while \swapped := &null do # the sort every i := 2 to *X do if op(X[i],X[i-1]) then X[i-1] :=: X[swapped := i] return X
end</lang>
Sample output:
Sorting Demo using procedure bubblesort on list : [ 3 14 1 5 9 2 6 3 ] with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms) with op = "numeric": [ 1 2 3 3 5 6 9 14 ] (0 ms) with op = "string": [ 1 14 2 3 3 5 6 9 ] (0 ms) with op = ">>": [ 9 6 5 3 3 2 14 1 ] (0 ms) with op = ">": [ 14 9 6 5 3 3 2 1 ] (0 ms) with op = procedure cmp: [ 1 2 3 3 5 6 9 14 ] (1 ms) with op = "cmp": [ 1 2 3 3 5 6 9 14 ] (0 ms) on string : "qwerty" with op = &null: "eqrtwy" (0 ms)
The following code supports this and other sorting demonstrations.
- Sorting illustrates a difference in the way Icon and Unicon handles data types. Built-in operators for comparing data types make a syntactic distinction between numeric and string types, and sorting structured and user-defined types require custom code. An added complication arises because mixed types are allowed. Two approaches are possible here: (1) that taken by the built-in sort which sorts first by type and then value The sort order of types is: &null, integer, real, string, cset, procedure, list, set, table, and record; and (2) Coercion of types which is used here (and implemented in 'sortop') to decide on using string or numeric sorting. These sorts will not handle more exotic type mixes.
- The 'sortop' procedure allows various methods of comparison be selected including customized ones. The example could be made more general to deal with coercion of types like cset to string (admittedly an uninteresting example as csets are already sorted). Custom comparators are shown by and example procedure 'cmp'.
- 'demosort' can apply different sorting procedures and operators to lists and strings to show how this works. The routines 'displaysort' and 'writex' are helpers.
<lang icon>invocable all # for op
procedure sortop(op,X) #: select how to sort
op := case op of { "string": "<<" "numeric": "<" &null: if type(!X) == "string" then "<<" else "<" default: op }
return proc(op, 2) | runerr(123, image(op)) end
procedure cmp(a,b) #: example custom comparison procedure
return a < b # Imagine a complex comparison test here!
end
procedure demosort(sortproc,L,s) # demonstrate sort on L and s
write("Sorting Demo using ",image(sortproc)) writes(" on list : ") writex(L) displaysort(sortproc,L) # default string sort displaysort(sortproc,L,"numeric") # explicit numeric sort displaysort(sortproc,L,"string") # explicit string sort displaysort(sortproc,L,">>") # descending string sort displaysort(sortproc,L,">") # descending numeric sort displaysort(sortproc,L,cmp) # ascending custom comparison displaysort(sortproc,L,"cmp") # ascending custom comparison writes(" on string : ") writex(s) displaysort(sortproc,s) # sort characters in a string write() return
end
procedure displaysort(sortproc,X,op) #: helper to show sort behavior local t,SX
writes(" with op = ",left(image(op)||":",15)) X := copy(X) t := &time SX := sortproc(X,op) writex(SX," (",&time - t," ms)") return
end
procedure writex(X,suf[]) #: helper for displaysort
if type(X) == "string" then writes(image(X)) else { writes("[") every writes(" ",image(!X)) writes(" ]") } every writes(!suf) write()
return end</lang>
J
<lang j>bubbleSort=: (([ (<. , >.) {.@]) , }.@])/^:_</lang>
Test program:
<lang j> ?. 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</lang>
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.
Java
Bubble sorting (ascending) an array of any Comparable type: <lang java>public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
boolean changed = false; do { changed = false; for (int a = 0; a < comparable.length - 1; a++) { if (comparable[a].compareTo(comparable[a + 1]) > 0) { E tmp = comparable[a]; comparable[a] = comparable[a + 1]; comparable[a + 1] = tmp; changed = true; } } } while (changed);
}</lang>
For descending, simply switch the direction of comparison: <lang java>if (comparable[a].compareTo(comparable[b]) < 0){
//same swap code as before
}</lang>
JavaScript
<lang 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;
}</lang>
<lang 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; var tmp = this[i - 1]; this[i - 1] = this[i]; this[i] = tmp; } } } return this;
}</lang>
Example: <lang javascript>var my_arr = ["G", "F", "C", "A", "B", "E", "D"]; my_arr.bubblesort(); print(my_arr);</lang>
Output:
A,B,C,D,E,F,G
Io
<lang Io> List do(
bubblesort := method( t := true while( t, t := false for( j, 0, self size - 2, if( self at( j ) start > self at( j+1 ) start, self swapIndices( j,j+1 ) t := true ) ) ) return( self ) )
) </lang>
Liberty BASIC
<lang lb>
itemCount = 20 dim item(itemCount) for i = 1 to itemCount item(i) = int(rnd(1) * 100) next i print "Before Sort" for i = 1 to itemCount print item(i) next i print: print counter = itemCount do hasChanged = 0 for i = 1 to counter - 1 if item(i) > item(i + 1) then temp = item(i) item(i) = item(i + 1) item(i + 1) = temp hasChanged = 1 end if next i counter =counter -1 loop while hasChanged = 1 print "After Sort" for i = 1 to itemCount print item(i) next i
end </lang>
Lisaac
<lang 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};
);</lang>
Lua
<lang 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 </lang>
Example: <lang lua> 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 </lang>
Lucid
[1] <lang lucid>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</lang>
M4
<lang 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')</lang>
Output:
17 63 80 55 90 88 25 9 71 38 9 17 25 38 55 63 71 80 88 90
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: <lang Mathematica>BubbleSort[input_] := input //. {a___, i_, j_, b___} /; OrderedQ[{j, i}] :> {a, j, i, b}</lang> Example: <lang Mathematica>BubbleSort[{10, 3, 7, 1, 4, 3, 8, 13, 9}]</lang> gives back: <lang Mathematica>{1, 3, 3, 4, 7, 8, 9, 10, 13}</lang>
MATLAB
<lang MATLAB>function list = bubbleSort(list)
hasChanged = true; itemCount = numel(list); while(hasChanged) hasChanged = false; itemCount = itemCount - 1; for index = (1:itemCount) if(list(index) > list(index+1)) list([index index+1]) = list([index+1 index]); %swap hasChanged = true; end %if end %for end %while
end %bubbleSort</lang>
Sample Output: <lang MATLAB>bubbleSort([5 3 8 4 9 7 6 2 1])
ans =
1 2 3 4 5 6 7 8 9</lang>
MAXScript
<lang 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
)</lang>
-- Usage
<lang maxscript>myArr = #(9, 8, 7, 6, 5, 4, 3, 2, 1) myArr = bubbleSort myArr</lang>
MMIX
<lang mmix>Ja IS $127
LOC Data_Segment
DataSeg GREG @ Array IS @-Data_Segment
OCTA 999,200,125,1,1020,40,4,5,60,100
ArrayLen IS (@-Array-Data_Segment)/8
NL IS @-Data_Segment BYTE #a,0 LOC @+(8-@)&7
Buffer IS @-Data_Segment
LOC #1000 GREG @
sorted IS $5 i IS $6 size IS $1 a IS $0 t IS $20 t1 IS $21 t2 IS $22 % Input: $0 ptr to array, $1 its length (in octabyte) % Trashed: $5, $6, $1, $20, $21, $22 BubbleSort SETL sorted,1 % sorted = true
SUB size,size,1 % size-- SETL i,0 % i = 0
3H CMP t,i,size % i < size ?
BNN t,1F % if false, end for loop 8ADDU $12,i,a % compute addresses of the ADDU t,i,1 % octas a[i] and a[i+1] 8ADDU $11,t,a LDO t1,$12,0 % get their values LDO t2,$11,0 CMP t,t1,t2 % compare BN t,2F % if t1<t2, next STO t1,$11,0 % else swap them STO t2,$12,0 SETL sorted,0 % sorted = false
2H INCL i,1 % i++
JMP 3B % next (for loop)
1H PBZ sorted,BubbleSort % while sorted is false, loop
GO Ja,Ja,0
% Help function (Print an octabyte) % Input: $0 (the octabyte) BufSize IS 64
GREG @
PrintInt8 ADDU t,DataSeg,Buffer % get buffer address
ADDU t,t,BufSize % end of buffer SETL t1,0 % final 0 for Fputs STB t1,t,0
1H SUB t,t,1 % t--
DIV $0,$0,10 % ($0,rR) = divmod($0,10) GET t1,rR % get reminder INCL t1,'0' % turn it into ascii digit STB t1,t,0 % store it PBNZ $0,1B % if $0 /= 0, loop OR $255,t,0 % $255 = t TRAP 0,Fputs,StdOut GO Ja,Ja,0 % print and return
Main ADDU $0,DataSeg,Array % $0 = Array address
SETL $1,ArrayLen % $1 = Array Len GO Ja,BubbleSort % BubbleSort it SETL $4,ArrayLen % $4 = ArrayLen
ADDU $3,DataSeg,Array % $3 = Array address 2H BZ $4,1F % if $4 == 0, break
LDO $0,$3,0 % $0 = * ($3 + 0) GO Ja,PrintInt8 % print the octa ADDU $255,DataSeg,NL % add a trailing newline
TRAP 0,Fputs,StdOut
ADDU $3,$3,8 % next octa SUB $4,$4,1 % $4--
JMP 2B % loop 1H XOR $255,$255,$255
TRAP 0,Halt,0 % exit(0)</lang>
Modula-2
<lang modula2>PROCEDURE BubbleSort(VAR a: ARRAY OF INTEGER);
VAR changed: BOOLEAN; temp, count, i: INTEGER;
BEGIN
count := HIGH(a); REPEAT changed := FALSE; DEC(count); FOR i := 0 TO count DO IF a[i] > a[i+1] THEN temp := a[i]; a[i] := a[i+1]; a[i+1] := temp; changed := TRUE END END UNTIL NOT changed
END BubbleSort;</lang>
Modula-3
<lang modula3>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; sorted := FALSE; END; END; END; END Sort;
END Bubble.</lang>
Nemerle
Functional
<lang Nemerle>using System; using System.Console;
module Bubblesort {
Bubblesort[T] (x : list[T]) : list[T] where T : IComparable { def isSorted(y) { |[_] => true |y1::y2::ys => (y1.CompareTo(y2) < 0) && isSorted(y2::ys) } def sort(y) { |[y] => [y] |y1::y2::ys => if (y1.CompareTo(y2) < 0) y1::sort(y2::ys) else y2::sort(y1::ys) } def loop(y) { if (isSorted(y)) y else {def z = sort(y); loop(z)} } match(x) { |[] => [] |_ => loop(x) } } Main() : void { def empty = []; def single = [2]; def several = [2, 6, 1, 7, 3, 9, 4]; WriteLine(Bubblesort(empty)); WriteLine(Bubblesort(single)); WriteLine(Bubblesort(several)); }
}</lang>
Imperative
We use an array for this version so that we can update in place. We could use a C# style list (as in the C# example), but that seemed too easy to confuse with a Nemerle style list. <lang Nemerle>using System; using System.Console;
module Bubblesort {
public static Bubblesort[T](this x : array[T]) : void where T : IComparable { mutable changed = false; def ln = x.Length; do { changed = false; foreach (i in [0 .. (ln - 2)]) { when (x[i].CompareTo(x[i + 1]) > 0) { x[i] <-> x[i + 1]; changed = true; } } } while (changed); } Main() : void { def several = array[2, 6, 1, 7, 3, 9, 4]; several.Bubblesort(); foreach (i in several) Write($"$i "); }
}</lang>
Objeck
<lang objeck> function : Swap(p : Int[]) ~ Nil {
t := p[0]; p[0] := p[1]; p[1] := t;
}
function : Sort(a : Int[]) ~ Nil {
do { sorted := true; size -= 1; for (i:=0; i<a->Size(); i+=1;) { if (a[i+1] < a[i]) { swap(a+i); sorted := 0; }; }; } while (sorted = false);
} </lang>
OCaml
Like the Haskell versions above:
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>
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. <lang ocaml>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</lang>
Octave
<lang 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</lang>
<lang octave>v = [9,8,7,3,1,100]; disp(bubblesort(v));</lang>
Oz
In-place sorting of mutable arrays: <lang oz>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}</lang>
Purely-functional sorting of immutable lists: <lang oz>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]}}</lang>
PARI/GP
<lang parigp>bubbleSort(v)={
for(i=1,#v-1, for(j=i+1,#v, if(v[j]<v[i], my(t=v[j]); v[j]=v[i]; v[i]=t ) ) ); v
};</lang>
Pascal
<lang pascal>procedure bubble_sort(n: integer; var list: array of real); var
i, j: integer; t: real;
begin
for i := n downto 2 do begin for j := 0 to i - 1 do begin if list[j] < list[j + 1] then begin continue end;
t := list[j]; list[j] := list[j + 1]; list[j + 1] := t; end; end;
end;</lang>
Usage:<lang pascal> var
list: array[0 .. 9] of real;
// ... bubble_sort(9, list); </lang>
Perl
<lang 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]; } }
}</lang>
Usage:
<lang perl>my @a = (39, 25, 30, 28, 36, 72, 98, 25, 43, 38); bubble_sort(@a);</lang>
Perl 6
<lang perl6>sub bubble_sort (@a is rw) {
for ^@a -> $i { for $i ^..^ @a -> $j { @a[$j] < @a[$i] and @a[$i, $j] = @a[$j, $i]; } }
}</lang>
PHP
<lang php>function bubbleSort( array &$array ) { do { $swapped = false; for( $i = 0, $c = count( $array ) - 1; $i < $c; $i++ ) { if( $array[$i] > $array[$i + 1] ) { list( $array[$i + 1], $array[$i] ) = array( $array[$i], $array[$i + 1] ); $swapped = true; } } } while( $swapped ); }</lang>
PL/I
<lang 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; </lang>
PicoLisp
<lang PicoLisp>(de bubbleSort (Lst)
(use Chg (loop (off Chg) (for (L Lst (cdr L) (cdr L)) (when (> (car L) (cadr L)) (xchg L (cdr L)) (on Chg) ) ) (NIL Chg Lst) ) ) )</lang>
Pop11
<lang 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 =></lang>
PostScript
<lang PostScript> /bubblesort{ /x exch def /temp x x length 1 sub get def /i x length 1 sub def /j i 1 sub def
x length 1 sub{ i 1 sub{ x j 1 sub get x j get lt { /temp x j 1 sub get def x j 1 sub x j get put x j temp put }if /j j 1 sub def }repeat /i i 1 sub def /j i 1 sub def }repeat x pstack }def </lang>
PowerShell
<lang 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 } } }
}</lang>
PureBasic
<lang 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</lang>
Python
<lang 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</lang>
R
<lang 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))</lang>
REXX
<lang rexx> /*REXX program sorts an array using the bubble-sort method. */
call gen@ /*generate array elements. */ call show@ 'before sort' /*show before array elements*/ call bubbleSort highItem /*invoke the bubble sort. */ call show@ ' after sort' /*show after array elements*/ exit
/*─────────────────────────────────────BUBBLESORT subroutine───────*/
bubbleSort: procedure expose @.; parse arg n /*n=number of items.*/
/*diminish #items each time.*/ do until done /*sort until it's done. */ done=1 /*assume it's done (1=true).*/
do j=1 for n-1 /*sort M items this time. */ k=j+1 /*point to next item. */ if @.j>@.k then do /*out of order ? */ _=@.j /*assign to a temp variable.*/ @.j=@.k /*swap current with next. */ @.k=_ /*... and next with _ */ done=0 /*indicate it's not done. */ end /* 1=true 0=false */ end
end
return
/*─────────────────────────────────────GEN@ subroutine─────────────*/
gen@: @.= /*assign default value. */
@.1 ='---letters of the Hebrew alphabet---' @.2 ='====================================' @.3 ='aleph [alef]' @.4 ='beth [bet]' @.5 ='gimel' @.6 ='daleth [dalet]' @.7 ='he' @.8 ='waw [vav]' @.9 ='zayin' @.10='heth [het]' @.11='teth [tet]' @.12='yod' @.13='kaph [kaf]' @.14='lamed' @.15='mem' @.16='nun' @.17='samekh' @.18='ayin' @.19='pe' @.20='sadhe [tsadi]' @.21='qoph [qof]' @.22='resh' @.23='shin' @.24='taw [tav]'
do highItem=1 while @.highItem\== /*find how many entries. */ end
highItem=highItem-1 /*adjust highItem slightly. */ return
/*─────────────────────────────────────SHOW@ subroutine────────────*/
show@: widthH=length(highItem) /*maximum width of any line.*/
do j=1 for highItem say 'element' right(j,widthH) arg(1)':' @.j end
say copies('─',80) /*show a seperator line. */ return </lang> Output:
element 1 before sort: ---letters of the Hebrew alphabet--- element 2 before sort: ==================================== element 3 before sort: aleph [alef] element 4 before sort: beth [bet] element 5 before sort: gimel element 6 before sort: daleth [dalet] element 7 before sort: he element 8 before sort: waw [vav] element 9 before sort: zayin element 10 before sort: heth [het] element 11 before sort: teth [tet] element 12 before sort: yod element 13 before sort: kaph [kaf] element 14 before sort: lamed element 15 before sort: mem element 16 before sort: nun element 17 before sort: samekh element 18 before sort: ayin element 19 before sort: pe element 20 before sort: sadhe [tsadi] element 21 before sort: qoph [qof] element 22 before sort: resh element 23 before sort: shin element 24 before sort: taw [tav] ──────────────────────────────────────────────────────────────────────────────── element 1 after sort: ---letters of the Hebrew alphabet--- element 2 after sort: ==================================== element 3 after sort: aleph [alef] element 4 after sort: ayin element 5 after sort: beth [bet] element 6 after sort: daleth [dalet] element 7 after sort: gimel element 8 after sort: he element 9 after sort: heth [het] element 10 after sort: kaph [kaf] element 11 after sort: lamed element 12 after sort: mem element 13 after sort: nun element 14 after sort: pe element 15 after sort: qoph [qof] element 16 after sort: resh element 17 after sort: sadhe [tsadi] element 18 after sort: samekh element 19 after sort: shin element 20 after sort: taw [tav] element 21 after sort: teth [tet] element 22 after sort: waw [vav] element 23 after sort: yod element 24 after sort: zayin ────────────────────────────────────────────────────────────────────────────────
Ruby
This example adds the bubblesort! method to the Array object. Below are two different methods that show four different iterating constructs in ruby.
<lang 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| self[i-1], self[i] = self[i], self[i-1] if self[i-1] < self[i] end end self end
end ary = [3, 78, 4, 23, 6, 8, 6] ary.bubblesort1! p ary
- => [3, 4, 6, 6, 8, 23, 78]</lang>
Sather
<lang sather>class SORT{T < $IS_LT{T}} is
private swap(inout a, inout b:T) is temp ::= a; a := b; b := temp; end; bubble_sort(inout a:ARRAY{T}) is i:INT; if a.size < 2 then return; end; loop sorted ::= true; loop i := 0.upto!(a.size - 2); if a[i+1] < a[i] then swap(inout a[i+1], inout a[i]); sorted := false; end; end; until!(sorted); end; end;
end;</lang>
<lang sather>class MAIN is
main is a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4|; SORT{INT}::bubble_sort(inout a); #OUT + a + "\n"; end;
end;</lang>
This should be able to sort (in ascending order) any object for which is_lt
(less than) is defined.
Scala
This slightly more complex version of Bubble Sort avoids errors with indices.
<lang scala>def bubbleSort[T](arr: Array[T])(implicit o: Ordering[T]) {
import o._ val consecutiveIndices = (arr.indices, arr.indices drop 1).zipped var hasChanged = true do { hasChanged = false consecutiveIndices foreach { (i1, i2) => if (arr(i1) > arr(i2)) { hasChanged = true val tmp = arr(i1) arr(i1) = arr(i2) arr(i2) = tmp } } } while(hasChanged)
}</lang>
Scheme
<lang 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)))</lang>
This solution iteratively finds the fixed point of sort-step. A comparison function must be passed to bubblesort. Example usages: <lang scheme>(bubble-sort (list 1 3 5 9 8 6 4 2) >) (bubble-sort (string->list "Monkey") char<?)</lang>
Here is a recursive bubble sort which sorts list 'l' using the comparator 'f':
<lang scheme>(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)))))</lang> For example, you could do <lang scheme>(bsort > '(3 2 1)) (1 2 3)</lang>
Seed7
<lang 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;</lang>
Original source: [2]
Smalltalk
A straight translation from the pseudocode above. Swap is done with a block closure.
<lang smalltalk>|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.</lang>
SNOBOL4
<lang SNOBOL4>* # Sort array in place, return array
define('bubble(a,alen)i,j,ub,tmp') :(bubble_end)
bubble i = 1; ub = alen outer gt(ub,1) :f(bdone)
j = 1
inner le(a<j>, a<j + 1>) :s(incrj)
tmp = a<j> a<j> = a<j + 1> a<j + 1> = tmp
incrj j = lt(j + 1,ub) j + 1 :s(inner)
ub = ub - 1 :(outer)
bdone bubble = a :(return) bubble_end
- # Fill array with test data
str = '33 99 15 54 1 20 88 47 68 72' output = str; arr = array(10)
floop i = i + 1; str span('0123456789') . arr = :s(floop)
- # Test and display
bubble(arr,10); str =
sloop j = j + 1; str = str arr<j> ' ' :s(sloop)
output = trim(str)
end</lang>
Output:
33 99 15 54 1 20 88 47 68 72 1 15 20 33 47 54 68 72 88 99
SPARK
The first version is based on the Ada version, with Integer for both the array index and the array element.
Static analysis of this code shows that it is guaranteed free of any run-time error when called from any other SPARK code. <lang Ada>package Bubble is
type Arr is array(Integer range <>) of Integer;
procedure Sort (A : in out Arr); --# derives A from *;
end Bubble;
package body Bubble
is
procedure Sort (A : in out Arr) is Finished : Boolean; Temp : Integer; begin if A'Last /= A'First then loop Finished := True; for J in Integer range A'First .. A'Last - 1 loop if A (J + 1) < A (J) then Finished := False; Temp := A (J + 1); A (J + 1) := A (J); A (J) := Temp; end if; end loop; --# assert A'Last /= A'First; exit when Finished; end loop; end if; end Sort;
end Bubble; </lang> The next version has a postcondition to guarantee that the returned array is sorted correctly. This requires the two proof rules that follow the source. The Ada code is identical with the first version. <lang Ada>package Bubble is
type Arr is array(Integer range <>) of Integer;
-- Sorted is a proof function with the definition: -- Sorted(A, From_I, To_I) -- <-> -- (for all I in Integer range From_I .. To_I - 1 => -- (A(I) <= A(I + 1))) . -- --# function Sorted (A : Arr; --# From_I, To_I : Integer) return Boolean; procedure Sort (A : in out Arr); --# derives A from *; --# post Sorted(A, A'First, A'Last);
end Bubble;
package body Bubble
is
procedure Sort (A : in out Arr) is Finished : Boolean; Temp : Integer; begin if A'Last > A'First then loop Finished := True; for J in Integer range A'First .. A'Last - 1 --# assert Finished -> Sorted(A, A'First, J); loop if A (J + 1) < A (J) then Finished := False; Temp := A (J + 1); A (J + 1) := A (J); A (J) := Temp; end if; end loop; --# assert A'Last /= A'First --# and (Finished -> Sorted(A, A'First, A'Last)); exit when Finished; end loop; end if; end Sort;
end Bubble; </lang> The proof rules are stated here without justification (but they are fairly obvious). A formal proof of these rules from the definition of Sorted has been completed.
bubble_sort_rule(1): sorted(A, I, J) may_be_deduced_from [ J <= I ] . bubble_sort_rule(2): Fin -> sorted(A, I, J + 1) may_be_deduced_from [ Fin -> sorted(A, I, J), element(A, [J]) <= element(A, [J + 1]) ] .
Both of the two versions above use an inner loop that scans over all the array on every pass of the outer loop. This makes the proof in the second version very simple.
The final version scans over a reducing portion of the array in the inner loop, consequently the proof becomes more complex. The package specification for this version is the same as the second version above. The package body defines two more proof functions. <lang Ada>package body Bubble is
procedure Sort (A : in out Arr) is Finished : Boolean;
-- In_Position is a proof function with the definition: -- In_Position(A, A_Start, A_I, A_End) -- <-> -- ((for all K in Integer range A_Start .. A_I - 1 => -- (A(K) <= A(A_I))) -- and -- Sorted(A, A_I, A_End) . -- --# function In_Position (A : Arr; --# A_Start, A_I, A_End : Integer) return Boolean;
-- Swapped is a proof function with the definition: -- Swapped(A_In, A_Out, I1, I2) -- <-> -- (A_Out = A_In[I1 => A_In(I2); I2 => A_In(I1)]). -- --# function Swapped (A_In, A_Out : Arr; --# I1, I2 : Integer) return Boolean;
procedure Swap (A : in out Arr; I1 : in Integer; I2 : in Integer) --# derives A from *, I1, I2; --# pre I1 in A'First .. A'Last --# and I2 in A'First .. A'Last; --# post Swapped(A~, A, I1, I2); is Temp : Integer; begin Temp := A(I2); A(I2) := A(I1); A(I1) := Temp; end Swap; pragma Inline (Swap);
begin if A'Last > A'First then for I in reverse Integer range A'First + 1 .. A'Last loop Finished := True; for J in Integer range A'First .. I - 1 loop if A (J + 1) < A (J) then Finished := False; Swap (A, J, J + 1); end if; --# assert I% = I -- I is unchanged by execution of the loop --# and (for all K in Integer range A'First .. J => --# (A(K) <= A(J + 1))) --# and (I < A'Last -> In_Position(A, A'First, I + 1, A'Last)) --# and (Finished -> Sorted(A, A'First, J + 1)); end loop; exit when Finished; --# assert In_Position(A, A'First, I, A'Last); end loop; end if; end Sort;
end Bubble; </lang> Completion of the proof of this version requires more rules than the previous version and they are rather more complex. Creation of these rules is quite straightforward - I tend to write whatever rules the Simplifier needs first and then validate them afterwards. A formal proof of these rules from the definition of Sorted, In_Position and Swapped has been completed.
bubble_sort_rule(1): sorted(A, I, J) may_be_deduced_from [ J <= I ] . bubble_sort_rule(2): sorted(A, I - 1, J) may_be_deduced_from [ sorted(A, I, J), element(A, [I - 1]) <= element(A, [I]) ] . bubble_sort_rule(3): Fin -> sorted(A, I, J + 1) may_be_deduced_from [ Fin -> sorted(A, I, J), element(A, [J]) <= element(A, [J + 1]) ] . bubble_sort_rule(4): sorted(A, Fst, Lst) may_be_deduced_from [ sorted(A, Fst, I), I < Lst -> in_position(A, Fst, I + 1, Lst), I <= Lst ] . bubble_sort_rule(5): in_position(A, Fst, I, Lst) may_be_deduced_from [ I < Lst -> in_position(A, Fst, I + 1, Lst), for_all(K : integer, Fst <= K and K <= I - 1 -> element(A, [K]) <= element(A, [I])), I >= Fst, I <= Lst ] . bubble_sort_rule(6): I < Lst -> in_position(A2, Fst, I + 1, Lst) may_be_deduced_from [ I < Lst -> in_position(A1, Fst, I + 1, Lst), swapped(A1, A2, J + 1, J + 2), J + 2 < I + 1, J >= Fst ] . bubble_sort_rule(7): I - 1 < Lst -> in_position(A2, Fst, I, Lst) may_be_deduced_from [ in_position(A1, Fst, I, Lst), swapped(A1, A2, J, J + 1), J + 1 < I, J >= Fst ] . bubble_sort_rule(8): for_all(K : integer, I <= K and K <= I -> element(A, [K]) <= element(A, [I + 1])) may_be_deduced_from [ element(A, [I]) <= element(A, [I + 1]) ] . bubble_sort_rule(9): for_all(K : integer, I <= K and K <= I -> element(A2, [K]) <= element(A2, [I + 1])) may_be_deduced_from [ element(A1, [I]) > element(A1, [I + 1]), swapped(A1, A2, I, I + 1) ] . bubble_sort_rule(10): for_all(K2 : integer, Fst <= K2 and K2 <= J + 1 -> element(A, [K2]) <= element(A, [J + 2])) may_be_deduced_from [ for_all(K1 : integer, Fst <= K1 and K1 <= J -> element(A, [K1]) <= element(A, [J + 1])), element(A, [J + 1]) <= element(A, [J + 2]) ] . bubble_sort_rule(11): for_all(K2 : integer, Fst <= K2 and K2 <= J + 1 -> element(A2, [K2]) <= element(A2, [J + 2])) may_be_deduced_from [ for_all(K1 : integer, Fst <= K1 and K1 <= J -> element(A1, [K1]) <= element(A1, [J + 1])), element(A1, [J + 1]) > element(A1, [J + 2]), swapped(A1, A2, J + 1, J + 2) ] .
TI-83 BASIC
Input your data into L1 and run this program to organize it.
:L1→L2 :1+dim(L2 :For(D,1,dim(L2) :N-1→N :0→I :For(C,1,dim(L2-2) :For(A,dim(L2)-N+1,dim(L2)-1) :If L2(A)>L2(A_1) :Then :1→I :L2(A)→B :L2(A+1)→L2(A) :B→L2(A+1) :End :End :End :If I=0 :Goto C :End :Lbl C :If L2(1)>L2(2) :Then :L2(1)→B :L2(2)→L2(1) :B→L2(2) :End :DelVar A :DelVar B :DelVar C :DelVar D :DelVar N :DelVar I :Return
Odd-Even Bubble Sort (same IO):
:"ODD-EVEN" :L1→L2( :1+dim(L2)→N :For(D,1,dim(L2)) :N-1→N :0→O :For(C,1,dim(L2)-2) :For(A,dim(L2)-N+2,dim(L2)-1,2) :If L2(A)>L2(A+1) :Then :1→O :L2(A)→B :L2(A+1)→L2(A) :B→L2(A+1) :End :End :For(A,dim(L2)-N+1,dim(L2)-1,2) :If L2(A)>L2(A+1) :Then :1→O :L2(A)→B :L2(A+1)→L2(A) :B→L2(A+1) :End :End :End :If O=0 :Goto C :End :Lbl C :If L2(1)>L2(2) :Then :L2(1)→B :L2(2)→L2(1) :B→L2(2) :End :DelVar A :DelVar B :DelVar C :DelVar D :DelVar N :DelVar O :Return
Tcl
<lang tcl>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</lang>
Idiomatic code uses the builtin lsort
instead, which is a stable O(n log n) sort.
Toka
Toka does not have a bubble sort predefined, but it is easy to code a simple one:
<lang toka>#! 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</lang>
Unicon
See Icon.
UnixPipes
<lang bash>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</lang>
Ursala
The bubblesort function is parameterized by a relational predicate. <lang Ursala>#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></lang> output:
<140,212,247,270,315,362,449,532,567,677>
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.
Implementation
<lang vb> 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 </lang>
Invocation
<lang vb> dim a a = array( "great eastern", "roe", "stirling", "albany", "leach") wscript.echo join(a,", ") bubbleSort a wscript.echo join(a,", ") </lang>
Output
great eastern, roe, stirling, albany, leach albany, great eastern, leach, roe, stirling
Visual Basic .NET
Platform: .NET
<lang vbnet>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</lang>
Yorick
<lang yorick>func bubblesort(&items) {
itemCount = numberof(items); do { hasChanged = 0; itemCount--; for(index = 1; index <= itemCount; index++) { if(items(index) > items(index+1)) { items([index,index+1]) = items([index+1,index]); hasChanged = 1; } } } while(hasChanged);
}</lang>
- Programming Tasks
- Sorting Algorithms
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- BBC BASIC
- C
- C++
- C sharp
- Clean
- Clojure
- COBOL
- Common Lisp
- D
- Delphi
- E
- Eiffel
- Euphoria
- Factor
- Forth
- Fortran
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- J
- Java
- JavaScript
- Io
- Liberty BASIC
- Lisaac
- Lua
- Lucid
- M4
- Mathematica
- MATLAB
- MAXScript
- MMIX
- Modula-2
- Modula-3
- Nemerle
- Objeck
- OCaml
- Octave
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PL/I
- PicoLisp
- Pop11
- PostScript
- PowerShell
- PureBasic
- Python
- R
- REXX
- Ruby
- Sather
- Scala
- Scheme
- Seed7
- Smalltalk
- SNOBOL4
- SPARK
- TI-83 BASIC
- Tcl
- Tcllib
- Toka
- UnixPipes
- Ursala
- VBScript
- Visual Basic .NET
- Yorick
- GUISS/Omit