Sortieren macht für ein zweidimensionales Array keinen Sinn ... oder doch?

Ihre Aufgabe ist es, ein Eingabegitter zu nehmen und einen Algorithmus anzuwenden, der einer Blasensortierung ähnelt, bis alle Werte im Gitter in jeder Zeile und Spalte nicht mehr von links nach rechts und von oben nach unten abnehmen.

Der Algorithmus funktioniert wie folgt:

• Jeder Durchgang erfolgt zeilenweise von oben nach unten, wobei jede Zelle mit ihren rechten und unteren Nachbarn verglichen / ausgetauscht wird.
  • Ist die Zelle größer als nur eine ihrer rechten und unteren Nachbarn, tauschen Sie sie gegen diejenige aus, die größer als ist
  • Ist die Zelle größer als die rechte und die untere Nachbarzelle, tauschen Sie sie mit dem kleineren Nachbarn aus
  • Wenn die Zelle größer ist als ihre rechten und unteren Nachbarn, die den gleichen Wert haben, tauschen Sie sie mit dem unteren Nachbarn aus.
  • Wenn die Zelle nicht größer als eine der rechten und unteren Nachbarn ist, nichts tun
• Fahren Sie so lange fort, bis während des gesamten Passes keine Auslagerungen mehr vorgenommen werden. Dies ist der Fall, wenn alle Zeilen und Spalten von links nach rechts und von oben nach unten angeordnet sind.

Beispiel

4 2 1
3 3 5
7 2 1

Die erste Reihe des Passes wird die 4 und die 2, dann die 4 mit der 1 tauschen.

2 1 4
3 3 5
7 2 1

Wenn wir die mittlere 3 bekommen, wird sie mit der 2 unten getauscht

2 1 4
3 2 5
7 3 1

Dann werden die 5 mit der 1 getauscht

2 1 4
3 2 1
7 3 5

Die letzte Reihe des ersten Durchgangs bewegt die 7 ganz nach rechts

2 1 4
3 2 1
3 5 7

Dann kehren wir wieder in die oberste Reihe zurück

1 2 1
3 2 4
3 5 7

Und weiter Zeile für Zeile ...

1 2 1
2 3 4
3 5 7

... bis das Raster "sortiert" ist

1 1 2
2 3 4
3 5 7

Ein anderes Beispiel

3 1 1
1 1 1
1 8 9

wird

1 1 1
1 1 1
3 8 9

eher, als

1 1 1
1 1 3
1 8 9

weil der Downward-Swap Vorrang hat, wenn sowohl der rechte als auch der untere Nachbar einer Zelle gleich sind.

Eine schrittweise Referenzimplementierung finden Sie hier .

Testfälle

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

wird

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

wird

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

Regeln

• Sie können das Eingaberaster in einem beliebigen Format verwenden
• Sie können davon ausgehen, dass die Rasterwerte alle nicht negative ganze Zahlen im vorzeichenlosen 16-Bit-Bereich (0-65535) sind.
• Sie können annehmen, dass das Raster ein perfektes Rechteck und kein gezacktes Array ist. Das Gitter wird mindestens 2x2 sein.
• Wenn Sie einen anderen Sortieralgorithmus verwenden, müssen Sie einen Beweis dafür liefern, dass immer die gleiche resultierende Reihenfolge wie bei dieser speziellen Marke der 2D-Blasensortierung erzielt wird, unabhängig von der Eingabe. Ich gehe davon aus, dass dies ein nicht trivialer Beweis ist. Daher ist es wahrscheinlich besser, den beschriebenen Algorithmus zu verwenden.

Viel Spaß beim Golfen!

JavaScript (Node.js) , 129 Byte

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

Probieren Sie es online!

APL (Dyalog Unicode) , 75 Byte ^SBCS

Vielen Dank an @ Adám für das Speichern von 11 Bytes.

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

Probieren Sie es 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)&

Probieren Sie es online!

Ich bin kein Mathematica-Experte, ich bin mir sicher, dass es auch kürzer geht. Insbesondere denke ich, dass die double if-Anweisung mit Hilfe von verkürzt werden könnte, Transposeaber ich weiß nicht wie.

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

Probieren Sie es online!

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

Probieren Sie es online!

Implementiert den Algorithmus genau wie beschrieben.

Der Link enthält eine Eingabe-Analyse, um das Format in der Frage zu übernehmen.

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

Probieren Sie es online!

_{-7 Bytes dank ovs}

C # (.NET Core) , 310 Byte

Ohne LINQ. Verwendet System.Collections.Generic nur zum Formatieren der Ausgabe, nachdem die Funktion zurückgegeben wurde. Die Sache ist riesig dumm. Ich freue mich auf die Golfplätze!

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

Probieren Sie es 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

Probieren Sie es online!

Unabhängig von TFelds Antwort entwickelt, weist einige Unterschiede auf.

Kohle , 118 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Ich habe auch ein paar Bytes für eine schönere Formatierung ausgegeben. Erläuterung:

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

JavaScript hat die praktische Eigenschaft, a[i]>a[i+1]die false ist, wenn ies das letzte Element des Arrays ist. Um das in Charcoal zu emulieren, berechne ich a, nanindem ich 9.e999auf Floating wirke und es dann von sich selbst subtrahiere. (Charcoal unterstützt keine exponentiellen Gleitkommakonstanten.) Dann nanfüge ich das ursprüngliche Array auf der rechten Seite mit dem hinzu und füge eine zusätzliche Zeile hinzu, die nur das enthält nan. (Die zyklische Indizierung von Charcoal bedeutet, dass ich nur ein Element in dieser Zeile benötige.)

ＦΣＥθＬι«

Schleife für jedes Element im Array. Dies sollte mehr als genug Schleifen sein, um die Arbeit zu erledigen, da ich auch all die Extras mit naneinbeziehe.

ＦＬθ«≔§θκι

Durchlaufen Sie jeden Zeilenindex und rufen Sie die Zeile an diesem Index ab. (Charcoal kann beides mit einem Ausdruck, aber nicht mit einem Befehl tun.) Dies schließt die Dummy-Zeile ein, aber das ist kein Problem, da alle Vergleiche fehlschlagen.

ＦＬι«≔§ιλζ

Durchlaufen Sie jeden Spaltenindex und ermitteln Sie den Wert an diesem Index. Auch hier werden die Dummy-Werte durchlaufen, aber die Vergleiche schlagen erneut fehl.

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

Holen Sie sich auch die Werte rechts und unten.

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

Wenn die Zelle größer als der untere Wert ist und der untere Wert nicht größer als der rechte Wert ist, tauschen Sie die Zelle gegen den unteren Wert aus.

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

Andernfalls, wenn die Zelle größer als der Wert rechts ist, tauschen Sie sie aus.

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

Entfernen Sie die nanWerte und formatieren Sie das Array für die implizite Ausgabe.

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

Probieren Sie es online!