Sorting algorithms/Bubble sort: Difference between revisions

{{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}}==

{{trans|Java}}

Assume numbers are in a DIM of size "size" called "nums".

DO

changed = 0

END IF

NEXT

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

==={{header|Sinclair ZX81 BASIC}}===

Works with the 1k RAM model. For simplicity, and to make it easy to animate the sort as it is going on, this implementation sorts a string of eight-bit unsigned integers which can be treated as character codes; it could easily be amended to sort an array of numbers or an array of strings, but the array would need to be dimensioned at the start.

20 PRINT S$

30 LET L=LEN S$-1

120 NEXT I

130 LET L=L-1

{{out}}

<pre> AABBBBCDDEEFILLNNNORRRUUU</pre>

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

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

==={{header|BaCon}}===

Numeric example:

total = 10

WHILE total > 1

DECR total

WEND

{{out}}

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

String example:

total = AMOUNT(t$)

WHILE total > 1

DECR total

WEND

{{out}}

<pre>Amsterdam Bern Bonn Kiev Lima Madrid Moscow Paris Rome Vienna Warschau</pre>

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

=={{header|Draco}}==

proc nonrec bubblesort([*] int a) void:

bool sorted;

write("After sorting: ");

for i from 0 upto 9 do write(a[i]:5) od

{{out}}

<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17

=={{header|Dyalect}}==

var done = false

while !done {

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.

{{trans|C#}}

ELENA 5.0 :

import extensions;

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|FreeBASIC}}==

Per task pseudo code:

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsort -7 3 -4 -6 4 -1 -2 2 7 0 5 1 -3 -5 6

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

(fun bubbles (vs)

(let done? F n (len vs))

---

(1 2 3)

=={{header|Gambas}}==

'''[https://gambas-playground.proko.eu/?gist=ba84832d633cb92bbe6c2f54704819c3 Click this link to run this code]'''

Dim byToSort As Byte[] = [249, 28, 111, 36, 171, 98, 29, 448, 44, 147, 154, 46, 102, 183, 24,

120, 19, 123, 2, 17, 226, 11, 211, 25, 191, 205, 77]

Print

Output:

<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|Liberty BASIC}}==

itemCount = 20

dim item(itemCount)

next i

end

=={{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}}

=={{header|MAXScript}}==

(

while true do

)

arr

-- Usage

=={{header|MMIX}}==

LOC Data_Segment

JMP 2B % loop

1H XOR $255,$255,$255

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