비드 정렬

Bead sort

중력 분류라고도 불리는 비드 분류는 조슈아 J. 아룰란담, 크리스티안 S. 칼루드, 마이클 J. 디넨이 2002년에 개발한 자연 분류 알고리즘으로, 유럽 이론 컴퓨터 과학 협회 회보에 게재되었다.[1]비드 분류의 디지털 하드웨어 구현과 아날로그 하드웨어 구현 모두 O(n)의 정렬 시간을 달성할 수 있지만, 이 알고리즘의 구현은 소프트웨어에서 상당히 느린 경향이 있고 양의 정수 목록을 정렬하는 데만 사용할 수 있다.또한, 최선의 경우에도 알고리즘에는 O(n2) 공간이 필요한 것으로 보인다.

알고리즘 개요

1단계: 수직 폴에 매달린 구슬.
2단계: 구슬이 떨어지도록 허용했다.

비드 분류 작업은 주판과 같이 비드가 평행 극에서 미끄러지는 방식과 비교할 수 있다.그러나 각 극에는 뚜렷한 수의 구슬이 있을 수 있다.처음에는 수직 기둥에 매달린 구슬을 상상하는 것이 도움이 될 수 있다.1단계에서 이러한 배열은 m=4 수직 극에 n=5줄의 비드를 사용하여 표시된다.각 행의 오른쪽에 있는 숫자는 해당 행이 나타내는 숫자를 나타낸다. 1행과 2행은 각각 3개의 구슬을 포함하기 때문에 양의 정수 3을 나타내고, 상단 행은 (2개의 구슬만 포함하기 때문에) 양의 정수 2를 나타낸다.[2]

만약 우리가 구슬이 떨어지도록 한다면, 그 행들은 이제 정렬된 순서대로 같은 정수를 나타낸다.1행은 집합에서 가장 큰 숫자를 포함하고 n행은 가장 작은 숫자를 포함한다.위에서 언급한 극 1..k와 극 k+1m 빈 채로 있는 극에 일련의 구슬이 들어 있는 행의 관습이 지켜졌다면, 여기서는 계속 그럴 것이다.

우리의 물리적 예에서 구슬을 "떨어지게" 하는 작용은 높은 행의 더 큰 값을 낮은 행으로 전파할 수 있게 했다.행 a로 나타낸 값이 행 a+1에 포함된 값보다 작을 경우, 행 a+1의 일부 구슬은 행 a에 속하게 된다. 행 a가 해당 위치에 구슬을 포함하지 않아 a+1의 구슬이 떨어지는 것을 막을 수 없기 때문에 이러한 현상이 발생할 것이 확실하다.

염기 비드 분류의 기초가 되는 메커니즘은 분류 뒤에 있는 것과 유사하다. 각 극에 있는 구슬의 수는 해당 극의 지수보다 같거나 큰 값을 가진 원소의 수에 해당한다.

복잡성

비드 정렬은 다음과 같은 네 가지 일반적인 수준의 복잡성으로 구현될 수 있다.

  • O(1) 구슬은 위의 간단한 물리적 예에서와 같이 모두 동일한 시간 단위로 동시에 이동한다.이것은 추상적인 복잡성으로, 실제로 실행될 수 없다.
  • O( 중력을 사용하는 현실적인 물리적 모델에서 구슬이 떨어지도록 하는 데 걸리는 시간은 n에 비례하는 최대 높이의 제곱근에 비례한다.
  • O(n): 구슬을 한 줄씩 움직인다.아날로그와 디지털 하드웨어 솔루션에서 사용되는 사례다.
  • O(S), 여기서 S는 입력 세트의 정수의 합이다: 각 비드는 개별적으로 이동한다.소프트웨어 구현과 같이 구슬 아래의 빈 공간을 찾는 데 도움이 되는 메커니즘 없이 비드 분류가 구현되는 경우가 이에 해당한다.

비둘기홀 분류와 마찬가지로, 비드 분류는 최악의 경우 O(n log n)보다 더 빠르게 수행될 수 있다는 점에서 이례적인 것으로, 최악의 경우 비교 분류가 가능한 가장 빠른 성능이다.이것은 비드 분류의 키가 항상 양의 정수이고 비드 분류가 그 구조를 이용하기 때문에 가능하다.

실행

이 구현은 Python에 기록되어 있다; 는 것으로 가정한다.input_list정수의 연속이 될 거야전달된 리스트를 변형하지 않고 새로운 리스트를 반환하는 기능이지만, 제자리에 효율적으로 운영되도록 사소한 수정도 가능하다. 

반항하다 구슬이 돋다(input_list):     """비드 분류."""     return_list = []     # '전송된 목록'을 초기화하여 최대한 많은 요소를 포함     # 입력의 최대값 - 실제로 '입력'을 취함     # 입력 구슬 기둥, 평평하게 펴서     transposed_list = [0] * 맥스.(input_list)     을 위해 숫자 에 input_list:         # 입력 목록의 각 요소(각 '비드 열')에 대해,         # '구슬을 평평하게 깔다' 원소 수만큼 증분해         # 칼럼이 높아서 리스트가 바뀐다.         # 이것들은 이전의 추가 사항들 위에 축적될 것이다.         transposed_list[:숫자] = [n + 1 을 위해 n 에 transposed_list[:숫자]]     # 이제 구슬을 떨어뜨렸다.트랜스포트 해제를 위해서는     # 떨어뜨린 구슬의 '병행'을 한 다음, 이것을 제거하는 흉내를 낸다.     # 전치목록의 각 '열'에서 1을 뺀 행     # 열이 현재 행에 비해 충분히 높은 위치에 도달하지 못할 경우,     # transposed_list의 값은 <= 0>이 될 것이다.     을 위해 _ 에 input_list:         # 값을 세는 것 > 0은 구슬이 몇 개인지 어떻게 말하는가.         # 현재 '병신행'Python의 볼은         # 정수로 평가됨; 참 == 1, 거짓 == 0.         return_list.덧셈을(합계를 내다(n > 0 을 위해 n 에 transposed_list))         # 각 원소에서 1을 빼서 '병목 행'을 제거한다.         transposed_list = [n - 1 을 위해 n 에 transposed_list]     # 결과 목록은 내림차순으로 정렬     돌아오다 return_list

참조 및 참고 사항

  1. ^ Arulanandham, Joshua J.; Calude, Cristian S.; Dinneen, Michael J. (January 2002). "Bead-Sort: A Natural Sorting Algorithm" (PDF). Department of Computer Science, University of Auckland. Retrieved 2021-05-14.
  2. ^ 관례에 따라, 양의 정수 k를 나타내는 행은 극 1.k에 구슬이 있어야 하고 극 k+1m는 비어 있어야 한다.이것은 엄격한 요구사항은 아니지만, 시행을 단순화할 가능성이 높다.

외부 링크