Sorting algorithms/Bubble sort: Difference between revisions

 

A   '''bubble'''   sort is also known as a   '''sinking'''   sort.

 

Because of its simplicity and ease of visualization, it is often taught in introductory computer science courses.

{{trans|Python}}

 

V changed = 1B

L changed == 1B

assert(testcase != testset)

bubble_sort(&testcase)

 

=={{header|360 Assembly}}==

For maximum compatibility, this program uses only the basic instruction set.

The program uses also HLASM structured macros (DO,ENDDO,IF,ELSE,ENDIF) for readability and two ASSIST/360 macros (XDECO,XPRNT) to keep the code as short as possible.

BUBBLE CSECT

USING BUBBLE,R13,R12 establish base registers

RN EQU 7 n-1

RM EQU 8 more

{{out}}

<pre>

=={{header|6502 Assembly}}==

Code can be copied and pasted into Easy6502. Make sure you set the monitor to $1200 and check the check box to view it in action. Bubble Sort's infamous reputation is very well-deserved as this is going to take a few minutes to finish. This example takes a reverse identity table (where the 0th entry is $FF, the first is $FE, and so on) and sorts them in ascending order. Slowly. And the program might not run unless its tab is active in your browser. I'd play Game Boy to pass the time. ;)

define z_L $00

define z_H $01

jmp BUBBLESORT

DoneSorting:

{{out}}

<pre>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program bubbleSort64.s */

.include "../includeARM64.inc"

 

=={{header|ACL2}}==

(if (endp (rest xs))

(mv nil xs)

 

(defun bsort (xs)

 

=={{header|Action!}}==

INT i

 

Test(c,8)

Test(d,12)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Bubble_sort.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

{

var changed:Boolean = false;

return toSort;

 

=={{header|Ada}}==

{{works with|GCC|4.1.2}}

 

type Element is private;

with function "=" (E1, E2 : Element) return Boolean is <>;

end loop;

New_Line;

 

=={{header|ALGOL 60}}==

{{works with|A60}}

comment Sorting algorithms/Bubble sort - Algol 60;

integer nA;

writetable(1,nA)

end

{{out}}

<pre>

 

=={{header|ALGOL 68}}==

PROC swap = (REF[]DATA slice)VOID:

(

sort(random);

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

{{out}}

<pre>

 

=={{header|ALGOL W}}==

% As algol W does not allow overloading, we have to have type-specific %

% sorting procedures - this bubble sorts an integer array %

writeData;

end test

{{out}}

<pre>

In AppleScript, the time taken to set and check a "has changed" boolean repeatedly over the greater part of the sort generally matches or exceeds any time it may save. A more effective optimisation, since the greater value in any pair also takes part in the following comparison, is to keep the greater value in a variable and only fetch one value from the list for the next comparison.

 

on bubbleSort(theList, l, r) -- Sort items l thru r of theList.

set listLen to (count theList)

set aList to {61, 23, 11, 55, 1, 94, 71, 98, 70, 33, 29, 77, 58, 95, 2, 52, 68, 29, 27, 37, 74, 38, 45, 73, 10}

sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.

 

{{output}}

 

=={{header|Arendelle}}==

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

 

/* ARM assembly Raspberry PI */

/***************************************************/

.include "../affichage.inc"

=={{header|Arturo}}==

 

len: size items

loop len [j][

]

 

 

{{out}}

 

=={{header|AutoHotkey}}==

(

dog

sorted .= array%A_Index% . "`n"

Return sorted

 

=={{header|AWK}}==

Sort the standard input and print it to standard output.

line[NR] = $0

}

print line[i]

}

 

GNU awk contains built in functions for sorting, but POSIX

variables.

 

# Test this example file from command line with:

#

exit

}

 

=={{header|bash}}==

I hope to see vastly improved versions of bubble_sort.

 

$ function bubble_sort() {

local a=("$@")

-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782

$

 

=={{header|BASIC}}==

==={{header|Applesoft BASIC}}===

1 FOR HC = -1 TO 0

2 LET IC = IC - 1

7 DIM I%(18000) : I%(0) = 50

8 FOR I = 1 TO I%(0) : I%(I) = INT (RND(1) * 65535) - 32767 : NEXT

 

{{out}}

 

==={{header|BASIC256}}===

{{works with|BASIC256 }}

Dim a(11): ordered=false

print "Original set"

print a[n]+", ";

next n

{{out}}(example)

<pre>

==={{header|BBC BASIC}}===

The Bubble sort is very inefficient for 99% of cases. This routine uses a couple of 'tricks' to try and mitigate the inefficiency to a limited extent. Note that the array index is assumed to start at zero.

test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCbubblesort(test(), 10)

n% = l%

UNTIL l% = 0

{{out}}

<pre>

</pre>

 

 

==={{header|Commodore BASIC}}===

5 REM ===============================================

10 REM HTTP://ROSETTACODE.ORG/

910 DATA 15

920 DATA 64,34,25,12,22,11,90,13,59,47,19,89,10,17,31

 

==={{header|GW-BASIC}}===

20 DIM ARR(20)

30 RANDOMIZE TIMER

1020 ARR(I+1) = TEMP

1030 CHANGED = 1

{{out}}<pre>

20 59 42 9 5 91 6 64 21 28 65 96 20 66 66 70 91 98 63 31

 

==={{header|IS-BASIC}}===

110 RANDOMIZE

120 NUMERIC ARRAY(-5 TO 9)

330 NEXT

340 LOOP WHILE CH

 

{{out}}

NEXT

{{out}}

 

=={{header|BCPL}}==

 

let bubblesort(v, length) be

for i=0 to 9 do writef("%N ", v!i)

wrch('*N')

{{out}}

<pre>1 2 3 4 5 6 7 8 9 10</pre>

 

=={{header|C}}==

 

void bubble_sort (int *a, int n) {

return 0;

}

{{out}}

<pre>

=={{header|C sharp|C#}}==

{{works with|C sharp|C#|3.0+}}

using System.Collections.Generic;

 

}

}

 

=={{header|C++}}==

Uses C++11. Compile with

g++ -std=c++11 bubble.cpp

#include <iostream>

#include <iterator>

copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

{{out}}

<pre>

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.

(:import java.util.ArrayList))

arr)))

 

 

Purely functional version working on Clojure sequences:

"was-changed: whether any elements prior to the current first element

were swapped;

(recur less? result)))))

 

=={{header|CLU}}==

bubble_sort = proc [T: type] (a: array[T])

where T has lt: proctype (T,T) returns (bool)

bubble_sort[int](test)

stream$puts(po, "After: ") print_arr[int](test, 3, po)

{{out}}

<pre>Before: 7 -5 0 2 99 16 4 20 47 19

Only for lists of integers.

 

function(bubble_sort var)

math(EXPR last "${ARGC} - 1") # Prepare to sort ARGV[1]..ARGV[last].

endforeach(index)

set("${var}" "${answer}" PARENT_SCOPE)

 

 

<pre>-- 11;22;33;44;55;66</pre>

This is a complete program that demonstrates the bubble sort algorithm in COBOL.

<br/>This version is for COBOL-74 which does not have in-line performs, nor END-IF and related constructs.

IDENTIFICATION DIVISION.

PROGRAM-ID. BUBBLESORT.

F-999.

EXIT.

 

A more modern version of COBOL.

identification division.

program-id. BUBBLSRT.

end-perform

.

 

{{out}}

=={{header|Common Lisp}}==

Bubble sort an sequence in-place, using the < operator for comparison if no comaprison function is provided

"sort a sequence (array or list) with an optional comparison function (cl:< is the default)"

(loop with sorted = nil until sorted do

(rotatef (elt sequence a)

(elt sequence (1+ a)))

 

 

<code>elt</code> 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 <code>cons</code> cell.

 

(do ((swapped t)) ((not swapped) vector)

(setf swapped nil)

(etypecase sequence

(list (bubble-sort-list sequence predicate))

 

=={{header|Cowgol}}==

 

 

# Comparator interface, on the model of C, i.e:

i := i + 1;

end loop;

 

{{out}}

 

=={{header|D}}==

 

T[] bubbleSort(T)(T[] data) pure nothrow

auto array = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4];

writeln(array.bubbleSort());

{{out}}

<pre>[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]</pre>

 

Static array is an arbitrary-based array of fixed length

 

{$APPTYPE CONSOLE}

Writeln;

Readln;

{{out}}

<pre>

0 3 5 7 8 16 20 27 29 31 37 42 47 67 84 86

</pre>

 

=={{header|Dyalect}}==

 

var done = false

while !done {

done = true

if list[i - 1] > list[i] {

var x = list[i]

}

}

var xs = [3,1,5,4,2,6]

bubbleSort(xs)

 

{{out}}

 

=={{header|E}}==

__loop(fn {

var changed := false

changed

})

 

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

 

=={{header|EchoLisp}}==

;; sorts a vector of objects in place

;; proc is an user defined comparison procedure

(bubble-sort V sort/length)

→ #(zen simon elvis albert antoinette)

 

=={{header|EDSAC order code}}==

 

To clarify the EDSAC program, an equivalent Pascal program is added as a comment.

[Bubble sort demo for Rosetta Code website]

[EDSAC program. Initial Orders 2]

E 14 Z [define entry point]

P F [acc = 0 on entry]

{{out}}

<pre>

This solution is presented in two classes. The first is a simple application that creates a set, an instance of <code lang="eiffel">MY_SORTED_SET</code>, 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.

 

APPLICATION

create

my_set: MY_SORTED_SET [INTEGER]

-- Set to be sorted

 

The second class is <code lang="eiffel">MY_SORTED_SET</code>.

 

MY_SORTED_SET [G -> COMPARABLE]

inherit

end

end

 

This class inherits from the Eiffel library class <code lang="eiffel">TWO_WAY_SORTED_SET</code>, which implements sets whose elements are comparable. Therefore, the set can be ordered and in fact is kept so under normal circumstances.

=={{header|Elena}}==

{{trans|C#}}

import extensions;

madeChanges := false;

itemCount -= 1;

{

if (list[i] > list[i + 1])

var list := new int[]{3, 7, 3, 2, 1, -4, 10, 12, 4};

console.printLine(list.bubbleSort().asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def bsort(list) when is_list(list) do

t = bsort_iter(list)

def bsort_iter([x, y | t]), do: [x | bsort_iter([y | t])]

def bsort_iter(list), do: list

 

=={{header|Erlang}}==

sort/3 copied from Stackoverflow.

-module( bubble_sort ).

 

sort( [X, Y | T], Acc, _Done ) when X > Y -> sort( [X | T], [Y | Acc], false );

sort( [X | T], Acc, Done ) -> sort( T, [X | Acc], Done ).

{{out}}

<pre>

 

=={{header|ERRE}}==

PROGRAM BUBBLE_SORT

 

PRINT

END PROGRAM

 

=={{header|Euphoria}}==

object tmp

integer changed

pretty_print(1,s,{2})

puts(1,"\nAfter: ")

 

{{out}}

 

=={{header|Ezhil}}==

 

## இந்த நிரல் ஒரு பட்டியலில் உள்ள எண்களை Bubble Sort என்ற முறைப்படி ஏறுவரிசையிலும் பின்னர் அதையே இறங்குவரிசையிலும் அடுக்கித் தரும்

பதிப்பி எண்கள்பிரதி

 

 

=={{header|F Sharp|F#}}==

let rec sort accum rev lst =

match lst, rev with

| head::tail, _ -> sort (head::accum) rev tail

sort [] true lst

 

=={{header|Factor}}==

sequences.private ;

IN: rosetta.bubble

 

: natural-sort! ( seq -- )

 

It is possible to pass your own comparison operator to <code>sort!</code>, so you can f.e. sort your sequence backwards with passing <code>[ >=< ]</code> into it.

 

[ "Before: " write . ]

[ "Natural: " write [ natural-sort! ] keep . ]

 

Before: { 3707 5045 4661 1489 3140 7195 8844 6506 6322 3199 }

This is not a complete implementation of bubblesort: it doesn't keep a boolean flag whether to stop, so it goes on printing each stage of the sorting process ad infinitum.

 

with bubblesort.

v <

>~{ao ^

>~}l &{ v

 

=={{header|Forth}}==

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

 

' > is bubble-test

 

i 2@ bubble-test if i 2@ swap i 2! then

cell +loop

 

This is the same algorithm done without the local variables:

 

dup 1 do

2dup i - cells bounds do

i 2@ bubble-test if i 2@ swap i 2! then

cell +loop

 

Version with ''O(n)'' best case:

begin

1- 2dup true -rot ( sorted addr len-1 )

then

cell +loop ( sorted )

 

Test any version with this:

 

=={{header|Fortran}}==

REAL, INTENT(in out), DIMENSION(:) :: a

REAL :: temp

IF (.NOT. swapped) EXIT

END DO

 

=={{header|g-fu}}==

(fun bubbles (vs)

(let done? F n (len vs))

---

(1 2 3)

 

 

 

 

 

<pre>

 

 

=={{header|Go}}==

Per task pseudocode:

 

import "fmt"

}

}

 

More generic version that can sort anything that implements <code>sort.Interface</code>:

 

import (

}

}

 

=={{header|Groovy}}==

Solution:

 

def checkSwap = { a, i, j = i+1 -> [(a[i] > a[j])].find { it }.each { makeSwap(a, i, j) } }

while (swapped) { swapped = (1..<list.size()).any { checkSwap(list, it-1) } }

list

 

Test Program:

 

{{out}}

=={{header|Haskell}}==

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

bsort s = case _bsort s of

t | t == s -> t

where _bsort (x:x2:xs) | x > x2 = x2:(_bsort (x:xs))

| otherwise = x:(_bsort (x2:xs))

 

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

 

import Control.Monad

 

then Just $ x2 : fromMaybe (x:xs) (_bsort $ x:xs)

else liftM (x:) $ _bsort (x2:xs)

 

This version is based on the above, but avoids sorting the whole list each time. To implement this without a counter and retain using pattern matching, inner sorting is reversed, and then the result is reversed back. Sorting is based on a predicate, e.g., (<) or (>).

 

import Control.Monad

 

 

bsort :: Ord a => [a] -> [a]

 

=={{header|Haxe}}==

@:generic

public static function sort<T>(arr:Array<T>) {

Sys.println('Sorted Strings: ' + stringArray);

}

 

{{out}}

 

=={{header|HicEst}}==

REAL :: a(1)

IF (swapped == 0) RETURN

ENDDO

 

=={{header|Icon}} and {{header|Unicon}}==

Icon/Unicon implementation of a bubble sort

demosort(bubblesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

X[i-1] :=: X[swapped := i]

return X

 

{{out}}

* 'demosort' can apply different sorting procedures and operators to lists and strings to show how this works. The routines 'displaysort' and 'writex' are helpers.

 

 

procedure sortop(op,X) #: select how to sort

write()

return

 

=={{header|Io}}==

List do(

bubblesort := method(

)

)

 

=={{header|J}}==

{{eff note|J|/:~ list}}

 

Test program:

 

4 6 8 6 5 8 6 6 6 9

bubbleSort ?. 10 $ 10

 

For the most part, bubble sort works against J's strengths. However, once a single pass has been implemented as a list operation, <code>^:_</code> tells J to repeat this until the result stops changing.

 

=={{header|Janet}}==

(defn bubble-sort!

[arr]

 

)

 

=={{header|Java}}==

Bubble sorting (ascending) an array of any <tt>Comparable</tt> type:

boolean changed = false;

do {

}

} while (changed);

 

For descending, simply switch the direction of comparison:

//same swap code as before

 

=={{header|JavaScript}}==

var done = false;

while (!done) {

}

return this;

 

{{works with|SEE|3.0}}

{{works with|OSSP js|1.6.20070208}}

var done = false;

while (! done) {

}

return this;

 

Example:

my_arr.bubblesort();

 

{{out}}

 

webpage version (for the rest of us):

Array.prototype.bubblesort = function() {

var done = false;

}

document.write(output);

 

=={{header|jq}}==

def swap(i;j): .[i] as $x | .[i]=.[j] | .[j]=$x;

 

else .

end )

'''Example''':

[3,2,1],

[1,2,3],

["G", "F", "C", "A", "B", "E", "D"]

{{Out}}

[1,2,3]

[1,2,3]

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

for _ in 2:length(arr), j in 1:length(arr)-1

if arr[j] > arr[j+1]

 

v = rand(-10:10, 10)

 

{{out}}

{{trans|Java}}

 

 

fun <T> bubbleSort(a: Array<T>, c: Comparator<T>) {

}

} while (changed)

 

=={{header|Lambdatalk}}==

{def bubblesort

{def bubblesort.swap!

{bubblesort {A.new 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]

 

=={{header|Lisaac}}==

 

+ name := BUBBLE_SORT;

};

}.do_while {!sorted};

 

=={{header|Lua}}==

 

function bubbleSort(A)

local itemCount=#A

until hasChanged == false

end

 

Example:

list = { 5, 6, 1, 2, 9, 14, 2, 15, 6, 7, 8, 97 }

bubbleSort(list)

print(j)

end

 

=={{header|Lucid}}==

[http://i.csc.uvic.ca/home/hei/lup/06.html]

follow(bsort(allbutlast(b)),last(b)) fi

where

last(x) = (x asa iseod next x) fby eod;

allbutlast(x) = if not iseod(next x) then x else eod fi;

 

=={{header|M2000 Interpreter}}==

 

 

Module Bubble {

function bubblesort {

}

Bubble

 

=={{header|M4}}==

 

define(`randSeed',141592653)

show(`a')

bubblesort(`a')

 

{{out}}

 

=={{header|Maple}}==

len := numelems(arr):

while(true) do

if (not change) then break end if:

end do:

{{Out|Output}}

<pre>[0,0,2,3,3,8,17,36,40,72]</pre>

=={{header|Mathematica}}/{{header|Wolfram Language}}==

===Using pattern matching===

bubbleSort[sortedList_] := sortedList

{{out}}

<pre>{1, 3, 3, 4, 7, 8, 9, 10, 13}</pre>

===Classic version===

BubbleSort[in_List] := Module[{x = in, l = Length[in], swapped},

swapped = True;

x

]

{{out}}

<pre>{1, 2, 3, 4, 6, 7, 7, 8, 12}</pre>

=={{header|MATLAB}}==

 

 

hasChanged = true;

end %for

end %while

 

{{out}}

 

1 2 3 4 5 6 7 8 9</pre>

 

=={{header|MAXScript}}==

(

while true do

)

arr

-- Usage

 

=={{header|MMIX}}==

 

LOC Data_Segment

JMP 2B % loop

1H XOR $255,$255,$255

 

=={{header|Modula-2}}==

VAR

changed: BOOLEAN;

END

UNTIL NOT changed

 

=={{header|Modula-3}}==

 

 

PROCEDURE Sort(VAR a: ARRAY OF INTEGER) =

END;

END Sort;

 

=={{header|N/t/roff}}==

{{works with|GROFF (GNU Troff)|1.22.2}}

 

.ig

Bubble sort algorithm in Troff

.nr Ai 0 1

.while \n(Ai<\n(Ac \n[A\n+[Ai]]

 

===Output===

=={{header|Nanoquery}}==

{{trans|Python}}

changed = true

 

testset = bubble_sort(testset)

println testset

 

{{out}}

=={{header|Nemerle}}==

===Functional===

using System.Console;

 

WriteLine(Bubblesort(several));

}

===Imperative===

{{trans|C#}}

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.

using System.Console;

 

Write($"$i ");

}

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

 

return list

{{out}}

<pre style="height: 20ex; overflow: scroll;">

===Translation of Pseudocode===

This version is a direct implementation of this task's pseudocode.

options replace format comments java crossref savelog symbols binary

 

method isFalse public constant binary returns boolean

return \isTrue

 

=={{header|Nim}}==

var t = true

for n in countdown(a.len-2, 0):

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

bubbleSort a

{{out}}

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|Objeck}}==

{{trans|C}}

function : Swap(p : Int[]) ~ Nil {

t := p[0];

while (sorted = false);

}

 

=={{header|Objective-C}}==

BOOL done = false;

return unsorted;

}

 

=={{header|OCaml}}==

 

This version checks for changes in a separate step for simplicity.

let rec _bsort = function

| x :: x2 :: xs when x > x2 ->

let t = _bsort s in

if t = s then t

 

This version uses the polymorphic <tt>option</tt> type to designate unchanged lists. (The type signature of <tt>_bsort</tt> is now <tt>'a list -> 'a list option</tt>.) It is slightly faster than the previous one.

let rec _bsort = function

| x :: x2 :: xs when x > x2 -> begin

match _bsort s with

| None -> s

 

=={{header|Octave}}==

itemCount = length(v);

do

until(hasChanged == false)

s = v;

 

 

=={{header|Ol}}==

(define (bubble-sort x ??)

(define (sort-step l)

(print

(bubble-sort (iota 100) <))

 

{{Out}}

{{trans|NetRexx}}

This version exploits the &quot;Collection Classes&quot; and some other features of the language that are only available in Open Object Rexx.

Do

placesList = sampleData()

Exit

 

{{out}}

<pre style="height: 20ex; overflow: scroll;">

===Translation of Pseudocode===

This version is a direct implementation of this task's pseudocode.

Do

placesList = sampleData()

isFalse: procedure

return \isTrue()

 

===Classic [[REXX|Rexx]] Implementation===

A more &quot;traditional&quot; implementation of version 1 using only Rexx primitive constructs. This version has been tested with the ''Open Object Rexx'' and ''Regina'' Rexx interpreters and could equally have been exhibited as a [[#REXX|Rexx]] solution.

Do

placesList. = ''

End

Exit

 

=={{header|Oz}}==

In-place sorting of mutable arrays:

proc {BubbleSort Arr}

proc {Swap I J}

in

{BubbleSort Arr}

 

Purely-functional sorting of immutable lists:

local

fun {Loop Xs Changed ?IsSorted}

end

in

 

=={{header|PARI/GP}}==

for(i=1,#v-1,

for(j=i+1,#v,

);

v

 

=={{header|Pascal}}==

var

i, j, n: integer;

list[j + 1] := t;

end;

 

list: array[0 .. 9] of real;

// ...

 

=={{header|Perl}}==

sub bubble_sort {

for my $i (0 .. $#_){

}

}

 

Usage:

 

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"After: "</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">bubble_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

=={{header|PHP}}==

 

foreach($array as $i => &$val){

foreach($array as $k => &$val2){

}

return $array;

 

=={{header|PicoLisp}}==

(use Chg

(loop

(xchg L (cdr L))

(on Chg) ) )

 

=={{header|PL/I}}==

bubble_sort: procedure (A);

declare A(*) fixed binary;

end;

end;

 

=={{header|Pop11}}==

lvars n=length(v), done=false, i;

while not(done) do

vars ar = { 10 8 6 4 2 1 3 5 7 9};

bubble_sort(ar);

 

=={{header|PostScript}}==

/bubblesort{

/x exch def

x pstack

}def

 

=={{header|PowerShell}}==

$l = $a.Length

$hasChanged = $true

}

}

 

=={{header|Prolog}}==

to the bubble sort algorithm. Some of these are easier and shorter to code and work as well if not better. Having said that,

it's difficult to think of a reason to code the bubble sort these days except as an example of inefficiency.

% Bubble sort

 

writef(' input=%w\n', [In]),

bubblesort(In, R),

for example:

<pre>?- test.

Should be ISO (but tested only with GNU Prolog).

Note: doesn't constuct list for each swap, only for each pass.

 

 

test([8,9,1,3,4,2,6,5,4]).

 

{{Out}}

<pre>[8,9,1,3,4,2,6,5,4]

[1,3,2,4,5,4,6,8,9]

[1,2,3,4,4,5,6,8,9]</pre>

 

=={{header|Python}}==

"""Inefficiently sort the mutable sequence (list) in place.

seq MUST BE A MUTABLE SEQUENCE.

while changed:

changed = False

if seq[i] > seq[i+1]:

seq[i], seq[i+1] = seq[i+1], seq[i]

from random import shuffle

 

shuffle(testcase)

assert testcase != testset # we've shuffled it

bubble_sort(testcase)

 

=={{header|Quackery}}==

 

[ rot tuck over peek

[ 10 random join ]

say "Before: " dup echo cr

 

{{out}}

 

=={{header|Qi}}==

[A] -> [A]

[A B|R] -> [B|(bubble-shot [A|R])] where (> A B)

 

(bubble-sort [6 8 5 9 3 2 2 1 4 7])

 

=={{header|R}}==

The previously solution missed out on a cool R trick for swapping items and had no check for lists of length 1. As R is 1-indexed, we have aimed to be as faithful as we can to the given pseudo-code.

{

repeat

{

{

{

}

}

}

#Examples taken from the Haxe solution.

 

{{out}}

 

=={{header|Ra}}==

class BubbleSort

**Sort a list with the Bubble Sort algorithm**

list[i + 1] := temp

changed := true

 

=={{header|Racket}}==

This bubble sort sorts the elelement in the vector v with regard to <?.

 

#lang racket

 

(when again? (loop (- max 1) #f)))

v)

 

Example: Sorting a vector of length 10 with random entries.

(bubble-sort < (for/vector ([_ 10]) (random 20)))

 

=={{header|Raku}}==

{{works with|Rakudo|#24 "Seoul"}}

 

for ^@a -> $i {

for $i ^..^ @a -> $j {

}

}

 

=={{header|REXX}}==

===version 0, alpha-numeric vertical list===

This REXX version sorts (using a bubble sort) and displays an array &nbsp; (of alpha-numeric items) &nbsp; in a vertical list.

call gen /*generate the array elements (items).*/

call show 'before sort' /*show the before array elements. */

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the internal array list:}}

<br>(Shown at &nbsp; '''⁵/₆''' &nbsp; size.)

 

Programming note: &nbsp; a check was made to not exceed REXX's upper range limit of the &nbsp; '''random''' &nbsp; BIF.

parse arg N .; if N=='' | N=="," then N=30 /*obtain optional size of array from CL*/

call gen N /*generate the array elements (items). */

/*──────────────────────────────────────────────────────────────────────────────────────*/

gen: h=min(N+N,1e5); w=length(h); do j=1 for N; @.j=random(h); end; return

{{out|output|text=&nbsp; when using a internally generated random array of thirty integers &nbsp; (which are right-justified for alignment in the display):}}

<pre>

===version 2, random integers, horizontal list===

{{trans|PL/I}}

/*REXX*/

Call random ,,1000

show:

l=''; Do i=1 To a.0; l=l a.i; End; Say arg(1)':'l

{{out}}

<pre>vorher : 9 17 16 19 5 7 3 20 16 0

Also note that only four snapshots of the sort-in-progress is shown here, &nbsp; the REXX program will show a snapshot of ''every''

<br>sorting pass; &nbsp; the &nbsp; &nbsp; &nbsp; ''at &nbsp; (about) &nbsp; nnn% sorted'' &nbsp; &nbsp; &nbsp; was added after-the-fact.

parse arg N seed . /*obtain optional size of array from CL*/

if N=='' | N=="," then N=30 /*Not specified? Then use the default.*/

do s=# for # by -1; say $.s; end /*s*/

say "└"copies('─', #) /*display the horizontal axis at bottom*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

flag = 0

bubbleSort(bubbleList)

next

end

 

=={{header|Ruby}}==

{{eff note|Ruby|Array.sort!}}This example adds the bubblesort! method to the Array object. Below are two different methods that show four different iterating constructs in ruby.

 

def bubblesort1!

length.times do |j|

ary.bubblesort1!

p ary

 

=={{header|Rust}}==

let mut n = values.len();

let mut swapped = true;

bubble_sort(&mut strings);

println!("After: {:?}", strings);

 

=={{header|Sather}}==

private swap(inout a, inout b:T) is

temp ::= a;

end;

end;

 

main is

a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4|;

#OUT + a + "\n";

end;

 

This should be able to sort (in ascending order) any object for which <code>is_lt</code> (less than) is defined.

This slightly more complex version of Bubble Sort avoids errors with indices.

 

import o._

val consecutiveIndices = (arr.indices, arr.indices drop 1).zipped

}

} while(hasChanged)

 

 

def bubbleSort(xt: List[Int]) = {

}

bubble(xt, Nil, Nil)

 

=={{header|Scheme}}==

(letrec

((fix (lambda (f i)

(cons (car l) (sort-step (cdr l))))))))

 

 

This solution recursively finds the fixed point of sort-step. A comparison function must be passed to bubblesort. Example usages:

 

Here is the same function, using a different syntax:

 

(define (dosort l)

(cond ((null? (cdr l))

l

(bsort try gt?))))

For example, you could do

 

=={{header|Scilab}}==

n=length(a)

swapped=%T

end

b=a

{{out}}

<pre style="height:20ex">-->y=[5 4 3 2 1]

 

=={{header|Seed7}}==

local

var boolean: swapped is FALSE;

end for;

until not swapped;

 

Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#bubbleSort]

=={{header|Shen}}==

Bubble sort a vector in-place, using the < operator for comparison.

 

(define swap

{ (vector number) --> (vector number) }

A -> (let N (limit A)

 

 

__________

(vector-> (value *arr*) 4 2)

(vector-> (value *arr*) 5 8)

 

Here is a more idiomatic implementation:

{{trans|Qi}}

 

 

(define bubble-shot

(define bubble-sort

{ (vector number) --> (vector number) }

 

 

=={{header|Sidef}}==

loop {

var swapped = false

}

return arr

 

=={{header|Simula}}==

 

PROCEDURE BUBBLESORT(A); NAME A; INTEGER ARRAY A;

OUTIMAGE;

 

{{out}}

<pre>

A straight translation from the pseudocode above. Swap is done with a [[wp:Smalltalk#Code_blocks|block closure]].

 

item := #(1 4 5 6 10 8 7 61 0 -3) copy.

swap :=

[swap value: index value: index + 1.

hasChanged := true]].

 

=={{header|SNOBOL4}}==

 

define('bubble(a,alen)i,j,ub,tmp') :(bubble_end)

bubble i = 1; ub = alen

sloop j = j + 1; str = str arr<j> ' ' :s(sloop)

output = trim(str)

 

{{out}}

 

Static analysis of this code shows that it is guaranteed free of any run-time error when called from any other SPARK code.

is

 

 

end Bubble;

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.

is

end Bubble;

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.

<pre>

 

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.

is

procedure Sort (A : in out Arr)

 

end Bubble;

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.

<pre>bubble_sort_rule(1): sorted(A, I, J)

 

File '''bubble.ads''':

 

type Arr is array (Integer range <>) of Integer;

end Bubble;

 

File '''bubble.adb''':

procedure Sort (A : in out Arr)

end Bubble;

 

File '''main.adb''':

with Bubble;

 

end loop;

end Main;

 

File '''bubble.gpr''':

 

for Main use ("main.adb");

 

end Bubble;

 

To verify the program, execute the command: '''gnatprove -P bubble.gpr -j0 --level=2'''

=={{header|Standard ML}}==

Assumes a list of integers.

fun bubble_select [] = []

| bubble_select [a] = [a]

fun bubblesort [] = []

| bubblesort (x::xs) =bubble_select (x::(bubblesort xs))

 

=={{header|Stata}}==

function bubble_sort(a) {

n = length(a)

}

}

 

=={{header|Swift}}==

var done = false

while !done {

print(list1)

bubbleSort(list: &list1)

 

=={{header|Symsyn}}==

 

x : 23 : 15 : 99 : 146 : 3 : 66 : 71 : 5 : 23 : 73 : 19

" $r $s " []

return

 

=={{header|Tailspin}}==

templates bubblesort

templates bubble

[4,5,3,8,1,2,6,7,9,8,5] -> bubblesort -> !OUT::write

 

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

}

 

 

Idiomatic code uses the builtin <code>lsort</code> instead, which is a stable O(''n'' log ''n'') sort.

 

=={{header|Toka}}==

Toka does not have a bubble sort predefined, but it is easy to code a simple one:

 

value| array count changed |

[ ( address count -- )

foo 10 .array

foo 10 bsort

 

=={{header|TorqueScript}}==

 

function bubbleSort(%list)

{

}

return %list;

 

=={{header|Unicon}}==

 

=={{header|UnixPipes}}==

 

reset() {

}

 

 

=={{header|Ursala}}==

The bubblesort function is parameterized by a relational predicate.

 

bubblesort "p" = @iNX ^=T ^llPrEZryPrzPlrPCXlQ/~& @l ~&aitB^?\~&a "p"?ahthPX/~&ahPfatPRC ~&ath2fahttPCPRC

#cast %nL

 

{{out}}

<pre><140,212,247,270,315,362,449,532,567,677></pre>

 

=={{header|Vala}}==

if (array[i1] == array[i2])

return;

foreach (int i in array)

print("%d ", i);

{{out}}

<pre>

</pre>

 

println('Input: ${arr.str()}')

mut count := arr.len

mut arr := [3, 5, 2, 1, 4]

bubble(mut arr)

{{out}}

<pre>Input: [3, 5, 2, 1, 4]

=={{header|Wren}}==

Based on the pseudo-code in the Wikipedia article.

var n = a.count

if (n < 2) return

}

 

System.print("Before: %(a)")

bubbleSort.call(a)

System.print("After : %(a)")

System.print()

 

{{out}}

=={{header|X86 Assembly}}==

Translation of XPL0. Assemble with tasm, tlink /t

.code

.486

popa

ret

 

{{out}}

 

=={{header|Xojo}}==

Dim isDirty As Boolean

count = Ubound(list) // count the array size

End

Next

 

=={{header|XPL0}}==

string 0; \use zero-terminated strings

 

BSort(Str, StrLen(Str));

Text(0, Str); CrLf(0);

 

{{out}}

" .Pabcdeefghiiijklmnoooqrstuuvwxyz"

</pre>

 

=={{header|Yorick}}==

itemCount = numberof(items);

do {

}

} while(hasChanged);

 

=={{header|zkl}}==

itemCount := list.len();

do{

}while(hasChanged);

list

Or, punting early termination:

foreach n,index in ([list.len()-1..0,-1],n){

if (list[index] > list[index + 1]) list.swap(index,index + 1);

}

list

{{out}}

<pre>L(" "," "," ","T","a","e","h","i","i","s","s","s","t","t")</pre>

 

{{omit from|GUISS}}