A classificação não faz sentido para uma matriz bidimensional ... ou faz?

Sua tarefa é pegar uma grade de entrada e aplicar um algoritmo do tipo bolha até que todos os valores na grade não diminuam da esquerda para a direita e de cima para baixo ao longo de cada linha e coluna.

O algoritmo funciona da seguinte maneira:

• Cada passagem vai linha por linha, de cima para baixo, comparando / trocando cada célula com seus vizinhos direito e abaixo.
  • se a célula for maior que apenas uma de suas vizinhas direita e abaixo, troque pela célula que é maior que
  • se a célula for maior que seus vizinhos direito e abaixo, troque com o vizinho menor
  • se a célula for maior que seus vizinhos direito e abaixo, que têm o mesmo valor, troque com o vizinho abaixo.
  • se a célula não for maior que qualquer um dos seus vizinhos direitos e abaixo, não faça nada
• Continue até que nenhuma troca seja feita durante todo o passe. Será quando todas as linhas e colunas estiverem em ordem, da esquerda para a direita e de cima para baixo.

Exemplo

4 2 1
3 3 5
7 2 1

A primeira linha do passe trocará o 4 e o 2, depois o 4 pelo 1.

2 1 4
3 3 5
7 2 1

Quando chegarmos ao meio 3, ele será trocado pelo 2 abaixo

2 1 4
3 2 5
7 3 1

Em seguida, o 5 é trocado pelo 1 abaixo

2 1 4
3 2 1
7 3 5

A última linha da primeira passagem move os 7 para a direita

2 1 4
3 2 1
3 5 7

Então voltamos à linha superior novamente

1 2 1
3 2 4
3 5 7

E continue linha por linha ...

1 2 1
2 3 4
3 5 7

... até que a grade seja "classificada"

1 1 2
2 3 4
3 5 7

Outro exemplo

3 1 1
1 1 1
1 8 9

torna-se

1 1 1
1 1 1
3 8 9

ao invés de

1 1 1
1 1 3
1 8 9

porque a troca descendente tem prioridade quando os vizinhos direito e abaixo de uma célula são iguais.

Uma implementação de referência passo a passo pode ser encontrada aqui .

Casos de teste

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

torna-se

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

torna-se

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

Regras

• Você pode pegar a grade de entrada em qualquer formato conveniente
• Você pode assumir que os valores da grade são todos números inteiros não negativos no intervalo de 16 bits não assinado (0-65535).
• Você pode assumir que a grade é um retângulo perfeito e não uma matriz irregular. A grade será pelo menos 2x2.
• Se você usar outro algoritmo de classificação, deverá fornecer uma prova de que ele sempre produzirá a mesma ordem resultante que essa marca específica de classificação de bolhas 2D, independentemente da entrada. Eu espero que isso seja uma prova não trivial, então você provavelmente está melhor usando o algoritmo descrito.

Golfe feliz!

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

Experimente online!

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

Obrigado a @ Adám por salvar 11 bytes.

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

Experimente online!

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

Experimente online!

Não sou especialista em Mathematica, tenho certeza que isso pode ser feito mais curto. Particularmente, acho que a declaração if dupla poderia ser reduzida usando, Transposemas não sei como.

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

Experimente online!

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

Experimente online!

Implementa o algoritmo exatamente como descrito.

O link inclui a análise de entrada para obter o formato na pergunta.

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

Experimente online!

_{-7 bytes, graças a ovs}

C # (.NET Core) , 310 bytes

Sem LINQ. Usa usando System.Collections.Generic apenas para formatar a saída após o retorno da função. A coisa é enorme e estúpida. Ansioso para os golfe!

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

Experimente online!

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

Experimente online!

Desenvolvido independentemente da resposta do TFeld, tem algumas diferenças.

Carvão , 118 bytes

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

Experimente online! Link é a versão detalhada do código. Também gastei alguns bytes em uma formatação mais bonita. Explicação:

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

O JavaScript tem a propriedade conveniente que a[i]>a[i+1]é falsa se ifor o último elemento da matriz. Para imitar isso em Charcoal, calculo um nanlançando 9.e999para flutuar e subtraindo-o de si mesmo. (O carvão vegetal não suporta constantes de flutuação exponencial.) Em seguida, preencho a matriz original à direita com o nane também adiciono uma linha adicional contendo apenas o nan. (A indexação cíclica do carvão vegetal significa que eu só preciso de um elemento nessa linha.)

ＦΣＥθＬι«

Loop para cada elemento na matriz. Isso deve ser loops mais do que suficientes para fazer o trabalho, pois também estou incluindo todos os nans extras .

ＦＬθ«≔§θκι

Faça um loop sobre cada índice de linha e obtenha a linha nesse índice. (O carvão vegetal pode fazer as duas coisas com uma expressão, mas não com um comando.) Isso inclui a linha fictícia, mas isso não é um problema, porque todas as comparações falharão.

ＦＬι«≔§ιλζ

Faça um loop sobre o índice de cada coluna e obtenha o valor nesse índice. Novamente, isso fará um loop sobre os valores fictícios, mas as comparações falharão novamente.

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

Obtenha também os valores à direita e abaixo.

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

Se a célula for maior que o valor abaixo e não for verdade que o valor abaixo é maior que o valor à direita, troque a célula pelo valor abaixo.

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

Caso contrário, se a célula for maior que o valor à direita, troque-os.

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

Remova os nanvalores e formate a matriz para saída 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)}

Experimente online!