# Bubble sorting in progress

Create a function or program that takes two inputs:

• A list of integers that shall be sorted (less than 20 elements)
• A positive integer, N, saying how many comparisons you should take

The function shall stop, and output the resulting list of integers after N comparisons. If the list is fully sorted before N comparisons are made, then the sorted list should be outputted.

The Bubble sort algorithm is well known, and I guess most people know it. The following Pseudo-code and animation (both from the linked Wikipedia-article) should provide the necessary details:

procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure


The animation below shows the progress:

An example (taken directly from the linked Wikipedia article) shows the steps when sorting the list: ( 5 1 4 2 8 ):

First Pass

1: ( 5 1 4 2 8 ) ->  ( 1 5 4 2 8 ) // Here, algorithm compares the first two elements,
// and swaps since 5 > 1.
2: ( 1 5 4 2 8 ) ->  ( 1 4 5 2 8 ) // Swap since 5 > 4
3: ( 1 4 5 2 8 ) ->  ( 1 4 2 5 8 ) // Swap since 5 > 2
4: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 ) // Now, since these elements are already in order
// (8 > 5), algorithm does not swap them.


Second Pass

5: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 )
6: ( 1 4 2 5 8 ) ->  ( 1 2 4 5 8 ) // Swap since 4 > 2
7: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
8: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )


Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass

9: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
10:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
11:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
12:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )


## Test cases:

Format: Number of comparisons (N): List after N comparisons

Input list:
5  1  4  2  8
Test cases:
1: 1  5  4  2  8
2: 1  4  5  2  8
3: 1  4  2  5  8
4: 1  4  2  5  8
5: 1  4  2  5  8
6: 1  2  4  5  8
10: 1  2  4  5  8
14: 1  2  4  5  8

Input list:
0: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
Test cases:
1: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
21: -6  15  18   9  -7  -1   7  18  19  -5  19  19   5  15  -5   3  18  14  19  20
41: -6   9  -7  15  -1   7  18  18  -5  19  19   5  15  -5   3  18  14  19  19  20
60: -6  -7  -1   9   7  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
61: -6  -7  -1   7   9  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
81: -7  -6  -1   7   9  15  -5  18  18   5  15  -5   3  18  14  19  19  19  19  20
119: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
120: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
121: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
122: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
123: -7  -6  -1  -5   7   9   5  15  -5  15   3  18  14  18  18  19  19  19  19  20
201: -7  -6  -5  -1  -5   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20
221: -7  -6  -5  -5  -1   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20


• Yes, built-in Bubble sort algorithms are permitted.
• No, you can not assume only positive integers, or unique integers.
• The sorting must be in the order described above. You can't start at the end of the list
• Clear and perfectly reasonable. Just a pity since I have discovered a truly marvelous solution for the mirrored bubble sort which this comment is not too narrow to contain :) – Ton Hospel Sep 9 '16 at 7:10
• Will the list be non-empty? – miles Sep 12 '16 at 21:26
• Also, will the list have size greater than or equal to 2? I noticed some answers below do not work for lists of length 1 or empty lists. – miles Sep 12 '16 at 21:54

# Jelly, 25 bytes

ḣ©ṫ-Ṣ®ṖṖ¤;;ṫḊ¥
JḊṁ¹³W¤;ç/


Based on my answer in J.

Try it online!

Verify number of comparisons.

## Explanation

The helper link modifies the list at index [i-1, i] by sorting it which produces the same result as the bubble sort comparison.

ḣ©ṫ-Ṣ®ṖṖ¤;;ṫḊ¥  Helper link - Input: list A, index i
ḣ               Take the first i values
©              Save a copy of it
ṫ-            Take the last two values
Ṣ           Sort them
;      Append them to
®            Get the copy
ṖṖ¤         Pop the last two values (Ṗ is pop)
;     Prepend it to
ṫ      Take the last i values
Ḋ¥    Dequeue - remove the head

JḊṁ¹³W¤;ç/  Input: list A and # of comparisons n
J           Enumerate the indices of A
Ḋ          Dequeue - remove the head
ṁ         Reshape it cyclically to length n
¹        Identity function (Just to avoid parsing rules)
;    Append it to
³         The list A
W¤       Wrap it as an array
ç/  Reduce from left to right using the helper link and return


# JavaScript (ES6), 102828086 80 bytes

Bug fix and 1 byte saved thanks to @edc65

(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")


Recursion may not be is definitely not is probably the best approach, but I'm sticking with a loop for now.

### Try it out:

f=(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")
Enter your numbers:<br>
<input id=A rows=10 value="5 1 4 2 8"><br>
Enter the number of steps:<br>
<input type="number" min=0 id=B rows=10 value="1"><br>
<button onclick="C.innerHTML=f((A.value.match(/-?\d+/g)||[]).map(Number),B.value)">Run</button><br>
<pre id=C></pre>

• I managed to golf your recursive version down to 82 bytes too: f=(a,m,n=0,_,b=a[n+1])=>b+.5?m?f(a,m-1,n+1,a[n]>b?a[a[n+1]=a[n],n]=b:0):a:f(a,m,0). – Neil Sep 8 '16 at 21:22
• @Neil Wow, that's impressive! You can post that as your own if you'd like. – ETHproductions Sep 8 '16 at 21:24
• @Neil You can do your recursive version in 80 too, just remove the last ,0 – Jonathan Allan Sep 9 '16 at 3:23
• Try 1/b instead of b+.5 to check for undefined – edc65 Sep 9 '16 at 6:34
• Fine, my suggestion for 1/b still holds – edc65 Sep 9 '16 at 12:46

y%x@(a:b:c)=(y++x):(y++[min a b])%(max a b:c)
y%x=[]%(y++x)
[x]!_=[x]
x!n=[]%x!!n


Usage example: [5,1,4,2,8] ! 5 -> [1,4,2,5,8].

In function % y keeps track of the elements visited so far during the current pass, x are ones yet to examine. a and b are the next two, i.e. the candidates to swap. If we reach the end of the list, we start from the beginning: y%x = []%(y++x). All steps are stored in a list where the main function picks the nth element.

Edit: previous versions didn't work for single element lists, luckily the new version is even shorter.

• Is it possible to test this online? I don't know anything at all about Haskell, and get errors when trying to paste this directly into an online ide. I guess I'm missing some basic stuff...? – Stewie Griffin Sep 9 '16 at 7:21
• Add f= before the second line of the answer, then append a third line to the program containing main=print(f [5,1,4,2,8] 5). That should make it runnable. – Lynn Sep 9 '16 at 11:36
• @WeeingIfFirst: full program – nimi Sep 9 '16 at 15:39

# Python 3, 77 74 bytes

-3 bytes thanks to @Maltysen (init j in declaration)

lambda l,n,j=0:exec('j*=j<len(l)-1;l[j:j+2]=sorted(l[j:j+2]);j+=1;'*n)or l


Test cases at ideone

Uses sorted to do each compare and swap operation, but it is performing a bubble sort.

Sets j=0 (the left index), then performs n compare and swaps of adjacent list items, resetting j to 0 whenever this window goes out of bounds.

The j*=j<len(l)-1 will multiply j by False (i.e. 0) at that point, whereas every other time it will multiply j by True (i.e. 1).

(It will still work for an empty list too.)

• I think you can save by removing the plus and setting j=0 on the lambda default params – Maltysen Sep 9 '16 at 2:31
• also, you don't need to reset j, you can use % – Maltysen Sep 9 '16 at 2:32
• @Maltysen actually I can't use modulo arithmetic and save bytes, since we need to handle a list of length 1, when we would get a divide by zero error, adding in the logic to handle that pushes me up in bytes. – Jonathan Allan Sep 9 '16 at 2:53
• Works fine for all test cases, and is quite a bit shorter than my MATLAB answer. +1 =) Unfortunately, I can't use the same technique with eval in MATLAB because of the inline assignments. – Stewie Griffin Sep 9 '16 at 7:07
• Updated to include new test cases – Jonathan Allan Sep 9 '16 at 7:30

## PowerShell v2+, 135 129 bytes

param($a,$n)for($s=1;$s){($s=0)..($a.count-2)|%{if($a[$_]-gt$a[$_+1]){$a[$_],$a[$_+1]=$a[$_+1],$a[$_];$s=1}if(!--$n){$a;exit}}}$a


So. Many. Dollars.

(Saved six bytes by realizing that this challenge doesn't include the "for free" optimization of skipping the last element(s) on each pass since that's guaranteed sorted, and instead runs through a full pass each time. This moved the $a.count into the for loop and eliminated the $z variable.)

Straight up bubble sort, with one nifty spot, doing the swap in one step --
$a[$_],$a[$_+1]=$a[$_+1],$a[$_]

The exiting logic is handled via if(!--$n){$a;exit}

(The array is shown as space-separated here because the default Output Field Separator for stringifying an array is a space. The stringification happens because we're concatenating with the labels "$_ -> ".) PS C:\Tools\Scripts\golfing> 1,2,3,4,5,6,10,14|%{"$_ -> "+(.\bubble-sorting-in-progress.ps1 @(5,1,4,2,8) $_)} 1 -> 1 5 4 2 8 2 -> 1 4 5 2 8 3 -> 1 4 2 5 8 4 -> 1 4 2 5 8 5 -> 1 4 2 5 8 6 -> 1 2 4 5 8 10 -> 1 2 4 5 8 14 -> 1 2 4 5 8 PS C:\Tools\Scripts\golfing> 1,21,41,60,61,81,119,120,121,122,123,201,221|%{"$_ -> "+(.\bubble-sorting-in-progress.ps1 @(15,18,-6,18,9,-7,-1,7,19,19,-5,20,19,5,15,-5,3,18,14,19) $_)} 1 -> 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19 21 -> -6 15 18 9 -7 -1 7 18 19 -5 19 19 5 15 -5 3 18 14 19 20 41 -> -6 9 -7 15 -1 7 18 18 -5 19 19 5 15 -5 3 18 14 19 19 20 60 -> -6 -7 -1 9 7 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20 61 -> -6 -7 -1 7 9 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20 81 -> -7 -6 -1 7 9 15 -5 18 18 5 15 -5 3 18 14 19 19 19 19 20 119 -> -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20 120 -> -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20 121 -> -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20 122 -> -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20 123 -> -7 -6 -1 -5 7 9 5 15 -5 15 3 18 14 18 18 19 19 19 19 20 201 -> -7 -6 -5 -1 -5 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20 221 -> -7 -6 -5 -5 -1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20  ## R, 132131112 136 bytes The programme receives the input as follows: first N, then the vector itself. For example, if you want v = [5 1 4 2 8] and n = 1, the input that goes into the scan is 1 5 1 4 2 8. So in order to run this programme, you run the first line, feed the numbers one by one in the console, and then run the rest (this is a REPL answer). Then the following code does the trick: v=scan() s=m=0 while(!s){s=T;for(i in 3:length(v)){m=m+1 if(m>v[1]){s=T;break} if(v[i-1]>v[i]){v[c(i-1,i)]=v[c(i,i-1)];s=F}}} cat(v[-1])  Test: Input: a vector with N first and the elements to be sorted next 1 5 1 4 2 8 5 5 1 4 2 8 14 5 1 4 2 8 60 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19 Output: 1 5 4 2 8 1 4 2 5 8 1 2 4 5 8 -6 -7 -1 9 7 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20  Update: golfed 1 byte owing to Vlo. • This appears to require hardcoding the inputs as variables and implicitly displaying the output via a REPL mechanism, which is not accepable per our list of acceptable I/O methods. – user45941 Sep 9 '16 at 7:13 • @Mego Okay, I fixed that. Please see if now it is fully compliant... – Andreï Kostyrka Sep 9 '16 at 8:16 • It looks like you can remove the first s=T; and still have correct output; this saves you 4 bytes. EDIT: In fact, you can remove the while() loop entirely, and just use the for() loop, replacing your s=T with break, which also allows us to get rid of some curly braces. This yields: v=scan();s=m=0;for(i in 3:length(v)){m=m+1;if(m>v[1])break;if(v[i-1]>v[i]);v[c(i-1,i)]=v[c(i,i-1)];break}};v[-1] For a total of 117 bytes. – rturnbull Sep 9 '16 at 15:55 • @rturnbull Your version is so much better! Kudos to you. – Andreï Kostyrka Sep 9 '16 at 16:40 • @rturnbull Where did those early comments go? Your suggestion of golfing 19 bytes away... it just removed that extra loop that was essential because the performance of the bubble sort is O(n²), whereas without that extra loop, it becomes (n-1) long. I should have checked... Now it is fixed and contains an explanation how to feed in the input! Is it better than before? – Andreï Kostyrka Sep 10 '16 at 1:07 # Pyth, 34 32 Bytes AQVH=*<ZtlGZ=GsXJcG,Zh=hZ1ShtJ;G  A translation of Jonathan Allan's Python answer. Try it here! ## JavaScript (ES6), 8280 79 bytes f=(a,m,n=0,_,b=a[n+1])=>1/b?m?f(a,m-1,n+1,a[n]>b?a[a[n+1]=a[n],n]=b:0):a:f(a,m)  Based on @ETHproduction's original answer. Edit: Saved 2 bytes thanks to @JonathanAllan. Saved 1 byte thanks to @edc65. # J, 62 60 bytes >@([:({.,(2/:~@{.}.),]}.~2+[)&.>/]|.@;<:@#@]<@|i.@[)^:(]1<#)  This is a verb that takes two arguments: the number of comparisons on the LHS and the list of integers on the RHS. First it checks if the length of the list if greater than one. If it isn't, it returns the list unmodified, otherwise it operates on it by performing the specified number of comparisons before returning the result. ## Usage For the first test case, extras commands are used to format multiple input/output. The second test case is shown as single input/output.  f =: >@([:({.,(2/:~@{.}.),]}.~2+[)&.>/]|.@;<:@#@]<@|i.@[)^:(]1<#) 1 2 3 4 5 6 10 14 ([;f)"0 1 ] 5 1 4 2 8 ┌──┬─────────┐ │1 │1 5 4 2 8│ ├──┼─────────┤ │2 │1 4 5 2 8│ ├──┼─────────┤ │3 │1 4 2 5 8│ ├──┼─────────┤ │4 │1 4 2 5 8│ ├──┼─────────┤ │5 │1 4 2 5 8│ ├──┼─────────┤ │6 │1 2 4 5 8│ ├──┼─────────┤ │10│1 2 4 5 8│ ├──┼─────────┤ │14│1 2 4 5 8│ └──┴─────────┘ 1 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19 123 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19 _7 _6 _1 _5 7 9 5 15 _5 15 3 18 14 18 18 19 19 19 19 20 221 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19 _7 _6 _5 _5 _1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20  ## Explanation It's hard to write terse code in J that uses mutability, so instead I convert the problem into reducing a list on a set of indicies. I think this code is messy so I will walkthrough the job of each phrase instead of each primitive. The first part grabs the length of the list and produces a range. Then, operate on each infix of size 2 to emulate one pass of comparisons.  i. # 5 1 4 2 8 0 1 2 3 4 2 <\ i. # 5 1 4 2 8 ┌───┬───┬───┬───┐ │0 1│1 2│2 3│3 4│ └───┴───┴───┴───┘ 2 <@{.\ i. # 5 1 4 2 8 ┌─┬─┬─┬─┐ │0│1│2│3│ └─┴─┴─┴─┘  These are the start indicies of each comparison. If 7 comparisons are being performed, reshape it to get the desired amount. J parses right to left, so its reduces right to left, like fold-right. Append the initial list and reverse it.  7$ 2 <@{.\ i. # 5 1 4 2 8
┌─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│0│1│2│
└─┴─┴─┴─┴─┴─┴─┘
|. 5 1 4 2 8 ; 7 $2 <@{.\ i. # 5 1 4 2 8 ┌─┬─┬─┬─┬─┬─┬─┬─────────┐ │2│1│0│3│2│1│0│5 1 4 2 8│ └─┴─┴─┴─┴─┴─┴─┴─────────┘  Alternatively, the range [0, 7) can be made and each value taken modulo the length of the list minus 1 to create the same range.  (<: # 5 1 4 2 8) <@| i. 7 ┌─┬─┬─┬─┬─┬─┬─┐ │0│1│2│3│0│1│2│ └─┴─┴─┴─┴─┴─┴─┘  The last part is a verb that takes a list on the RHS and an index on the LHS which marks the start index of the comparison. Select the two elements starting at that index, sort them, and plug them back into the list and return it.  > ({.,(2/:~@{.}.),]}.~2+[)&.>/ |. 5 1 4 2 8 ; 7$ 2 <@{.\ i. # 5 1 4 2 8
1 2 4 5 8

• Impressive, very impressive +1. – Magic Octopus Urn Sep 9 '16 at 20:02

# Matlab, 93 91 bytes

function l=f(l,m)
n=numel(l)-1;i=0;while n&m;i=mod(i,n)+1;m=m-1;l(i:i+1)=sort(l(i:i+1));end


Saves 11 bytes by omitting if l(i)>l(i+1);l(i:i+1)=l([i+1,i]), and instead just sort the two elements every time. Works for lists of length 1. Could save a byte or two using Octave's m-- operator, but that's not much.

Saves two more bytes by setting n=numel(l)-1;, because then I can just do while n instead of while n>1, and i=mod(i,n)+1 instead of i=mod(i,n-1)+1.

For the record, this answer was written many hours after the challenge was created.

# Groovy (101 Bytes)

{l,n->(l.size()..0).each{i->(0..i-2).each{if(l[it]>l[it+1] && n>0 && it>-1){l.swap(it,it+1)};n--}};l}


EDIT: I didn't need to write my own swap closure, groovy had this built in.
Try it here: https://groovyconsole.appspot.com/script/5104724189642752

## Example Output Trace:

4:[1, 5, 4, 2, 8]
3:[1, 4, 5, 2, 8]
2:[1, 4, 2, 5, 8]
1:[1, 4, 2, 5, 8]
0:[1, 4, 2, 5, 8] - Locks in the final answer.
-1:[1, 4, 2, 5, 8]
-2 (Return):[1, 4, 2, 5, 8]


# Old Implementation (122 Bytes)

m={l,n->s={x,y->t=l[x];l[x]=l[y];l[y]=t};((l.size()-2)..2).each{i->(0..i).each{if(l[it]>l[it+1] && n){s(it,it+1)};n--}};l}

• This errors for lists with fewer than two items – Jonathan Allan Sep 9 '16 at 2:56
• On my mobile... addding it>=0 in the second if statement fixes that problem. – Magic Octopus Urn Sep 9 '16 at 5:18
• It seems to fail for lists with negative input too. For instance the second test case. – Stewie Griffin Sep 9 '16 at 6:33
• Works now, I was on a mobile last night so I couldn't make the edits required. – Magic Octopus Urn Sep 9 '16 at 13:22

# php, 148 145 bytes

<?php for($i=2,$a=$argv;$a[1]--;$i=$i==count($a)-2?2:$i+1)if($a[$i]>$a[$i+1])list($a[$i],$a[$i+1])=[$a[$i+1],$a[$i]];echo substr(join(' ',$a),5);  I'm not very happy with the loop structure but I like the list switch and it does work so I'm posting it anyway. php7.1 would allow me to save at least 4 bytes. With nicer formatting: <?php for($i=2,$a=$argv;$a[1]--;$i=$i==count($a)-2?2:$i+1) if($a[$i]>$a[$i+1]) list($a[$i],$a[$i+1])=[$a[$i+1],$a[$i]]; echo substr(join(' ',$a),5);


Edit: Jörg Hülsermann reminded me of join, instead of implode.
note: needs to be in a file with a single character filename.

• php.net/manual/de/function.join.php alias of implode – Jörg Hülsermann Sep 9 '16 at 18:00
• $t=$a[$i];$a[$i]=$a[$i+1];$a[$i+1]=$t; is shorter then list($a[$i],$a[$i+1])=[$a[$i+1],$a[$i]]; and i am not sure if instead of echo substr(implode(' ',$a),5); this one$a[1]=null;echo join(' ',$a); the better alternative is. – Jörg Hülsermann Sep 9 '16 at 19:32 • While using the temporary variable is 2 bytes shorter it's also multiple statements so you need to use those 2 bytes to enclose the whole thing in curly braces. For the$a[1]=null you'd actually need to unset($a[0],$a[1]) to avoid whitespace and the name of the file at the beginning. – user59178 Sep 12 '16 at 9:08

## Ruby, 52 50 bytes

Wait... no Ruby?

->l,n{n.times{|a|l[s=a%~-l.size,2]=l[s,2].sort};l}