Bubble sorting in progress

Question

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:

enter image description here

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

• Ton Hospel: 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 :)
• miles: Will the list be non-empty?
• miles: 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.

Answer 1

JavaScript (ES6), (削除) 102 (削除ここまで) (削除) 82 (削除ここまで) (削除) 80 (削除ここまで) (削除) 86 (削除ここまで) 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>

• Neil: 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).
• ETHproductions: @Neil Wow, that's impressive! You can post that as your own if you'd like.
• Jonathan Allan: @Neil You can do your recursive version in 80 too, just remove the last ,0
• edc65: Try 1/b instead of b+.5 to check for undefined
• edc65: Fine, my suggestion for 1/b still holds

Answer 2

Haskell, (削除) 83 (削除ここまで) (削除) 82 (削除ここまで) 81 bytes

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.

• Stewie Griffin: 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...?
• lynn: 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.
• nimi: @WeeingIfFirst: full program

Answer 3

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

• Maltysen: I think you can save by removing the plus and setting j=0 on the lambda default params
• Maltysen: also, you don't need to reset j, you can use %
• Jonathan Allan: @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.
• Stewie Griffin: 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.
• Jonathan Allan: Updated to include new test cases

Answer 4

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}

Test Cases

(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

Answer 5

Jelly, 25 bytes

ḣ©ṫ-Ṣ®ṖṖ¤;;ṫḊ\
JḊṁ13W¤;ç/

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

Answer 6

R, (削除) 132 (削除ここまで) (削除) 131 (削除ここまで) (削除) 112 (削除ここまで) 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.

• user45941: 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.
• Andreï V. Kostyrka: @Mego Okay, I fixed that. Please see if now it is fully compliant...
• rturnbull: 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.
• Andreï V. Kostyrka: @rturnbull Your version is so much better! Kudos to you.
• Andreï V. Kostyrka: @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?

Answer 7

Pyth, (削除) 34 (削除ここまで) 32 Bytes

AQVH=*<ZtlGZ=GsXJcG,Zh=hZ1ShtJ;G

A translation of Jonathan Allan's Python answer.

Try it here!

Answer 8

JavaScript (ES6), (削除) 82 (削除ここまで) (削除) 80 (削除ここまで) 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.

Answer 9

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

• Magic Octopus Urn: Impressive, very impressive +1.

Answer 10

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.

Answer 11

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}

Try it here: https://groovyconsole.appspot.com/script/6316871066320896

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

Answer 12

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.

• Jörg Hülsermann: php.net/manual/de/function.join.php alias of implode
• Jörg Hülsermann: $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.
• user59178: 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.

Answer 13

Ruby, (削除) 52 (削除ここまで) 50 bytes

Wait... no Ruby?

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