Sorting algorithms/Bubble sort: Difference between revisions

Line 2:

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(n<sup>2</sup>) performance, it is not used often for large (or even medium-sized) datasets.

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(n<sup>2</sup>) 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.

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

Line 321:

Line 325:

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

)</lang>

Output:

<pre>

Before: +1 +6 +3 +5 +2 +9 +8 +4 +7 +0

After: +0 +1 +2 +3 +4 +5 +6 +7 +8 +9

</pre>

=={{header|AutoHotkey}}==

Line 488:

Line 494:

next n

</lang>

~~Output:~~(example)

{{out}}(example)

<pre>

Original set

Line 520:

Line 526:

UNTIL l% = 0

ENDPROC</lang>

'''Output:'''

<pre>

-31 0 1 2 2 4 65 83 99 782

</pre>

=={{header| zx spectrum basic}}==

Line 601:

Line 608:

std::cout << "\n";

}</lang>

Output:

<pre>

-199 -52 2 3 33 56 99 100 177 200

Line 852:

Line 859:

</lang>

<pre> Output: 02;04;11;17;19;24;24;28;44;46; </pre>

Line 976:

Line 984:

Readln;

end.</lang>

Output:

<pre>

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

Line 1,078:

Line 1,086:

<code lang="eiffel">MY_SORTED_SET</code> redefines only the routine <code lang="eiffel">sort</code> which contains the implementation of the sort algorithm. The implementation in the redefined version of <code lang="eiffel">sort</code> in <code lang="eiffel">MY_SORTED_SET</code> uses a bubble sort.

Output:

<pre>

Before: 7 10 4 8 9 3 5 1 6 2

Line 1,084:

Line 1,092:

</pre>

<code lang="eiffel">TWO_WAY_SORTED_SET</code> is implemented internally as a list.

<code lang="eiffel">TWO_WAY_SORTED_SET</code> is implemented internally as a list. For this example, we use the feature <code lang="eiffel">put_front</code> 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 <code lang="eiffel">extend</code> (rather than <code lang="eiffel">put_front</code>) to add elements to the list. This would assure that the order was maintained even as elements were added.

For this example, we use the feature <code lang="eiffel">put_front</code> 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 <code lang="eiffel">extend</code> (rather than <code lang="eiffel">put_front</code>) to add elements to the list.

This would assure that the order was maintained even as elements were added.

=={{header|Erlang}}==

Line 1,141:

Line 1,153:

pretty_print(1,bubble_sort(s),{2})</lang>

Output:

<pre>Before: {

4,

Line 1,449:

Line 1,461:

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:

<pre>..............................................................................................................................................[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]</pre>

Line 1,531:

Line 1,543:

end</lang>

Sample output:

<pre>Sorting Demo using procedure bubblesort

on list : [ 3 14 1 5 9 2 6 3 ]

Line 1,682:

Line 1,694:

print(my_arr);</lang>

Output:

<pre>

A,B,C,D,E,F,G

</pre>

=={{header|jq}}==

<lang jq>def bubble_sort:

Line 1,919:

Line 1,934:

show(`a')</lang>

Output:

<pre>17 63 80 55 90 88 25 9 71 38

Line 1,954:

Line 1,969:

end %bubbleSort</lang>

Sample Output:

<~~lang MATLAB~~>bubbleSort([5 3 8 4 9 7 6 2 1])

<pre>bubbleSort([5 3 8 4 9 7 6 2 1])

ans =

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

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

=={{header|MAXScript}}==

Line 2,229:

Line 2,244:

return list

</lang>

;Output

UK London

Line 2,317:

Line 2,332:

bubbleSort a

echo a</lang>

Output:

Line 2,482:

Line 2,497:

</lang>

;Output

UK London

Line 2,928:

Line 2,943:

main :- test(T), bubble_sort(T,_), halt.</lang>

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

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

Line 3,120:

Line 3,135:

say copies('─',80) /*show a separator line. */

return</lang>

'''output'''

element 1 before sort: ---letters of the Hebrew alphabet---

Line 3,385:

Line 3,400:

end</lang>

Output:

<pre>33 99 15 54 1 20 88 47 68 72

1 15 20 33 47 54 68 72 88 99</pre>

Line 3,866:

Line 3,881:

example = bubblesort(nleq) <362,212,449,270,677,247,567,532,140,315></lang>

output:

Line 3,918:

Line 3,933:

</lang>

=====Output=====

<pre>

great eastern, roe, stirling, albany, leach

Line 3,974:

Line 3,989:

end start</lang>

Output:

<pre>

.Pabcdeefghiiijklmnoooqrstuuvwxyz

Line 4,005:

Line 4,020:

]</lang>

Output:

<pre>

" .Pabcdeefghiiijklmnoooqrstuuvwxyz"