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:

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 )

Examples:

( 5 1 4 2 8 ), 1    // Input
( 1 5 4 2 8 )       // Output

( 5 1 4 2 8 ), 5
( 1 4 2 5 8 )

( 5 1 4 2 8 ), 14
( 1 2 4 5 8 )

Yes, built-in Bubble sort algorithms are permitted. No, you can not assume only positive integers, or unique integers.

This bubbles the largest value to the end. May we bubble the smallest value to the front instead ? (working in mirror image) — Ton Hospel, 6 hours ago

ETHproductions · Answer 1 · 2016-09-09 03:27:15Z

up vote 5 down vote

JavaScript (ES6), 102 82 80 bytes

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

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

Try it out:

f=(a,m)=>eval("for(i=0;m--;a[i]>b?a[a[i+1]=a[i],i]=b:0,i++)b=a[i+1],b+.5?0: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)||[],B.value)">Run</button><br>
<pre id=C></pre>

edited 1 hour ago

answered 8 hours ago

ETHproductions

12.1k22073

SyntaxError: missing : in conditional expression. – Neil 7 hours ago

@Neil Thanks, fixed. I had simply forgotten to include those parentheses; the program with parens is 82 bytes. – ETHproductions 7 hours ago

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 7 hours ago

@Neil Wow, that's impressive! You can post that as your own if you'd like. – ETHproductions 7 hours ago

@Neil You can do your recursive version in 80 too, just remove the last ,0 – Jonathan Allan 1 hour ago

add a comment |

nimi · Answer 2 · 2016-09-08 21:20:55Z

Haskell, 83 82 bytes

x#i|(h,a:b:c)<-splitAt i x=x:(h++min a b:max a b:c)#mod(i+1)(length x-1)
(!!).(#0)

Usage example: ( (!!).(#0) )[5,1,4,2,8] 5 -> [1,4,2,5,8].

x # i splits the list x at index i and swaps the elements there if necessary. It builds a list of such steps by appending a recursive call with index increased by 1 (modulus the length of the list, to wrap around). The main function picks the nth element of this list.

TimmyD · Answer 3 · 2016-09-08 20:44:54Z

PowerShell v2+, 135 bytes

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

So. Many. Dollars.

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..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
7 -> 1 2 4 5 8
8 -> 1 2 4 5 8
9 -> 1 2 4 5 8
10 -> 1 2 4 5 8
11 -> 1 2 4 5 8
12 -> 1 2 4 5 8
13 -> 1 2 4 5 8
14 -> 1 2 4 5 8

carusocomputing · Answer 4 · 2016-09-08 22:25:04Z

Groovy (90 Bytes)

{l,n->(l.size()-2..2).each{i->(0..i).each{if(l[it]>l[it+1] && n){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/5183970899656704

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

This errors for lists with fewer than two items – Jonathan Allan 2 hours ago — Jonathan Allan, 2 hours ago

Jonathan Allan · Answer 5 · 2016-09-09 02:52:46Z

up vote 1 down vote

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

edited 2 hours ago

answered 5 hours ago

Jonathan Allan

2,09718

1

I think you can save by removing the plus and setting j=0 on the lambda default params – Maltysen 2 hours ago

1

also, you don't need to reset j, you can use % – Maltysen 2 hours ago

@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 2 hours ago

add a comment |

Andreï Kostyrka · Answer 6 · 2016-09-09 00:52:25Z

R, 116 bytes

You wrote that the vector to sort and the number of comparisons shall be supplied; let’s name them v and n respectively. Let them be pre-defined and therefore excluded from the byte count, as in the other responses:

v <- c(5, 1, 4, 2, 8)
n <- 1

Then the following code does the trick:

s=T;m=0
while(s){s=F;for(i in 2:length(v)){m=m+1
if(m>n){s=F;break}
if(v[i-1]>v[i]){v[c(i-1,i)]=v[c(i,i-1)];s=T}}}
v

Test:

Steven H. · Answer 7 · 2016-09-09 05:04:42Z

up vote 0 down vote

Pyth, 34 32 Bytes

AQVH=?gZlG0Z=GsXJcG,Zh=hZ1ShtJ;G

A translation of Johnathan Allan's Python answer.

Try it here!

answered 6 mins ago

Steven H.

763112

add a comment |

asked	today
viewed	338 times
active	today

current community

your communities

more stack exchange communities

Bubble sorting in progress

Examples:

7 Answers 7

JavaScript (ES6), 102 82 80 bytes

Try it out:

Haskell, 83 82 bytes

PowerShell v2+, 135 bytes

Test Cases

Groovy (90 Bytes)

Example Output Trace:

Old Implementation (122 Bytes)

Python 3, 77 74 bytes

R, 116 bytes

Pyth, 34 32 Bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf sorting or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Bubble sorting in progress

Examples:

7 Answers 7

JavaScript (ES6), 102 82 80 bytes

Try it out:

Haskell, 83 82 bytes

PowerShell v2+, 135 bytes

Test Cases

Groovy (90 Bytes)

Example Output Trace:

Old Implementation (122 Bytes)

Python 3, 77 74 bytes

R, 116 bytes

Pyth, 34 32 Bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf sorting or ask your own question.

Related

Hot Network Questions