Penyortiran tidak masuk akal untuk array 2 dimensi ... atau bukan?

Tugas Anda adalah mengambil kisi masukan dan menerapkan algoritme seperti gelembung hingga semua nilai di kisi tidak berkurang dari kiri ke kanan dan atas ke bawah di sepanjang setiap baris dan kolom.

Algoritma bekerja sebagai berikut:

• Setiap pass berjalan baris demi baris, atas ke bawah, membandingkan / menukar setiap sel dengan tetangga kanan dan bawahnya.
  • jika sel lebih besar dari hanya satu di kanan dan di bawah tetangga, bertukar dengan yang lebih besar dari
  • jika sel lebih besar dari tetangga kanan dan bawahnya, bertukar dengan tetangga yang lebih kecil
  • jika sel lebih besar dari tetangga kanan dan bawahnya, yang nilainya sama, maka tukar dengan tetangganya di bawah.
  • jika sel tidak lebih besar dari kanan dan tetangganya di bawah, jangan lakukan apa pun
• Lanjutkan ini sampai tidak ada swap yang dilakukan di seluruh pass. Ini akan terjadi ketika setiap baris dan kolom dalam urutan, kiri ke kanan dan atas ke bawah.

Contoh

4 2 1
3 3 5
7 2 1

Baris pertama pass akan menukar 4 dan 2, lalu 4 dengan 1.

2 1 4
3 3 5
7 2 1

Ketika kita mendapatkan 3 tengah, itu akan ditukar dengan 2 di bawah ini

2 1 4
3 2 5
7 3 1

Kemudian 5 akan ditukar dengan 1 di bawah ini

2 1 4
3 2 1
7 3 5

Baris terakhir dari lintasan pertama menggerakkan 7 hingga ke kanan

2 1 4
3 2 1
3 5 7

Kemudian kita kembali ke baris paling atas lagi

1 2 1
3 2 4
3 5 7

Dan lanjutkan baris demi baris ...

1 2 1
2 3 4
3 5 7

... sampai kisi "diurutkan"

1 1 2
2 3 4
3 5 7

Contoh lain

3 1 1
1 1 1
1 8 9

menjadi

1 1 1
1 1 1
3 8 9

daripada

1 1 1
1 1 3
1 8 9

karena swap ke bawah mengambil prioritas ketika kedua tetangga sel di bawah dan kanan sama.

Implementasi referensi langkah demi langkah dapat ditemukan di sini .

Uji kasus

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

menjadi

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

menjadi

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

Aturan

• Anda dapat mengambil kisi input dalam format apa pun yang nyaman
• Anda dapat mengasumsikan nilai kisi-kisi adalah semua bilangan bulat non-negatif dalam kisaran 16-bit yang tidak ditandatangani (0-65535).
• Anda dapat mengasumsikan kisi-kisi adalah persegi panjang yang sempurna dan bukan array bergerigi. Kotak akan setidaknya 2x2.
• Jika Anda menggunakan algoritme penyortiran lain, Anda harus memberikan bukti bahwa penyortiran akan selalu menghasilkan urutan yang sama dengan merek penyortiran gelembung 2D ini, apa pun inputnya. Saya berharap ini menjadi bukti non-sepele, jadi Anda mungkin lebih baik menggunakan algoritma yang dijelaskan.

Selamat Golf!

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

Cobalah online!

APL (Dyalog Unicode) , 75 byte ^SBCS

Terima kasih kepada @ Adám karena telah menghemat 11 byte.

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

Cobalah online!

Bahasa Wolfram (Mathematica) , 183 byte

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

Cobalah online!

Saya bukan ahli Mathematica, saya yakin itu bisa dilakukan lebih pendek. Khususnya saya berpikir bahwa pernyataan ganda jika bisa disingkat menggunakan Transposetapi saya tidak tahu caranya.

R , 169 165 144 132 byte

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

Cobalah online!

Bersihkan , 240 byte

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

Cobalah online!

Menerapkan algoritma persis seperti yang dijelaskan.

Tautan termasuk penguraian input untuk mengambil format dalam pertanyaan.

Python 2 , 215 208 byte

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

Cobalah online!

_{-7 byte, terima kasih atas ovs}

C # (.NET Core) , 310 byte

Tanpa LINQ. Penggunaan menggunakan System.Collections.Generic hanya untuk memformat output setelah fungsi dikembalikan. Hal itu sangat besar. Menantikan 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;}

Cobalah online!

Python 2 , 198 byte

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

Cobalah online!

Dikembangkan secara independen dari jawaban TFeld, memiliki beberapa perbedaan.

Arang , 118 byte

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

Cobalah online!Tautan adalah untuk mengucapkan versi kode. Saya juga menghabiskan beberapa byte pada beberapa format yang lebih cantik. Penjelasan:

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

JavaScript memiliki properti praktis yang a[i]>a[i+1]salah jika imerupakan elemen terakhir dari array. Untuk menirunya dalam Charcoal, saya menghitung a nandengan casting 9.e999ke float dan kemudian mengurangkannya dari dirinya sendiri. (Arang tidak mendukung konstanta float eksponensial.) Saya kemudian pad array asli di sebelah kanan dengan nandan juga menambahkan baris tambahan yang hanya berisinan . (Pengindeksan siklik Charcoal berarti saya hanya perlu satu elemen di baris itu.)

ＦΣＥθＬι«

Loop untuk setiap elemen dalam array. Ini harus lebih dari cukup loop untuk menyelesaikan pekerjaan, karena saya termasuk semua tambahan nanjuga.

ＦＬθ«≔§θκι

Ulangi setiap indeks baris dan dapatkan baris pada indeks itu. (Arang dapat melakukan keduanya dengan ekspresi tetapi tidak dengan perintah.) Ini termasuk baris dummy tapi itu tidak masalah karena semua perbandingan akan gagal.

ＦＬι«≔§ιλζ

Ulangi setiap indeks kolom dan dapatkan nilainya di indeks itu. Sekali lagi, ini akan mengulangi nilai-nilai dummy tetapi perbandingan hanya akan gagal lagi.

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

Juga dapatkan nilainya ke kanan dan di bawah.

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

Jika sel lebih besar dari nilai di bawah dan tidak benar bahwa nilai di bawah lebih besar dari nilai di sebelah kanan, maka tukarkan sel dengan nilai di bawah.

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

Kalau tidak, jika sel lebih besar dari nilai di sebelah kanan maka swap mereka.

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

Hapus nannilai - nilai dan format array untuk output implisit.

Kotlin , 325 byte

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

Cobalah online!