17
\$\begingroup\$

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!

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Do we have to implement the exact algorithm specified in your challenge? \$\endgroup\$ Commented Feb 19, 2019 at 3:00
  • 1
    \$\begingroup\$ Will the array be at least 2x2? \$\endgroup\$ Commented Feb 19, 2019 at 3:50
  • 3
    \$\begingroup\$ @EmbodimentofIgnorance: only if you prove that it results in an equivalent sort in all cases. I expect this to be a non-trivial proof. \$\endgroup\$ Commented Feb 19, 2019 at 6:04
  • 5
    \$\begingroup\$ Whoever voted to close this as "too broad", would you mind explaining your reasoning? This was in the sandbox for a week with 3 upvotes and no comments for correction, so the prior consensus was that this was a decent challenge. \$\endgroup\$ Commented Feb 19, 2019 at 6:08

10 Answers 10

Reset to default
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 75 bytesSBCS

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ -11 \$\endgroup\$ Commented Feb 25, 2019 at 10:57
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 208 bytes with output to Debug / STDERR. \$\endgroup\$ Commented Feb 19, 2019 at 13:28
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.