정렬 네트워크 계산기 (바이토닉·홀짝 병합)
입력을 보지 않고 미리 정해진 순서로만 비교·교환하는 정렬 회로를 만들어 비교기 수와 단수를 냅니다. 0과 1로만 이루어진 모든 입력을 넣어 정말 정렬되는지 전수로 확인해 보여 줍니다.
입력 개수
바이토닉과 홀짝 병합은 2의 거듭제곱일 때만 만들어집니다. 홀짝 전위는 2개부터 16개까지 아무 수나 됩니다.
쉼표나 공백으로 구분합니다. 개수가 모자라면 알아서 채우고 남으면 자릅니다.
홀짝 병합(배처) 네트워크 · 입력 8개
비교기 19개 · 6단
하나씩 순서대로 돌리면 19단계가 들지만, 겹치지 않는 비교기를 한꺼번에 돌리면 6단계로 끝납니다. 병렬로 돌렸을 때 3.17배 빠른 셈입니다.
회로도
가로선이 값이 흐르는 선이고 세로선 하나가 비교기입니다. 비교기는 두 선의 값을 보고 작은 쪽을 위로, 큰 쪽을 아래로 보냅니다. 같은 가로 위치에 나란히 선 비교기들이 한 단이며, 서로 선을 겹쳐 쓰지 않으므로 동시에 동작해도 됩니다. 왼쪽 숫자가 입력, 오른쪽 파란 숫자가 결과입니다.
단별 진행
| 단 | 비교기 | 이 단이 끝난 뒤 | 바뀜 |
|---|---|---|---|
| 시작 | — | 5 3 8 1 9 2 7 4 | — |
| 1 | (0,1) (2,3) (4,5) (6,7) | 3 5 1 8 2 9 4 7 | 4 |
| 2 | (0,2) (1,3) (4,6) (5,7) | 1 5 3 8 2 7 4 9 | 2 |
| 3 | (1,2) (5,6) (0,4) (3,7) | 1 3 5 8 2 4 7 9 | 2 |
| 4 | (1,5) (2,6) | 1 3 5 8 2 4 7 9 | 0 |
| 5 | (2,4) (3,5) | 1 3 2 4 5 8 7 9 | 2 |
| 6 | (1,2) (3,4) (5,6) | 1 2 3 4 5 7 8 9 | 2 |
값이 무엇이든 비교기의 순서는 똑같습니다. 「바뀜」이 0인 단이 있어도 건너뛰지 않습니다 — 건너뛰려면 값을 봐야 하는데, 값을 보지 않는 것이 이 회로의 존재 이유입니다.
사용 방법
- 1네트워크 종류를 고릅니다. 홀짝 병합이 비교기가 가장 적고, 홀짝 전위는 배선이 가장 단순합니다.
- 2입력 개수를 고릅니다. 바이토닉과 홀짝 병합은 2·4·8·16만 됩니다.
- 3정렬해 볼 값을 쉼표로 구분해 넣으면 회로도의 왼쪽에 입력, 오른쪽에 결과가 나옵니다.
- 4「단별 진행」에서 한 단이 끝날 때마다 값이 어떻게 움직이는지 확인합니다.
- 5맨 아래에서 0-1 전수 검사 결과를 봅니다. 모두 통과했다면 그 회로는 어떤 입력이 와도 정렬합니다.
자주 묻는 질문
입력값을 보지 않고 미리 정해진 순서로만 비교·교환해 정렬하는 회로입니다. 비교기 하나는 두 자리를 보고 작은 값을 한쪽으로, 큰 값을 다른 쪽으로 보내는 일만 합니다. 퀵소트나 삽입정렬과 달리 비교 결과에 따라 다음 행동이 갈리는 분기가 아예 없어서, 어떤 입력이 와도 똑같은 자리를 똑같은 순서로 비교합니다.
분기가 없어서 하드웨어로 굳히거나 병렬로 돌릴 수 있기 때문입니다. 선을 겹쳐 쓰지 않는 비교기들은 동시에 동작해도 되므로, 비교기를 「단」으로 묶으면 한 단이 한 클럭이 됩니다. 입력 8개짜리 홀짝 병합 네트워크는 비교기가 19개지만 단수는 6이라, 하나씩 돌리는 것보다 3배 넘게 빠릅니다. GPU·FPGA·SIMD처럼 분기가 비싼 곳에서 이 맞바꿈이 남습니다.
0과 1로만 이루어진 입력을 모두 정렬하는 네트워크는 어떤 입력이든 정렬한다는 정리입니다. 모든 순서를 확인하려면 n개일 때 n!가지를 넣어야 하지만, 0-1 원리 덕분에 2ⁿ가지만 보면 됩니다. 16개면 20조 가지가 65,536가지로 줄어듭니다. 비교기가 하는 일이 min과 max뿐이고 이 둘이 단조 증가 함수와 자리를 바꿔도 되기 때문에 성립합니다. 이 계산기는 실제로 2ⁿ가지를 전부 돌려 결과를 보여 줍니다.
같은 입력 개수에서 단수는 같고 비교기는 홀짝 병합(배처)이 적습니다. 8개일 때 바이토닉은 24개, 홀짝 병합은 19개를 쓰면서 둘 다 6단입니다. 하드웨어 면적으로는 홀짝 병합이 유리합니다. 다만 바이토닉은 모든 단이 정확히 n/2개로 꽉 차 있고 짝짓는 규칙이 i XOR j로 단순해서 GPU 커널로 옮기기가 쉬워, 실제 GPU 구현에서는 바이토닉이 더 자주 보입니다.
이웃한 두 선끼리만 이어지면 되는 배선이 필요할 때 씁니다. 비교기가 n(n−1)/2개로 가장 많고 단수도 n으로 가장 크지만, 물리적으로 떨어진 선을 잇지 않아도 되므로 시스톨릭 배열처럼 배선 거리가 비용인 구조에 맞습니다. 입력 개수에 2의 거듭제곱 같은 제약도 없습니다.
홀짝 전위를 쓰거나, 실제 구현에서는 모자란 자리를 무한대 값으로 채워 다음 2의 거듭제곱까지 늘립니다. 이 계산기는 바이토닉과 홀짝 병합을 2·4·8·16에서만 만듭니다. 채워 넣는 방식은 낭비되는 비교기가 생기고 채운 값이 결과 뒤쪽에 몰리는 것을 따로 잘라내야 해서, 회로 자체를 보여 주는 목적에는 오히려 헷갈리기 때문입니다.
전송되지 않습니다. 회로 구성과 검사가 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 검증은 0-1 원리 전수 검사로 했습니다. 세 네트워크 모두 만들 수 있는 모든 입력 개수(2~16)에서 2ⁿ가지 0-1 입력을 남김없이 넣어 정렬되는지 확인했습니다.
- 0-1 원리 자체도 확인했습니다. 입력 8개까지는 n!가지 순열을 실제 수로 전부 넣어 정렬되는지 따로 봤고, 0-1 전수 검사와 결과가 같았습니다.
- 검사기가 껍데기가 아닌지도 확인했습니다. 맞는 네트워크에서 비교기를 하나씩 빼 가며 19가지 경우를 만들어 보니 모두 검사에 걸렸습니다.
- 비교기 수와 단수는 널리 알려진 값과 맞춰 두었습니다. 입력 8개에서 바이토닉 24개·6단, 홀짝 병합 19개·6단, 홀짝 전위 28개·8단입니다. 홀짝 전위의 비교기 수가 n(n−1)/2로 딱 떨어지는 것도 16개까지 확인했습니다.
- 단은 비교기를 앞에서부터 훑으며 두 선이 모두 비어 있는 가장 이른 자리에 넣어 나눕니다. 비교기의 순서는 그대로 지키므로 결과가 달라지지 않습니다.
- 입력 16개까지만 다룹니다. 0-1 전수 검사가 2ⁿ가지를 모두 돌리기 때문이고, 17개부터는 브라우저에서 즉시 끝나지 않습니다.
- 이 계산기가 만드는 것은 잘 알려진 구성법 세 가지입니다. 비교기 수를 가장 적게 만드는 「최소 정렬 네트워크」는 별개의 어려운 문제이고, 입력 9개 이상에서는 아직 최적이 확정되지 않은 크기도 있습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.