2-Dimensional Bubble Sort

Question

Sorting makes no sense for a 2-dimensional array... or does it?

Your task is to take an input grid and apply a bubble-sort-like algorithm to it until all values in the grid are non-decreasing from left to right and top to bottom along every row and column.

The algorithm works as follows:

• Each pass goes row by row, top to bottom, comparing/swapping each cell with its right and below neighbors.
  • if the cell is greater than only one of its right and below neighbors, swap with the one that it is greater than
  • if the cell is greater than both its right and below neighbors, swap with the smaller neighbor
  • if the cell is greater than both its right and below neighbors, which are the same value, then swap with the below neighbor.
  • if the cell is not greater than either of its right and below neighbors, do nothing
• Continue this until no swaps are made throughout the entire pass. This will be when every row and column are in order, left to right and top to bottom.

Example

4 2 1
3 3 5
7 2 1

The first row of the pass will swap the 4 and the 2, then the 4 with the 1.

2 1 4
3 3 5
7 2 1

When we get the the middle 3, it will be swapped with the 2 below

2 1 4
3 2 5
7 3 1

Then the 5 gets swapped with the 1 below

2 1 4
3 2 1
7 3 5

The last row of the first pass moves the 7 all the way to the right

2 1 4
3 2 1
3 5 7

Then we go back to the top row again

1 2 1
3 2 4
3 5 7

And continue row by row...

1 2 1
2 3 4
3 5 7

... until the grid is "sorted"

1 1 2
2 3 4
3 5 7

Another Example

3 1 1
1 1 1
1 8 9

becomes

1 1 1
1 1 1
3 8 9

rather than

1 1 1
1 1 3
1 8 9

because the downward swap takes priority when both the right and below neighbors of a cell are equal.

A step-by-step reference implementation can be found here.

Test cases

5 3 2 6 7 3 1 0
3 2 1 9 9 8 3 0
3 2 2 8 9 8 7 6

becomes

0 0 1 1 2 2 3 6
2 2 3 3 6 7 8 8
3 3 5 7 8 9 9 9

---

2 1 2 7 8 2 1 0
2 2 2 2 3 2 1 0
1 2 3 4 5 4 3 2
9 8 7 6 5 4 3 6
6 5 4 3 2 2 1 0

becomes

0 0 0 1 1 1 2 2
1 1 2 2 2 2 2 2
2 2 2 2 3 3 3 3
3 4 4 4 4 5 6 6
5 5 6 7 7 8 8 9

Rules

• You can take the input grid in any convenient format
• You may assume the grid values are all non-negative integers in the unsigned 16-bit range (0-65535).
• You may assume the grid is a perfect rectangle and not a jagged array. The grid will be at least 2x2.
• If you use another algorithm of sorting, you must supply a proof that it will always produce the same resulting order as this particular brand of 2D bubble sorting, no matter what the input is. I expect this to be a non-trivial proof, so you're probably better off using the described algorithm.

Happy Golfing!

Answer 1

JavaScript (Node.js), 129 bytes

a=>[...a+''].map(t=>a.map((l,y)=>l.map((v,x)=>(L=a[y+1]||[],d=L[X=x],r=l[x+1],v>r?r>=d||(L=l,X++):v>d||(L=l),l[x]=L[X],L[X]=v))))

Try it online!

Answer 2

APL (Dyalog Unicode), 75 bytes^SBCS

Thanks to @Adám for saving 11 bytes.

{m⊣{d r←⍵∘(s⌊+)¨↓∘.=⍨⍳2⋄∨/c>a c b←m[r⍵d]:m⊢←⌽@⍵(d r⊃⍨1+b>a)⊢m⋄⍬}¨⍳s←⍴m←⍵}⍣≡

Try it online!

Answer 3

Wolfram Language (Mathematica), 183 bytes

(R=#;{a,b}=Dimensions@R;e=1;g:=If[Subtract@@#>0,e++;Reverse@#,#]&;While[e>0,e=0;Do[If[j<b,c=R[[i,j;;j+1]];R[[i,j;;j+1]]=g@c]If[i<a,c=R[[i;;i+1,j]];R[[i;;i+1,j]]=g@c],{i,a},{j,b}]];R)&

Try it online!

I'm not a Mathematica expert, I'm sure it can be done shorter. Particularly I think that the double if statement could be shortened using Transpose but I don't know how.

Answer 4

R, 169 165 144 132 bytes

function(m,n=t(m)){while(any(F-(F=n)))for(i in 1:sum(1|n)){j=(j=i+c(0,r<-nrow(n),!!i%%r))[order(n[j])[1]];n[c(i,j)]=n[c(j,i)]};t(n)}

Try it online!

Answer 5

Clean, 240 bytes

import StdEnv
$l=limit(iterate?l)
?[]=[]
?l#[a:b]= @l
=[a: ?b]
@[[a,b:c]:t]#(t,[u:v])=case t of[[p:q]:t]=([q:t],if(a>p&&b>=p)[b,p,a]if(a>b)[a,b,p][b,a,p]);_=(t,sortBy(>)[a,b])
=[v%(i,i)++j\\i<-[0..]&j<- @[[u:c]:t]]
@l=sort(take 2l)++drop 2l

Try it online!

Implements the algorithm exactly as described.

Link includes input parsing to take the format in the question.

Answer 6

Python 2, 215 208 bytes

m=input()
h=len(m);w=len(m[0])
while 1:
 M=eval(`m`)
 for k in range(h*w):i,j=k/w,k%w;v,b,a=min([(M[x][y],y,x)for x,y in(i,j),(i+(i<h-1),j),(i,j+(j<w-1))]);M[i][j],M[a][b]=M[a][b],M[i][j]
 M!=m or exit(M);m=M

Try it online!

_{-7 bytes, thanks to ovs}

Answer 7

C# (.NET Core), 310 bytes

Without LINQ. Uses using System.Collections.Generic only for formatting the output after the function is returned. Thing is stupid huge. Looking forward to the golfs!

a=>{int x=a.GetLength(0),y=a.GetLength(1);bool u,o;int j=0,k,l,t,z;for(;j<x*y;j++)for(k=0;k<x;k++)for(l=0;l<y;){o=l>y-2?0>1:a[k,l+1]<a[k,l];u=k>x-2?0>1:a[k+1,l]<a[k,l];z=t=a[k,l];if((u&!o)|((u&o)&&(a[k,l+1]>=a[k+1,l]))){t=a[k+1,l];a[k+1,l]=z;}else if((!u&o)|(u&o)){t=a[k,l+1];a[k,l+1]=z;}a[k,l++]=t;}return a;}

Try it online!

Answer 8

Python 2, 198 bytes

G=input()
O=e=enumerate
while O!=G:
 O=eval(`G`)
 for i,k in e(G):
	for j,l in e(k):v,x,y=min((G[i+x/2][j+x%2],x&1,x/2)for x in(0,1,2)if i+x/2<len(G)and j+x%2<len(k));G[i][j],G[i+y][j+x]=v,l
print G

Try it online!

Developed independently from TFeld's answer, has some differences.

Answer 9

Charcoal, 118 bytes

≔Ｉ9.e999η≧⁻ηηＦθ⊞ιη⊞θ⟦η⟧ＦΣＥθＬι«ＦＬθ«≔§θκιＦＬι«≔§ιλζ≔§ι⊕λε≔§§θ⊕κλδ¿››ζδ›δ嫧≔§θ⊕κλζ§≔ιλδ»¿›ζ嫧≔ι⊕λζ§≔ιλε»»»»¿⊟θ¿Ｅθ⊟ιＥθ⪫ι 

Try it online! Link is to verbose version of code. I've also spent a few bytes on some prettier formatting. Explanation:

≔Ｉ9.e999η≧⁻ηηＦθ⊞ιη⊞θ⟦η⟧

JavaScript has the convenient property that a[i]>a[i+1] is false if i is the last element of the array. To emulate that in Charcoal, I calculate a nan by casting 9.e999 to float and then subtracting it from itself. (Charcoal doesn't support exponential float constants.) I then pad the original array on the right with the nan and also add an additional row containing just the nan. (Charcoal's cyclic indexing means that I only need one element in that row.)

ＦΣＥθＬι«

Loop for each element in the array. This should be more than enough loops to get the job done, as I'm including all the extra nans too.

ＦＬθ«≔§θκι

Loop over each row index and get the row at that index. (Charcoal can do both with an expression but not with a command.) This includes the dummy row but that's not a problem because all of the comparisons will fail.

ＦＬι«≔§ιλζ

Loop over each column index and get the value at that index. Again, this will loop over the dummy values but the comparisons will just fail again.

≔§ι⊕λε≔§§θ⊕κλδ

Also get the values to the right and below.

¿››ζδ›δ嫧≔§θ⊕κλζ§≔ιλδ»

If the cell is greater than the value below and it's not true that the value below is greater than the value to the right then swap the cell with the value below.

¿›ζ嫧≔ι⊕λζ§≔ιλε»»»»

Otherwise if the cell is greater than the value to the right then swap them.

¿⊟θ¿Ｅθ⊟ιＥθ⪫ι 

Remove the nan values and format the array for implicit output.

Answer 10

Kotlin, 325 bytes

{m:Array<Array<Int>>->val v={r:Int,c:Int->if(r<m.size&&c<m[r].size)m[r][c]
else 65536}
do{var s=0>1
for(r in m.indices)for(c in m[r].indices)when{v(r,c)>v(r+1,c)&&v(r+1,c)<=v(r,c+1)->m[r][c]=m[r+1][c].also{m[r+1][c]=m[r][c]
s=0<1}
v(r,c)>v(r,c+1)&&v(r,c+1)<v(r+1,c)->m[r][c]=m[r][c+1].also{m[r][c+1]=m[r][c]
s=0<1}}}while(s)}

Try it online!