병합 정렬 은 주어진 목록을 반으로 나누고 작은 목록을 재귀 적으로 정렬 한 다음 다시 정렬 된 목록으로 병합하여 작동하는 정렬 알고리즘입니다. 재귀의 기본 사례는 싱글 톤 목록에 도달하는데,이 목록은 더 이상 분할 할 수 없지만 정의에 따라 이미 정렬되어 있습니다.

목록에서 알고리즘의 실행은 [1,7,6,3,3,2,5]다음과 같은 방식으로 시각화 할 수 있습니다.

       [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]

작업

적절한 정렬 방식으로 정수 목록을 입력으로 사용하고 병합 정렬 알고리즘으로 정렬되는 동안이 목록의 다른 파티션을 시각화하는 프로그램 또는 함수를 작성하십시오. 즉 , 위와 같이 그래프를 출력 할 필요는 없지만 목록 만 있으면됩니다.

[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]

또한 합리적인 목록 표기법은 괜찮으므로 다음과 같은 결과가 유효합니다.

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

마지막으로, 두 결과 목록의 길이가 최대 하나가 다르면 목록을 두 개의 작은 목록으로 나누는 방법은 사용자에게 달려 있습니다. 그 말 대신 분할 [3,2,4,3,7]로 [3,2,4]하고 [3,7], 당신은 또한 짝수 및 홀수 인덱스 (에서 요소를 고려하여 분할 수 [3,4,7]와 [2,3]) 또는 분할 때마다 무작위로.

이것은 code-golf 이므로 바이트 단위 로 측정 된 모든 언어에서 가장 짧은 코드 가 우선합니다 .

테스트 사례

위에서 언급했듯이 실제 형식과 목록을 반으로 나누는 방법은 사용자에게 달려 있습니다.

[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]

답변

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

[[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]]

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

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

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

Reverse@Most@u

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

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

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

≔⟦⪪Ｓ ⟧θ

Ｗ⊖Ｌ§θ⁰«

⟦⪫Ｅθ⪫κ ¦|⟧

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

⟦⪫ΦＥθ⪫ι ι|⟧

Ｗ⊖Ｌθ«

≔⮌θη≔⟦⟧θ

Ｗη«

≔⊟ηε

≔⟦⟧ζ

Ｆ⊟η«

≔εδ≔⟦⟧ε

Ｆδ

⊞⎇‹ＩμＩλζεμ

⊞ζλ»

⊞θ⁺ζε»

⟦⪫Ｅθ⪫κ ¦|

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

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

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

S+ȯ†O↔hUmfL¡ṁ½

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.