Вызов

Дайте список целых чисел, покажите, как будет выполняться гравитационная сортировка.

Гравитационная сортировка

В гравитационном виде представьте числа в виде звездочек. Затем все падает, и новые строки будут явно отсортированы. Давайте посмотрим на пример:

[2, 7, 4, 6]:

**
*******
****
******
-------
**
****
*******
******
-------
**      | 2
****    | 4
******  | 6
******* | 7

Обратите внимание, что это в значительной степени просто параллельная пузырьковая сортировка.

Точные характеристики

На каждой итерации, начиная с верхней строки, возьмите каждую звездочку из строки, у которой под ней нет звездочки, и переместите ее вниз на строку. Продолжайте делать это, пока список не отсортирован.

вход

На входе будет список строго положительных чисел.

Выход

Для вывода вы должны вывести каждый шаг. Вы можете выбрать любые два непечатаемых печатных символа ASCII, один из которых будет «звездочкой», а другой - разделителем «тире». Ряды звездочек должны быть разделены стандартной новой строкой (например, \nили \r\f). Ряд черточек должен быть не меньше ширины самого широкого ряда (иначе ваши звездочки могут упасть слишком далеко вниз!). Ряд черточек в самом низу необязателен. Завершающий перевод строки в конце разрешен. Пробелы на каждой строке разрешены.

Тестовые случаи

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

[4, 3, 2, 1]
****
***
**
*
----
***
** *
* *
**
----
**
* *
** *
***
----
*
**
***
****

[6, 4, 2, 5, 3, 1]
******
****
**
*****
***
*
------
****
**  **
****
***
*  **
***
------
**
****
*** **
*  *
***
*****
------
**
***
*  *
*** **
****
*****
------
**
*
***
****
******
*****
------
*
**
***
****
*****
******

[8, 4, 2, 1]
********
****
**
*
--------
****
**  ****
* **
**
--------
**
* **
**  ****
****
--------
*
**
****
********

Пожалуйста, не стесняйтесь исправлять мои тесты, если они ошибочны, я сделал их вручную :)

Примечание. Не выводите отсортированный список в конце. :)

счет

Все ваши программы будут написаны друг на друге. Вы не хотели бы, чтобы части вашей программы рухнули, поэтому убедитесь, что у вас самый короткий код!

Pyth , 27 байт

jsCM.u:R"v "" v"N+R\-.t*L\v

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

Perl 5 , 118 байт

115 байт кода + -plaфлаги.

\@X[$_]for@F;s%\d+ ?%Y x$&.$"x($#X-$&).$/%ge;while(/Y.{$#X} /s){print$_,_ x$#X;1while s/Y(.{$#X}) /X$1b/s;y/bX/Y /}

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

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

Я использую Yвместо *и _вместо -.

Октава, 104 байта

b=(1:max(L=input("")))<=L;do;disp(" *-"([b;max(b)+1]+1))until b==(b=imerode(b,k=[1;1])|imdilate(b,k)~=b)

* Требуется пакет изображений.

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

Объяснение:

input = [8 ;4 ;2 ;1]

L = input('');                    %input list
b=(1:max(L))<=L;                  % generate matrix of 0s and 1s as indexes of asterisks 

b =

  1  1  1  1  1  1  1  1
  1  1  1  1  0  0  0  0
  1  1  0  0  0  0  0  0
  1  0  0  0  0  0  0  0
do;
    disp(' *-'([b;max(b)+1]+1))  %display asterisks and dashes

    E = imerode(b,k=[1;1]);      %morphological erosion
    E =

      1  1  1  1  0  0  0  0
      1  1  0  0  0  0  0  0
      1  0  0  0  0  0  0  0
      1  0  0  0  0  0  0  0

    D = imdilate(b,k);           %morphological dilation
    D =

      1  1  1  1  1  1  1  1
      1  1  1  1  1  1  1  1
      1  1  1  1  0  0  0  0
      1  1  0  0  0  0  0  0

    b_temp = E | (D~=b)          %intermediate result
    b_temp =

      1  1  1  1  0  0  0  0
      1  1  0  0  1  1  1  1
      1  0  1  1  0  0  0  0
      1  1  0  0  0  0  0  0

until b==(b=b_temp)              %loop until no change

Python, 203 199 байт

def k(x):
 m,j=max(x),''.join;d=[*map(lambda i:('*'*i).ljust(m),x)];f=sorted(d);print(*d,sep='\n')
 while d!=f:d=[*map(j,zip(*[x.replace('* ',' *')for x in map(j,zip(*d))]))];print('-'*m,*d,sep='\n')

Japt , 69 62 байта

-7 байт благодаря @Shaggy

®ç'x +SpZnUrwÃpQpUrw¹·
V
l o ®V=z d" x""x " z3ÃuW
X¯XbXgJ)Ä ·

Изучал Джапта и хотел попробовать более сложную задачу. Вывод с xs и "s вместо звездочек и тире; принимает входные данные в виде массива чисел. Предполагается, что сортировка будет завершена в течение нескольких input.lengthшагов; поправьте меня, если это не так.

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

объяснение

                              // implicit: U = input array
 ®   ç'x +SpZnUrwà pQpUrw¹ ·  // implicit: V = this line
UmZ{Zç'x +SpZnUrw} pQpUrw) qR // ungolfed
UmZ{             }            // U mapped by the function:
    Zç'x                      //   "x" times this item
         +SpZnUrw             //   plus " " times the max of the input array (Urw) minus this value (Z)
                   pQpUrw)    // push " (Q) times the max
                           qR // join with newlines

V                             // implicit: W = this line

 l o ®   V=z d" x""x " z3Ã uW // implicit: X = this line
Ul o mZ{ZV=z d" x""x " z3} uW // ungolfed
Ul o                          // the array of the range [0, U.length)
     mZ{Z                }    // mapped by the no-arg function:
         V=z                  //   set V to itself rotated 90deg
             d" x""x "        //   replace all " x" with "x " to "fall"
                       z3     // rotate back to normal
                           uW // add  W(the original) to the start

X¯XbXgJ)Ä ·                   // implicit: return this line
Xs0,XbXgJ)+1 qR               // ungolfed
Xs0,                          // get the substring of X from 0 to...
    XbXgJ)+1                  // the first index of the last item, plus one
             qR               // join with newlines

R , 210 205 байт

l=scan();w=max(l);h=sum(l|1);a=1:h;p=h+1;m=matrix(' ',w,p);m[,p]='+';for(x in a)m[l[x]:1,x]='*';f=function()write(m,'',w,sep='');f();while(any(i<-m[,a]>m[,a+1])){s=which(i);m[,a][s]=' ';m[,a][s+w]='*';f()}

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

читает в списке из stdin; разделенные +символами вместо -. Это намного дольше, чем я думал. Использует тот факт, что сравнение '*'>'+'оценивается, FALSEно '*'>' 'есть TRUE, по крайней мере, на TIO (на моей машине, которую я использовал, '='которая выглядела немного лучше).

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

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

Haskell , 213 211 208 байт

import Data.List
(?)=replicate
p=transpose
s l|w<-length l,i<-[n?'*'++w?' '|n<-l]=intercalate[w?'-']$i:(p<$>unfoldr f(p i))
f i|i==n=mempty|2>1=Just(n,n)where n=t<$>i
t(a:b:y)|a>b=" *"++t y|2>1=a:t(b:y);t k=k

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

Javascript, 274 байта

a=>(r="",m=Math.max(...a),b=a.map(n=>Array(m).fill(0).map((_,i)=>i<n)),(k=_=>(b.map(c=>r+=c.map(v=>v?"*":" ").join``.trim()+`
`),r+="-".repeat(m)+`
`,n=0,b.map((r,i)=>(s=b[i+1])&&r.map((c,j)=>s[j]||(n|=s[j]=-(c>0),c>0&&(r[j]=0)))),b=b.map(c=>c.map(n=>n<0?1:n)),n&&k()))(),r)

Пример кода:

f =

a=>(r="",m=Math.max(...a),b=a.map(n=>Array(m).fill(0).map((_,i)=>i<n)),(k=_=>(b.map(c=>r+=c.map(v=>v?"*":" ").join``.trim()+`
`),r+="-".repeat(m)+`
`,n=0,b.map((r,i)=>(s=b[i+1])&&r.map((c,j)=>s[j]||(n|=s[j]=-(c>0),c>0&&(r[j]=0)))),b=b.map(c=>c.map(n=>n<0?1:n)),n&&k()))(),r)

o.innerText = f([6,4,2,5,3,1])

<pre id=o>