Sortowanie nie ma sensu w przypadku dwuwymiarowej tablicy ... czy to prawda?

Twoim zadaniem jest wziąć siatkę wejściową i zastosować do niej algorytm sortowania bąbelkowego, aż wszystkie wartości w siatce nie będą się zmniejszały od lewej do prawej i od góry do dołu wzdłuż każdego wiersza i kolumny.

Algorytm działa w następujący sposób:

• Każde przejście przechodzi rząd po rzędzie, od góry do dołu, porównując / zamieniając każdą komórkę z jej prawym i poniżej sąsiadów.
  • jeśli komórka jest większa niż tylko jedna z jej prawej i poniżej sąsiadów, zamień na komórkę, która jest większa niż
  • jeśli komórka jest większa niż jej prawa i poniżej sąsiadów, zamień na mniejszego sąsiada
  • jeśli komórka jest większa niż jej prawa i dolna część sąsiadów, które mają tę samą wartość, zamień z dolnym sąsiadem.
  • jeśli komórka nie jest większa niż którykolwiek z jej prawych i znajdujących się poniżej sąsiadów, nie rób nic
• Kontynuuj to, dopóki nie zostaną wykonane żadne zamiany podczas całego przejścia. Nastąpi to, gdy każdy wiersz i kolumna będą w porządku, od lewej do prawej i od góry do dołu.

Przykład

4 2 1
3 3 5
7 2 1

Pierwszy rząd przepustki zamieni 4 i 2, a następnie 4 z 1.

2 1 4
3 3 5
7 2 1

Kiedy otrzymamy środkową 3, zostanie ona zamieniona na 2 poniżej

2 1 4
3 2 5
7 3 1

Następnie 5 zostaje zamienionych na 1 poniżej

2 1 4
3 2 1
7 3 5

Ostatni rząd pierwszego przejścia przesuwa 7 do końca w prawo

2 1 4
3 2 1
3 5 7

Następnie wracamy do górnego rzędu

1 2 1
3 2 4
3 5 7

I kontynuuj rząd po rzędzie ...

1 2 1
2 3 4
3 5 7

... dopóki siatka nie zostanie „posortowana”

1 1 2
2 3 4
3 5 7

Inny przykład

3 1 1
1 1 1
1 8 9

staje się

1 1 1
1 1 1
3 8 9

zamiast

1 1 1
1 1 3
1 8 9

ponieważ zamiana w dół ma pierwszeństwo, gdy zarówno prawa, jak i niższa sąsiada komórki są równe.

Implementację referencji krok po kroku można znaleźć tutaj .

Przypadki testowe

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

staje się

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

staje się

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

Zasady

• Możesz wziąć siatkę wejściową w dowolnym dogodnym formacie
• Możesz założyć, że wszystkie wartości liczbowe są liczbami całkowitymi nieujemnymi w 16-bitowym zakresie bez znaku (0–65535).
• Możesz założyć, że siatka jest idealnym prostokątem, a nie poszarpaną tablicą. Siatka będzie wynosić co najmniej 2x2.
• Jeśli użyjesz innego algorytmu sortowania, musisz dostarczyć dowód, że zawsze będzie generował to samo zamówienie wynikowe, jak ta konkretna marka sortowania bąbelkowego 2D, bez względu na to, co jest wprowadzane. Spodziewam się, że będzie to nietrywialny dowód, więc prawdopodobnie lepiej będzie użyć opisanego algorytmu.

Wesołego golfa!

JavaScript (Node.js) , 129 bajtów

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

Wypróbuj online!

APL (Dyalog Unicode) , 75 bajtów ^SBCS

Dzięki @ Adám za zapisanie 11 bajtów.

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

Wypróbuj online!

Wolfram Language (Mathematica) , 183 bajty

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

Wypróbuj online!

Nie jestem ekspertem od matematyki, jestem pewien, że można to zrobić krócej. Szczególnie uważam, że podwójne wyrażenie if można skrócić, Transposeale nie wiem jak.

R , 169 165 144 132 bajtów

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

Wypróbuj online!

Czysty , 240 bajtów

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

Wypróbuj online!

Implementuje algorytm dokładnie tak, jak opisano.

Link zawiera parsowanie danych wejściowych w celu pobrania formatu z pytania.

Python 2 , 215 208 bajtów

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

Wypróbuj online!

_{-7 bajtów, dzięki ovs}

C # (.NET Core) , 310 bajtów

Bez LINQ. Wykorzystuje System.Collections.Generic tylko do formatowania danych wyjściowych po zwróceniu funkcji. To jest głupie ogromne. Czekamy na golfa!

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

Wypróbuj online!

Python 2 , 198 bajtów

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

Wypróbuj online!

Opracowany niezależnie od odpowiedzi TFeld, ma pewne różnice.

Węgiel drzewny , 118 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wydałem też kilka bajtów na ładniejsze formatowanie. Wyjaśnienie:

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

JavaScript ma wygodną właściwość, która a[i]>a[i+1]jest fałszem, jeśli ijest ostatnim elementem tablicy. Aby naśladować to w Charcoal, obliczam nan, rzucając, 9.e999by unosić się, a następnie odejmując go od siebie. (Węgiel drzewny nie obsługuje wykładniczych stałych zmiennoprzecinkowych.) Następnie nanuzupełniam pierwotną tablicę po prawej stronie za pomocą, a także dodaję dodatkowy wiersz zawierający tylko nan. (Cykliczne indeksowanie węgla drzewnego oznacza, że ​​potrzebuję tylko jednego elementu w tym wierszu).

ＦΣＥθＬι«

Pętla dla każdego elementu w tablicy. To powinno być więcej niż wystarczająca liczba pętli, aby wykonać zadanie, ponieważ uwzględniam także wszystkie dodatkowe nans.

ＦＬθ«≔§θκι

Zapętlaj indeks każdego wiersza i uzyskaj wiersz o tym indeksie. (Węgiel drzewny może robić zarówno z wyrażeniem, ale nie z poleceniem.) Obejmuje to atrapę, ale nie stanowi to problemu, ponieważ wszystkie porównania zakończą się niepowodzeniem.

ＦＬι«≔§ιλζ

Pętla nad indeksem każdej kolumny i uzyskaj wartość tego indeksu. Ponownie spowoduje to zapętlenie wartości manekina, ale porównania znów się nie powiodą.

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

Uzyskaj także wartości po prawej i poniżej.

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

Jeśli komórka jest większa niż wartość poniżej i nie jest prawdą, że wartość poniżej jest większa niż wartość po prawej, zamień komórkę na wartość poniżej.

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

W przeciwnym razie, jeśli komórka jest większa niż wartość po prawej, zamień je.

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

Usuń nanwartości i sformatuj tablicę pod kątem niejawnego wyniku.

Kotlin , 325 bajtów

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

Wypróbuj online!