Сортировка не имеет смысла для двумерного массива ... или нет?

Ваша задача - взять входную сетку и применить к ней алгоритм, подобный пузырьковой сортировке, пока все значения в сетке не будут уменьшаться слева направо и сверху вниз по каждой строке и столбцу.

Алгоритм работает следующим образом:

• Каждый проход идет строка за строкой сверху вниз, сравнивая / меняя каждую ячейку с ее правыми и нижними соседями.
  • если ячейка больше, чем только один из ее правых и нижних соседей, поменяйте местами с той, что больше
  • если ячейка больше, чем ее правые и нижние соседи, поменяйте местами с меньшим соседом
  • если ячейка больше, чем ее правые и нижние соседи, которые имеют одинаковое значение, то поменяйте местами с нижним соседом.
  • если ячейка не больше, чем любой из ее правых и ниже соседей, ничего не делать
• Продолжайте до тех пор, пока на протяжении всего прохода не будет выполнено никаких перестановок. Это будет, когда все строки и столбцы расположены по порядку, слева направо и сверху вниз.

пример

4 2 1
3 3 5
7 2 1

Первый ряд прохода поменяет 4 и 2, затем 4 с 1.

2 1 4
3 3 5
7 2 1

Когда мы получим середину 3, она поменяется местами с 2 ниже

2 1 4
3 2 5
7 3 1

Затем 5 меняется местами с 1 ниже

2 1 4
3 2 1
7 3 5

Последний ряд первого прохода перемещает 7 полностью вправо

2 1 4
3 2 1
3 5 7

Затем мы снова возвращаемся в верхний ряд

1 2 1
3 2 4
3 5 7

И продолжайте построчно ...

1 2 1
2 3 4
3 5 7

... пока сетка не "отсортирована"

1 1 2
2 3 4
3 5 7

Другой пример

3 1 1
1 1 1
1 8 9

становится

1 1 1
1 1 1
3 8 9

скорее, чем

1 1 1
1 1 3
1 8 9

потому что нисходящий своп имеет приоритет, когда и правые, и нижние соседи ячейки равны.

Пошаговую справочную реализацию можно найти здесь .

Контрольные примеры

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

становится

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

становится

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

правила

• Вы можете взять входную сетку в любом удобном формате
• Можно предположить, что все значения сетки представляют собой неотрицательные целые числа в 16-разрядном диапазоне без знака (0-65535).
• Вы можете предположить, что сетка представляет собой идеальный прямоугольник, а не зубчатый массив. Сетка будет не менее 2х2.
• Если вы используете другой алгоритм сортировки, вы должны предоставить доказательство того, что он всегда будет производить тот же результирующий порядок, что и конкретный бренд двумерной пузырьковой сортировки, независимо от того, какой будет ввод. Я ожидаю, что это будет нетривиальным доказательством, поэтому вам лучше использовать описанный алгоритм.

Счастливого гольфа!

JavaScript (Node.js) , 129 байт

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

Попробуйте онлайн!

APL (Dyalog Unicode) , 75 байтов ^SBCS

Спасибо @ Adám за сохранение 11 байтов.

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 183 байта

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

Попробуйте онлайн!

Я не эксперт по Mathematica, я уверен, что это можно сделать короче. В частности, я думаю, что двойное выражение if можно сократить с помощью, Transposeно я не знаю как.

R , 169 165 144 132 байт

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

Попробуйте онлайн!

Чистый , 240 байт

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

Попробуйте онлайн!

Реализует алгоритм точно так, как описано.

Ссылка включает в себя синтаксический анализ ввода, чтобы принять формат в вопросе.

Python 2 , 215 208 байт

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

Попробуйте онлайн!

_{-7 байт, благодаря овсу}

C # (.NET Core) , 310 байт

Без LINQ. Использует System.Collections.Generic только для форматирования вывода после возврата функции. Вещь глупо огромна. Ждем в гольф!

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

Попробуйте онлайн!

Python 2 , 198 байт

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

Попробуйте онлайн!

Разработан независимо от ответа TFeld, имеет некоторые отличия.

Древесный уголь , 118 байт

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

Попробуйте онлайн! Ссылка на подробную версию кода. Я также потратил несколько байтов на более красивое форматирование. Объяснение:

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

JavaScript имеет удобное свойство a[i]>a[i+1]false, если iэто последний элемент массива. Чтобы подражать этому в Charcoal, я вычисляю a nan, бросая, 9.e999чтобы плавать и затем вычитая это из себя. (Древесный уголь не поддерживает экспоненциальные константы с плавающей точкой.) Затем я nanдобавляю исходный массив справа и также добавляю дополнительную строку, содержащую только nan. (Циклическая индексация угля означает, что мне нужен только один элемент в этой строке.)

ＦΣＥθＬι«

Цикл для каждого элемента в массиве. Это должно быть более чем достаточно циклов, чтобы выполнить работу, так как я включаю все дополнительные nanS тоже.

ＦＬθ«≔§θκι

Цикл по каждому индексу строки и получить строку по этому индексу. (Древесный уголь может быть как с выражением, но не с командой.) Это включает в себя пустую строку, но это не проблема, потому что все сравнения не удастся.

ＦＬι«≔§ιλζ

Цикл по каждому индексу столбца и получить значение по этому индексу. Опять же, это зациклится на фиктивных значениях, но сравнение снова не удастся.

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

Также получите значения справа и снизу.

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

Если ячейка больше значения, указанного ниже, и неверно, что значение ниже больше значения справа, то поменяйте местами ячейку со значением ниже.

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

В противном случае, если ячейка больше значения справа, поменяйте их местами.

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

Удалите nanзначения и отформатируйте массив для неявного вывода.

Котлин , 325 байт

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

Попробуйте онлайн!