Scalanie sortowania to algorytm sortowania, który działa poprzez podzielenie danej listy na pół, rekurencyjne sortowanie obu mniejszych list i scalenie ich z powrotem w jedną posortowaną listę. Podstawowy przypadek rekurencji dochodzi do listy singletonów, której nie można dalej dzielić, ale według definicji jest już posortowana.

Wykonanie algorytmu na liście [1,7,6,3,3,2,5]można wizualizować w następujący sposób:

       [1,7,6,3,3,2,5]
       /             \      split
   [1,7,6,3]       [3,2,5]
    /     \        /    \   split
 [1,7]   [6,3]   [3,2]  [5]
 /   \   /   \   /   \   |  split
[1] [7] [6] [3] [3] [2] [5]
 \   /   \   /   \   /   |  merge
 [1,7]   [3,6]   [2,3]  [5]
    \     /         \   /   merge
   [1,3,6,7]       [2,3,5]
       \             /      merge
       [1,2,3,3,5,6,7]

Zadanie

Napisz program lub funkcję, która pobiera listę liczb całkowitych w jakikolwiek rozsądny sposób jako dane wejściowe i wizualizuje różne partycje tej listy podczas sortowania według algorytmu sortowania po scaleniu. Oznacza to, że nie musisz generować wykresu jak powyżej, ale tylko listy są w porządku:

[1,7,6,3,3,2,5]
[1,7,6,3][3,2,5]
[1,7][6,3][3,2][5]
[1][7][6][3][3][2][5]
[1,7][3,6][2,3][5]
[1,3,6,7][2,3,5]
[1,2,3,3,5,6,7]

Co więcej, każda rozsądna notacja na liście jest w porządku, dlatego następujące dane byłyby również prawidłowymi danymi wyjściowymi:

1 7 6 3 3 2 5
1 7 6 3|3 2 5
1 7|6 3|3 2|5
1|7|6|3|3|2|5
1 7|3 6|2 3|5
1 3 6 7|2 3 5
1 2 3 3 5 6 7

Wreszcie sposób podzielenia listy na dwie mniejsze listy zależy od ciebie, o ile długość obu list wynikowych różni się co najwyżej o jedną. Oznacza to, że zamiast dzielić [3,2,4,3,7]na [3,2,4]i [3,7], możesz również dzielić, biorąc elementy o indeksach parzystych i nieparzystych ( [3,4,7]i [2,3]), a nawet za każdym razem losować podział.

To jest golf golfowy , więc wygrywa najkrótszy kod w dowolnym języku mierzony w bajtach.

Przypadki testowe

Jak wspomniano powyżej, faktyczny format i sposób podziału list na pół zależy od Ciebie.

[10,2]
[10][2]
[2,10]

[4,17,1,32]
[4,17][1,32]
[4][17][1][32]
[4,17][1,32]
[1,4,17,32]

[6,5,4,3,2,1]
[6,5,4][3,2,1]
[6,5][4][3,2][1]
[6][5][4][3][2][1]
[5,6][4][2,3][1] <- Important: This step cannot be [5,6][3,4][1,2], because 3 and 4 are on different branches in the the tree
[4,5,6][1,2,3]
[1,2,3,4,5,6]

Haskell , 137 128 127 125 121 109 106 bajtów

^{(-2) + (- 4) = (- 6) bajtów dzięki Nimi ! Zmiana go w celu zebrania wszystkich kroków na liście (ponownie z powodu nich) pozwala zaoszczędzić jeszcze 12 bajtów.}

^{Kolejne 3 bajty ze względu na Laikoni , z powiązaniem strażnika wzorca i sprytnym użyciem zrozumienia listy do zakodowania strażnika.}

import Data.List
g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]
h[a]=[[a]]
h x=foldr(\x[b,a]->[x:a,b])[[],[]]x

Wypróbuj online!

Podział list na nieparzyste i parzyste elementy jest krótszym kodem niż na dwie kolejne połówki, ponieważ nie musimy lengthwtedy mierzyć .

Działa poprzez „drukowanie” list, a następnie rekurencję z listami podzielonymi (x >>= h ), jeśli rzeczywiście dokonano podziału, i „drukowanie” posortowanych list; zaczynając od listy z jednym wejściem; przy założeniu niepustego wejścia. I zamiast faktycznego drukowania, wystarczy zebrać je na liście.

Lista tworzona przez g[[6,5..1]], drukowana linia po linii, to:

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

Wolfram Language (Mathematica) , 146 127 111 102 bajtów

Join[u=Most[#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&~FixedPointList~#],Reverse@Most@u/.a:{b}:>Sort@a]&

Wypróbuj online!

Zwraca a, Listktóry zawiera kroki.

Wyjaśnienie

#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&

Na wejściu podziel wszystkie Lists zawierające 2 lub więcej liczb całkowitych na pół. Pierwsza lista podrzędna zawiera elementy nieparzyste (1 indeksowane), a druga ma elementy parzyste.

u=Most[... &~FixedPointList~#]

Powtarzaj to, dopóki nic się nie zmieni (tzn. Wszystkie listy podrzędne mają długość-1). Zachowaj wszystkie wyniki pośrednie. Przechowuj to ( Listwszystkie kroki) w u.

Reverse@Most@u

Upuść ostatni element ui odwróć go.

... /.a:{b}:>Sort@a

Na podstawie powyższego wyniku posortuj wszystkie wystąpienia listy liczb całkowitych.

Czysty , 228 206 168 157 140 121 104 bajtów

Tworzy listę etapów od końców do wewnątrz, wykorzystując fakt, że n-ty element od końca jest posortowaną wersjąn -tego elementu od początku.

Pomysł z komentarza JungHwan Min

import StdEnv
@u#(a,b)=splitAt(length u/2)u
=if(a>[])[[u]:[x++y\\y<- @b&x<- @a++ @a++ @a]][]++[[sort u]]

Wypróbuj online!

Węgiel drzewny , 145 133 123 122 bajtów

≔⟦⪪Ｓ ⟧θＷ⊖Ｌ§θ⁰«⟦⪫Ｅθ⪫κ ¦|⟧≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»⟦⪫ΦＥθ⪫ι ι|⟧Ｗ⊖Ｌθ«≔⮌θη≔⟦⟧θＷη«≔⊟ηε≔⟦⟧ζＦ⊟η«≔εδ≔⟦⟧εＦδ⊞⎇‹ＩμＩλζεμ⊞ζλ»⊞θ⁺ζε»⟦⪫Ｅθ⪫κ ¦|

Wypróbuj online! Link jest do pełnej wersji kodu. Wciąż muszę obejść błędy związane z węglem drzewnym ... Edycja: Zaoszczędziłem 5 bajtów, używając podwójnej Mapjako tablicy dla biednego człowieka. Zaoszczędzono 4 bajty, używając Popdo podwójnej iteracji po tablicy. Zaoszczędzono 3 bajty, używając konkatenacji zamiast Push. Zaoszczędzono 10 bajtów, wprowadzając whilewarunek golfisty , który pozwala również uniknąć błędu węgla drzewnego. Zaoszczędzono 1 bajt, odkrywając, że węgiel rzeczywiście ma operatora filtru. Wyjaśnienie:

≔⟦⪪Ｓ ⟧θ

Podziel dane wejściowe na spacje, a następnie zawiń wynik w zewnętrznej tablicy, zapisując to w q.

Ｗ⊖Ｌ§θ⁰«

Powtarzaj, gdy pierwszy element qma więcej niż jeden element. (Pierwszy element qzawsze ma najwięcej elementów ze względu na sposób podziału list na dwa).

⟦⪫Ｅθ⪫κ ¦|⟧

Wydrukuj elementy qpołączonych spacjami i liniami pionowymi. (Tablica powoduje, że wynik jest drukowany we własnej linii. Istnieją inne sposoby osiągnięcia tego dla tej samej liczby bajtów.)

≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»

Utwórz listę, powielając każdy element q, a następnie zmapuj tę listę i weź połowę każdej listy (stosując podejście do elementów alternatywnych), zapisując wynik z powrotem q.

⟦⪫ΦＥθ⪫ι ι|⟧

Wydrukuj elementy qpołączonych spacjami i liniami pionowymi. Właściwie w tym momencie elementy qsą albo listami pustymi, albo jednoelementowymi, więc połączenie ich po prostu przekształca je w puste łańcuchy lub ich elementy. Puste łańcuchy dodawałyby niepotrzebne końcowe linie, aby zostały odfiltrowane. Spłaszczony operator byłby jednak bardziej golfistą (coś w stylu ⟦⪫Σθ|⟧).

Ｗ⊖Ｌθ«

Powtórz, gdy qma więcej niż jeden element. (Poniższy kod wymaga parzystej liczby elementów).

≔⮌θη≔⟦⟧θ

Skopiuj qdo h, ale cofnij (patrz poniżej) i zresetuj qdo pustej listy.

Ｗη«

Powtarzaj, aż hbędzie pusty.

≔⊟ηε

Wyciąg następny element hdo e. ( Popwyciągi z końca, dlatego muszę cofnąć q.)

≔⟦⟧ζ

Zainicjuj zna pustej liście.

Ｆ⊟η«

Pętla nad elementami następnego elementu h.

≔εδ≔⟦⟧ε

Skopiować edo di przywrócić edo pustej listy.

Ｆδ

Pętla nad elementami d.

⊞⎇‹ＩμＩλζεμ

Popchnij je do zlub w ezależności od tego, czy są mniejsze niż bieżący element następnego elementu h.

⊞ζλ»

Naciśnij bieżący element następnego elementu hdo z.

⊞θ⁺ζε»

Połącz zz pozostałymi elementami ei popchnij to do q. To kończy scalenie dwóch elementów h.

⟦⪫Ｅθ⪫κ ¦|

Wydrukuj elementy qpołączonych spacjami i liniami pionowymi.

Python 2 , 145 144 bajtów

^{Pomysł z komentarza JungHwan Min
-1 bajt dzięki Jonathan Frech}

p=input()
l=[[p]]
i=0
while 2**i<len(p):l[i+1:i+1]=[sum([[x[1::2],x[::2]][len(x)<2:]for x in l[i]],[]),map(sorted,l[i])];i+=1
for s in l:print s

Wypróbuj online!

JavaScript (ES6), 145 bajtów

f=a=>a.join`|`+(a[0][1]?`
${f([].concat(...a.map(b=>b[1]?[b.slice(0,c=-b.length/2),b.slice(c)]:[b])))}
`+a.map(b=>b.sort((x,y)=>x-y)).join`|`:``)

Pobiera dane wejściowe jako tablicę w obrębie tablicy, tj f([[6,5,4,3,2,1]]). Działa, generując pierwszy i ostatni wiersz wyniku, a następnie dzieląc i wywołując się ponownie, aż każda podgrupa ma długość 1. Oto podstawowa demonstracja tego, jak to działa:

f([[6,5,4,3,2,1]]):
  6,5,4,3,2,1
  f([[6,5,4],[3,2,1]]):
    6,5,4|3,2,1
    f([[6,5],[4],[3,2],[1]]):
      6,5|4|3,2|1
      f([[6],[5],[4],[3],[2],[1]]):
        6|5|4|3|2|1
      end f
      5,6|4|2,3|1
    end f
    4,5,6|1,2,3
  end f
  1,2,3,4,5,6
end f

Łuska , 14 bajtów

S+ȯ†O↔hUmfL¡ṁ½

Pobiera tablicę zawierającą pojedynczą tablicę. Wypróbuj online!

Wyjaśnienie

S+ȯ†O↔hUmfL¡ṁ½  Implicit input, say A = [[4,17,32,1]].
           ¡    Iterate this function on A:
            ṁ½   Split each array in two, concatenate results: [[4,17],[32,1]]
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[],[17],[],[32],[],[1],[]],
                           ...
        mfL     Map filter by length, removing empty arrays.
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[17],[32],[1]],
                           ...
       U        Longest prefix of unique elements:
                       P = [[[4,17,32,1]],[[4,17],[32,1]],[[4],[17],[32],[1]]]
      h         Remove last element: [[[4,17,32,1]],[[4,17],[32,1]]]
     ↔          Reverse: [[[4,17],[32,1]],[[4,17,32,1]]]
   †O           Sort each inner array: [[[4,17],[1,32]],[[1,4,17,32]]]
S+ȯ             Concatenate to P:
                           [[[4,17,32,1]],
                            [[4,17],[32,1]],
                            [[4],[17],[32],[1]],
                            [[4,17],[1,32]],
                            [[1,4,17,32]]]
                Implicitly print.

Wbudowany ½pobiera tablicę i dzieli ją na środku. Jeśli jego długość jest nieparzysta, pierwsza część jest dłuższa o jeden element. Tablicy Singleton [a]skutkuje [[a],[]]i pusta tablica []daje [[],[]], więc jest to konieczne w celu usunięcia pustych tablic przed zastosowaniem U.

Stax , 116 (÷ 3>) 38 29 bajtów ^CP437

-9 bajtów na komentarz przez @recursive. Teraz dane wejściowe podano jako singleton, którego jedynym elementem jest tablica liczb do posortowania.

ƒ3s}óºE/ßB╢↕êb∩áαπüµrL╞¶è,te+

Wypróbuj online!

Wersja rozpakowana z 35 bajtami:

{c{Jm'|*Pc{2Mm:f{fc{Dm$wW{{eoJm'|*P

Wyjaśnienie

Kod można podzielić na dwie części. Pierwsza część wizualizuje podział, a druga wizualizuje scalanie.

Kod do wizualizacji podziału:

{                      w    Do the following while the block generates a true value
 c                          Copy current nested array for printing
  {Jm                       Use spaces to join elements in each part
     '|*                    And join different parts with vertical bar 
        P                   Pop and print

         c                  Copy current nested array for splitting
          {2Mm              Separate each element of the array to two smaller parts with almost the same size
                                That is, if the number of elements is even, partition it evenly.
                                Otherwise, the first part will have one more element than the second.
              :f            Flatten the array once
                {f          Remove elements that are empty arrays

                  c         Copy the result for checking 
                   {Dm$     Is the array solely composed of singletons?
                            If yes, ends the loop.

Kod wizualizacji scalania:

W              Execute the rest of the program until the stack is empty
 {{eoJm        For each part, sort by numeric value, then join with space
       '|*     Join the parts with vertical bar
          P    Pop and print the result

Stara wersja, właściwie budująca zagnieżdżoną strukturę listy.

{{cc0+=!{x!}Mm',*:}}Xd;%v:2^^{;s~{c^;<~sc%v,*{2M{s^y!svsm}M}YZ!x!Q,dmU@e;%v:2^{;%v:2^-N~0{c;={scc0+=Cc%v!C:f{o}{scc0+=C{s^y!svsm}?}Y!cx!P,dcm

cc0+= jest używany trzy razy w kodzie, aby sprawdzić, czy szczyt stosu jest skalarem, czy tablicą.

{{cc0+=!{x!}Mm',*:}}Xbuduje blok, który rekurencyjnie wywołuje się, aby poprawnie wypisać zagnieżdżoną tablicę liczb. (Domyślne wyjście w Stax wektoryzuje zagnieżdżoną tablicę przed drukowaniem).

{                  }X    Store the code block in X
 {           m           Map each element in the list with block
  cc                     Make two copies of the element
    0+                   + 0. If the element is a scalar, nothing will change
                              If the element is an array, the element 0 will be appended
      =!{  }M            If the element has changed after the `0+` operation
                             Which means it is an array
         x!              Recursively execute the whole code block on the element

              ',*        Join the mapped elements with comma
                 :}      Bracerizes the final result

Istnieją dwa inne bloki, które odpowiednio dzielą i scalają. Są zbyt gadatliwi i nie dbam o wyjaśnienia (w historycznej wersji tego postu jest nieco więcej informacji, ale nie oczekuję zbyt wiele).