나는 Batcher Sort의 개념을 파악하려고합니다. 그러나 필자가 온라인에서 찾은 대부분의 자료는 전적으로 또는 저급 의사 코드에 초점을 맞 춥니 다. 증명을보기 전에 Batcher Sort가 어떻게 작동하는지 이해하고 싶습니다. 어떤 사람이 지나치게 장황한 가상 코드없이 배터 정렬이 작동하는 방식 (특히 병합)에 대한 높은 수준의 개요를 제공 할 수 있습니까 (구현하지 않고 배지 정렬에 대한 아이디어를 원합니다). 감사!Batcher Merge는 어떻게 높은 수준에서 작동합니까?
배터의 정렬은 배터의 병합과 병합됩니다.
두 개의 배열 A와 B를 병합하려면 Batcher의 병합에서 A를 B와 역순으로 병합하여 비트 배열을 만듭니다. 그런 다음 Batcher의 격렬한 정렬을 적용합니다.
배터의 격렬한 정렬은 퀵 소트의 사촌입니다. 이 배열은 배열을 두 개의 반으로 나눕니다. 첫 번째 반의 요소가 두 번째 요소의 요소보다 크지 않도록 교체합니다. 반올림을 반복적으로 정렬합니다.
배열을 회전시켜 요소가 증가하거나 감소 할 수있는 경우 배열은 비트닉입니다. 뻔뻔스러운 종류의 제로 원론에 따르면, 제로 원 입력에 대한 정확성을 증명하는 것만으로도 충분하며, 이제 우리는 그 가정을합니다. 가능성은
0^a 1^b 0^c = 0 ... a copies ... 0 1 ... b copies ... 1 0 ... c copies ... 0 (rotate right by c positions)
및 A, B, C가 음이 아닌 정수
1^a 0^b 1^c (rotate left by a positions)
A = 0^w
B = 1^x 0^y 1^z
또는
A = 0^w 1^x
B = 1^y 0^z
또는
A = 0^w 1^x 0^y
B = 1^z
유일한 사소하지 않은 경우가
A = 0^w 1^x
B = 1^y 0^z
하고 보완
이다. w> = y이면 A, B가A = 0^(w+x)
B = 1^y 0^(w-y) 1^x
이됩니다. 따라서 A는 모두 0이고 B는 비트입니다. w < y이면,
A = 0^w 1^(y-w) 0^z
B = 1^(y+z)
이므로 B는 모두 1이고 A는 비트 음입니다. 우리가 재귀 적으로 A와 B를 정렬하면, 그것들의 연결은 정렬 된 배열입니다.