병합 정렬 시각화

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

목록에서 알고리즘의 실행은 [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]) 또는 분할 때마다 무작위로.

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

테스트 사례

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

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



답변

하스켈 , 137 128 127 125 121 109 106 바이트

nimi 덕분에 (-2) + (-4) = (-6) 바이트 ! 목록에서 모든 단계를 수집하도록 다시 변경하면 (니미로 인해) 12 바이트가 더 절약됩니다.

Laikoni에 의한 또 다른 3 바이트 , 패턴 가드 바인딩 및 가드를 인코딩하기 위해 목록 이해력을 영리하게 사용합니다.

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

온라인으로 사용해보십시오!

목록을 홀수 및 짝수 요소로 나누는 것은 두 개의 순차적 인 절반보다 짧은 코드입니다. 왜냐하면 우리는를 측정해야하기 때문 length입니다.

목록을 “인쇄”한 다음 실제로 분할이 수행 된 경우 분할 목록 ( x >>= h)으로 되풀이 하고 정렬 된 목록을 “인쇄”하여 작동합니다. 하나의 입력 목록으로 시작; 비어 있지 않은 입력을 가정합니다. 실제 인쇄하는 대신 목록으로 수집 하면됩니다.

g[[6,5..1]]인쇄 된 목록 은 다음과 같습니다.

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


답변

볼프람 언어 (티카) , 146 (127) 111 102 바이트

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

온라인으로 사용해보십시오!

List단계가 포함 된를 반환 합니다.

설명

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

입력에서 List2 개 이상의 정수를 포함하는 모든 s를 반으로 나눕니다 . 첫 번째 하위 목록에는 홀수 색인 요소 (1 색인)가 있고 두 번째 하위 목록에는 짝수 색인 요소가 있습니다.

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

아무것도 변경되지 않을 때까지 반복하십시오 (즉, 모든 하위 목록의 길이는 1입니다). 모든 중간 결과를 유지하십시오. 이것을 ( List모든 단계 중)에 저장 하십시오 u.

Reverse@Most@u

마지막 요소를 u버리고 뒤집습니다.

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

위의 결과에서 정수 목록의 모든 항목을 정렬하십시오.


답변

면도 , 228 206 168 157 140 121 104 바이트

n끝에서 n-th 요소가 처음부터 -th 요소 의 정렬 된 버전 이라는 사실을 사용하여 끝에서 안쪽으로 단계 목록을 작성합니다 .

에서 아이디어 JungHwan 최소의 코멘트

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

온라인으로 사용해보십시오!


답변

, 145 133 123 122 바이트

≔⟦⪪S ⟧θW⊖L§θ⁰«⟦⪫Eθ⪫κ ¦|⟧≔EE⊗Lθ§θ÷λ²✂κ﹪λ²Lκ²θ»⟦⪫ΦEθ⪫ι ι|⟧W⊖Lθ«≔⮌θη≔⟦⟧θWη«≔⊟ηε≔⟦⟧ζF⊟η«≔εδ≔⟦⟧εFδ⊞⎇‹IμIλζεμ⊞ζλ»⊞θ⁺ζε»⟦⪫Eθ⪫κ ¦|

온라인으로 사용해보십시오! 링크는 자세한 버전의 코드입니다. 여전히 숯불 문제를 해결해야합니다 … 편집 : Map가난한 사람의 배열 이해력 으로 double 을 사용하여 5 바이트를 절약했습니다 . Pop배열을 두 번 반복 하여 4 바이트를 절약했습니다 . 대신 연결을 사용하여 3 바이트를 절약했습니다 Push. while숯불 버그를 피하는 골퍼 조건으로 10 바이트를 절약했습니다 . Charcoal에 실제로 필터 연산자가 있음을 발견하여 1 바이트를 절약했습니다. 설명:

≔⟦⪪S ⟧θ

공백으로 입력을 분할 한 다음 결과를 외부 배열로 래핑하여에 저장합니다 q.

W⊖L§θ⁰«

의 첫 번째 요소에 q둘 이상의 요소가있는 동안 반복하십시오 . (첫 번째 요소 q는 목록이 두 가지로 나뉘어져 있기 때문에 항상 가장 많은 요소를 갖습니다.)

⟦⪫Eθ⪫κ ¦|⟧

q공백과 수직선 으로 결합 된 요소를 인쇄합니다 . (배열은 결과를 자체 행에 인쇄합니다. 동일한 바이트 수로이를 달성하는 다른 방법이 있습니다.)

≔EE⊗Lθ§θ÷λ²✂κ﹪λ²Lκ²θ»

의 각 요소를 복제하여 목록을 생성 한 q다음 해당 목록 위에 매핑하고 각 목록의 절반을 대체 요소 접근 방식을 사용하여 결과를에 저장합니다 q.

⟦⪫ΦEθ⪫ι ι|⟧

q공백과 수직선 으로 결합 된 요소를 인쇄합니다 . 실제로이 시점에서의 요소는 q비어 있거나 단일 요소 목록이므로 결합하면 빈 문자열 또는 요소로 변환됩니다. 빈 문자열은 불필요한 후행 줄을 추가하여 필터링됩니다. 납작한 연산자는 그래도 골퍼 였을 것 ⟦⪫Σθ|⟧입니다.

W⊖Lθ«

q요소가 둘 이상있는 동안 반복하십시오 . (다음 코드에는 짝수 개의 요소가 필요합니다.)

≔⮌θη≔⟦⟧θ

로 복사 하되 반전 q시키십시오 h(아래 참조) q. 빈 목록으로 재설정 하십시오.

Wη«

h비어 있을 때까지 반복하십시오 .

≔⊟ηε

의 다음 요소 추출 h에를 e. ( Pop끝에서 추출하기 때문에 반전해야합니다 q.)

≔⟦⟧ζ

z빈 목록으로 초기화 하십시오.

F⊟η«

의 다음 요소의 요소를 반복합니다 h.

≔εδ≔⟦⟧ε

복사 ed리셋e 빈 목록.

Fδ

의 요소를 반복 d .

⊞⎇‹IμIλζεμ

그것들을 다음 요소의 현재 요소보다 작은 지에 따라 z또는eh .

⊞ζλ»

다음 요소의 현재 요소 hz .

⊞θ⁺ζε»

z남아있는 요소와 연결하여을 ( 를) e누릅니다 q. 이것으로 두 요소의 병합을 완료합니다h .

⟦⪫Eθ⪫κ ¦|

q공백과 수직선 으로 결합 된 요소를 인쇄합니다 .


답변

파이썬 2 , 145144 바이트

에서 아이디어 JungHwan 분의 의견
조나단 FRECH -1 바이트 감사

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

온라인으로 사용해보십시오!


답변

자바 스크립트 (ES6), 145 바이트

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]])받습니다 ( 예 🙂 . 출력의 첫 번째와 마지막 줄을 생성 한 다음 모든 하위 배열의 길이가 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
      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


답변

껍질 , 14 바이트

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.

내장 ½은 배열 을 가져 와서 중간에 나눕니다. 길이가 홀수이면 첫 번째 부분이 하나의 요소만큼 길어집니다. 단일 배열이 [a]발생 [[a],[]]하고 빈 배열이 []제공 [[],[]]되므로 적용하기 전에 빈 배열을 제거해야합니다 U.