Ordenar no tiene sentido para una matriz bidimensional ... ¿o sí?

Su tarea es tomar una cuadrícula de entrada y aplicarle un algoritmo de tipo burbuja hasta que todos los valores de la cuadrícula no disminuyan de izquierda a derecha y de arriba a abajo a lo largo de cada fila y columna.

El algoritmo funciona de la siguiente manera:

• Cada pase va fila por fila, de arriba abajo, comparando / intercambiando cada celda con sus vecinos derecho e inferior.
  • si la celda es mayor que solo uno de sus vecinos derechos e inferiores, intercambie con el que es mayor que
  • Si la celda es mayor que sus vecinos derecho e inferior, intercambie con el vecino más pequeño
  • si la celda es mayor que sus vecinos derecho e inferior, que tienen el mismo valor, intercambie con el vecino inferior.
  • si la celda no es mayor que cualquiera de sus vecinos derechos e inferiores, no haga nada
• Continúe esto hasta que no se realicen intercambios en todo el pase. Esto será cuando cada fila y columna estén en orden, de izquierda a derecha y de arriba a abajo.

Ejemplo

4 2 1
3 3 5
7 2 1

La primera fila del pase intercambiará el 4 y el 2, luego el 4 con el 1.

2 1 4
3 3 5
7 2 1

Cuando obtengamos el 3 del medio, se intercambiará con el 2 a continuación

2 1 4
3 2 5
7 3 1

Luego el 5 se intercambia con el 1 a continuación

2 1 4
3 2 1
7 3 5

La última fila de la primera pasada mueve el 7 completamente hacia la derecha

2 1 4
3 2 1
3 5 7

Luego volvemos a la fila superior nuevamente

1 2 1
3 2 4
3 5 7

Y continuar fila por fila ...

1 2 1
2 3 4
3 5 7

... hasta que la cuadrícula esté "ordenada"

1 1 2
2 3 4
3 5 7

Otro ejemplo

3 1 1
1 1 1
1 8 9

se convierte

1 1 1
1 1 1
3 8 9

más bien que

1 1 1
1 1 3
1 8 9

porque el intercambio hacia abajo tiene prioridad cuando los vecinos derecho e inferior de una celda son iguales.

Una implementación de referencia paso a paso se puede encontrar aquí .

Casos de prueba

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

se convierte

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

se convierte

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

Reglas

• Puede tomar la cuadrícula de entrada en cualquier formato conveniente
• Puede suponer que los valores de la cuadrícula son todos enteros no negativos en el rango de 16 bits sin signo (0-65535).
• Puede suponer que la cuadrícula es un rectángulo perfecto y no una matriz irregular. La cuadrícula será al menos 2x2.
• Si usa otro algoritmo de clasificación, debe proporcionar una prueba de que siempre producirá el mismo orden resultante que esta marca particular de clasificación de burbujas 2D, sin importar cuál sea la entrada. Espero que esto sea una prueba no trivial, por lo que probablemente sea mejor usar el algoritmo descrito.

¡Feliz golf!

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

Pruébalo en línea!

APL (Dyalog Unicode) , ^{SBCS de} 75 bytes

Gracias a @ Adám por guardar 11 bytes.

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

Pruébalo en línea!

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

Pruébalo en línea!

No soy un experto en Mathematica, estoy seguro de que se puede hacer más corto. Particularmente creo que la declaración double if podría acortarse usando Transposepero no sé cómo.

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

Pruébalo en línea!

Limpio , 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

Pruébalo en línea!

Implementa el algoritmo exactamente como se describe.

El enlace incluye análisis de entrada para tomar el formato en la pregunta.

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

Pruébalo en línea!

_{-7 bytes, gracias a los ovs}

C # (.NET Core) , 310 bytes

Sin LINQ Se usa System.Collections.Generic solo para formatear la salida después de que se devuelve la función. La cosa es estúpidamente enorme. Mirando hacia el golf!

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;}

Pruébalo en línea!

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

Pruébalo en línea!

Desarrollado independientemente de la respuesta de TFeld, tiene algunas diferencias.

Carbón , 118 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. También he gastado algunos bytes en un formato más bonito. Explicación:

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

JavaScript tiene la propiedad conveniente que a[i]>a[i+1]es falsa si ies el último elemento de la matriz. Para emular eso en el carbón, calculo un nanpor 9.e999flotación y luego lo resta de sí mismo. (El carbón no admite constantes de flotación exponencial). Luego relleno la matriz original a la derecha con el nany también agrego una fila adicional que contiene solo el nan. (La indexación cíclica del carbón vegetal significa que solo necesito un elemento en esa fila).

ＦΣＥθＬι«

Bucle para cada elemento en la matriz. Esto debería ser bucles más que suficientes para hacer el trabajo, ya que también incluyo todos los nans adicionales .

ＦＬθ«≔§θκι

Pase por encima de cada índice de fila y obtenga la fila en ese índice. (El carbón puede hacer ambas cosas con una expresión pero no con un comando). Esto incluye la fila ficticia, pero eso no es un problema porque todas las comparaciones fallarán.

ＦＬι«≔§ιλζ

Recorra cada índice de columna y obtenga el valor en ese índice. Nuevamente, esto repetirá los valores ficticios, pero las comparaciones simplemente fallarán nuevamente.

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

También obtenga los valores a la derecha y a continuación.

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

Si la celda es mayor que el valor de abajo y no es cierto que el valor de abajo es mayor que el valor de la derecha, entonces intercambie la celda con el valor de abajo.

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

De lo contrario, si la celda es mayor que el valor de la derecha, cámbielos.

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

Elimine los nanvalores y formatee la matriz para la salida implícita.

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

Pruébalo en línea!