Le tri n'a aucun sens pour un tableau à deux dimensions ... ou pas?

Votre tâche consiste à prendre une grille d'entrée et à lui appliquer un algorithme de type bulle jusqu'à ce que toutes les valeurs de la grille ne diminuent pas de gauche à droite et de haut en bas le long de chaque ligne et colonne.

L'algorithme fonctionne comme suit:

• Chaque passe va ligne par ligne, de haut en bas, en comparant / échangeant chaque cellule avec ses voisins droit et inférieur.
  • si la cellule est supérieure à un seul de ses voisins droit et inférieur, échangez avec celle dont elle est supérieure à
  • si la cellule est supérieure à ses voisins droit et inférieur, échangez avec le voisin plus petit
  • si la cellule est supérieure à ses voisins droit et inférieur, qui sont de la même valeur, échangez avec le voisin inférieur.
  • si la cellule n'est pas plus grande que ses voisins droit et inférieur, ne faites rien
• Continuez jusqu'à ce qu'aucun échange ne soit effectué tout au long du passage. Ce sera lorsque chaque ligne et colonne sera dans l'ordre, de gauche à droite et de haut en bas.

Exemple

4 2 1
3 3 5
7 2 1

La première rangée de la passe permutera le 4 et le 2, puis le 4 avec le 1.

2 1 4
3 3 5
7 2 1

Lorsque nous aurons le 3 du milieu, il sera échangé avec le 2 ci-dessous

2 1 4
3 2 5
7 3 1

Ensuite, le 5 est échangé avec le 1 ci-dessous

2 1 4
3 2 1
7 3 5

La dernière rangée de la première passe déplace le 7 complètement à droite

2 1 4
3 2 1
3 5 7

Ensuite, nous revenons à la rangée du haut

1 2 1
3 2 4
3 5 7

Et continuez ligne par ligne ...

1 2 1
2 3 4
3 5 7

... jusqu'à ce que la grille soit "triée"

1 1 2
2 3 4
3 5 7

Un autre exemple

3 1 1
1 1 1
1 8 9

devient

1 1 1
1 1 1
3 8 9

plutôt que

1 1 1
1 1 3
1 8 9

car l'échange vers le bas est prioritaire lorsque les voisins droit et inférieur d'une cellule sont égaux.

Une implémentation de référence étape par étape peut être trouvée ici .

Cas de test

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

devient

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

devient

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

Règles

• Vous pouvez prendre la grille d'entrée dans n'importe quel format pratique
• Vous pouvez supposer que les valeurs de la grille sont toutes des entiers non négatifs dans la plage de 16 bits non signée (0-65535).
• Vous pouvez supposer que la grille est un rectangle parfait et non un tableau dentelé. La grille sera au moins 2x2.
• Si vous utilisez un autre algorithme de tri, vous devez fournir une preuve qu'il produira toujours le même ordre résultant que cette marque particulière de tri à bulles 2D, quelle que soit l'entrée. Je m'attends à ce que ce soit une preuve non triviale, donc vous feriez probablement mieux d'utiliser l'algorithme décrit.

Bon golf!

JavaScript (Node.js) , 129 octets

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

Essayez-le en ligne!

APL (Dyalog Unicode) , 75 octets ^SBCS

Merci à @ Adám pour avoir économisé 11 octets.

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

Essayez-le en ligne!

Langue Wolfram (Mathematica) , 183 octets

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

Essayez-le en ligne!

Je ne suis pas un expert de Mathematica, je suis sûr que cela peut être fait plus rapidement. En particulier, je pense que la double déclaration if pourrait être raccourcie en utilisant Transposemais je ne sais pas comment.

R , 169 165 144 132 132 octets

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

Essayez-le en ligne!

Propre , 240 octets

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

Essayez-le en ligne!

Implémente l'algorithme exactement comme décrit.

Le lien inclut l'analyse syntaxique d'entrée pour prendre le format dans la question.

Python 2 , 215 208 octets

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

Essayez-le en ligne!

_{-7 octets, grâce aux ovs}

C # (.NET Core) , 310 octets

Sans LINQ. Utilise System.Collections.Generic uniquement pour formater la sortie après le retour de la fonction. La chose est stupide énorme. Au plaisir des 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;}

Essayez-le en ligne!

Python 2 , 198 octets

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

Essayez-le en ligne!

Développé indépendamment de la réponse de TFeld, présente quelques différences.

Fusain , 118 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. J'ai également passé quelques octets sur un formatage plus joli. Explication:

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

JavaScript a la propriété pratique qui a[i]>a[i+1]est false si iest le dernier élément du tableau. Pour imiter cela dans le charbon de bois, je calcule unnan en lançant 9.e999pour flotter puis en le soustrayant de lui-même. (Charcoal ne prend pas en charge les constantes flottantes exponentielles.) Je remplis ensuite le tableau d'origine à droite avec le nanet ajoute également une ligne supplémentaire contenant uniquement le nan. (L'indexation cyclique du charbon de bois signifie que je n'ai besoin que d'un élément dans cette ligne.)

ＦΣＥθＬι«

Boucle pour chaque élément du tableau. Cela devrait être plus que suffisant de boucles pour faire le travail, car j'inclus également tous les extras nan.

ＦＬθ«≔§θκι

Faites une boucle sur chaque index de ligne et obtenez la ligne à cet index. (Charcoal peut faire les deux avec une expression mais pas avec une commande.) Cela inclut la ligne fictive mais ce n'est pas un problème car toutes les comparaisons échoueront.

ＦＬι«≔§ιλζ

Faites une boucle sur chaque index de colonne et obtenez la valeur à cet index. Encore une fois, cela bouclera sur les valeurs fictives mais les comparaisons échoueront à nouveau.

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

Obtenez également les valeurs à droite et en dessous.

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

Si la cellule est supérieure à la valeur ci-dessous et qu'il n'est pas vrai que la valeur ci-dessous soit supérieure à la valeur à droite, échangez la cellule avec la valeur ci-dessous.

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

Sinon, si la cellule est supérieure à la valeur de droite, échangez-les.

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

Supprimez les nanvaleurs et formatez le tableau pour une sortie implicite.

Kotlin , 325 octets

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

Essayez-le en ligne!