[정렬 알고리즘] Bead 정렬 (번역)

#자료구조/알고리즘

Bead 정렬(혹은 Gravity 정렬)은 자연적인 정렬 알고리즘 중 하나입니다.

이건 디지털이든 아날로그 하드웨어든 O(n)의 정렬시간을 달성할 수 있어요.
그런데, 이 알고리즘의 구현은 소프트웨어에선 느린 경향이 있어요. 그리고 양수의 리스트를 정렬핼 때만 사용할 수 있죠.

이건 하드웨어 구현이 소프트웨어 구현보다 훨씬 빠르다는 것에 대한 완벽한 예시이기도 합니다.
소프트웨어는 해당 하드웨어보다 빨라야만 한다는 통상적인 믿음에 반대되죠.(mechanical calculators를 생각한다면)

이 정렬은 2002년에 Joshua J. Arulanandham, Cristian S. Calude, Michael J. Dinneen에 의해서 개발되었습니다.

알고리즘
bead 정렬의 연산은 여러개의 병렬 기둥에 구슬들을 끼워넣은 것과 비교할 수 있습니다. 그러니까 '주판'같은거요.

그런데, 이 각각의 기둥은 구슬의 숫자가 정해져있어요.
처음엔 세로 기둥에 걸린 구슬들을 상상해본다면, 이해하는데 도움이 될겁니다.

스텝 1.
m개의 세로기둥에 n개의 구슬 행(row)을 왼쪽에서 오른쪽으로 채워넣습니다.
n은 정렬할 각 배열의 길이고, m이 해당 배열의 최대 수가 되죠.

스텝 2.
만약 구슬들이 떨어져 모인다면, 행들은 동일한 정수를 정렬된 순서로 표현할 겁니다.
그럼 행 1은 집합에서 가장 큰 수를 포함하겠죠. 행 n이 가장 작은걸 포함하고요

왜 하드웨어 구현이 더 빠를까요?
이 정렬 스텝은 중력에 의해 수행됩니다. 우리가 아는 그 자연적인 물리법칙의 중력이요.
그래서 한 스텝에 병렬로 동시에 처리됩니다. 그냥 중력이 밀어주니까...

이와 다르게 소프트웨어에서, 이 각각의 스텝은 최소 m 클락 사이클을 필요로 합니다.

복잡도(Complexity)
bead 정렬은 다음과 같은 4가지의 일반 수준 복잡도로 구현될 수 있습니다.

O(1):
구슬들이 동일한 단위에서 동시에 전부 움직인다면, 위에 있는 간단한 물리적 예제의 경우처럼 될겁니다.
추상적인 복잡도라서 실제로는 구현할 수 없습니다.

O(√N):
중력을 사용한 현실적인 물리 모델에선, 구슬들이 떨어지도록 하는 시간이 (n에 비례하는) 최대 높이의 루트값에 비례합니다.

O(n):
한번에 한 행의 구슬들이 움직입니다.
이 경우는 아날로그와 디지털 하드웨어 솔루션만 해당합니다.

O(S):
S는 입력 집합에 들어있는 정수들의 합입니다.
각각의 구슬은 개별적으로 움직이죠.
구슬 밑 빈 공간을 찾을 수 있는 메커니즘이 없이 bead 소트가 구현될 경우입니다.
소프트웨어 구현이 그렇죠.