스파게티 종류

Spaghetti sort

스파게티 분류는 A. K. 듀드니가 사이언티픽 아메리칸 칼럼에서 소개한 일련의 항목을 정렬하기 위한 선형 시간 아날로그 알고리즘이다.[1][2][3] 이 알고리즘은 O(n) 스택 공간이 필요한 항목의 순서를 안정적으로 정렬한다. 병렬 프로세서가 필요하다.

알고리즘.

간단히 말해서, 우리가 자연수 목록을 분류하고 있다고 가정해보자. 분류 방법은 스파게티의 조리되지 않은 봉을 사용하여 설명한다.

  1. 목록의 각 숫자 x에 대해 길이 x 로드를 구한다.(단위를 선택하는 한 가지 실용적인 방법은 목록에서 가장 큰 숫자 m이 스파게티 로드의 하나의 전체 로드에 해당하도록 하는 것이다. 이 경우 풀 로드는 m 스파게티 단위와 같다. 길이 x의 막대를 얻으려면 한 조각이 길이 x 단위가 되도록 막대기를 두 개로 부러뜨리고, 다른 조각은 폐기하십시오.)
  2. 스파게티 로드를 모두 손에 넣었으면 주먹에 느슨하게 쥐고 테이블로 내려서 모두 똑바로 서서 테이블 표면에 쉬도록 하라. 자, 각 막대마다 다른 손을 위에서 아래로 내려서 그것이 막대기와 만날 때까지. 이 손이 분명히 가장 길다. 이 로드를 제거하고 (초기적으로 비어 있는) 출력 목록의 전면에 삽입하십시오(또는 동등하게, 출력 배열의 마지막 사용되지 않는 슬롯에 배치). 모든 로드가 제거될 때까지 반복하십시오.

분석

스파게티의 n 로드를 준비하는 것은 선형적인 시간이 걸린다. 테이블의 로드를 내리려면 일정한 시간이 걸린다, O(1). 이것은 손, 스파게티 로드, 테이블이 완전히 평행한 계산 장치로 작동하기 때문에 가능하다. 그런 다음 각 접촉 및 제거 작업에 일정한 시간이 걸린다고 가정할 때 제거해야 하는 로드가 n개 있으며, 알고리즘의 최악의 시간 복잡성은 O(n)이다.

참조

  1. ^ Dewdney, A. K. (June 1984), "On the spaghetti computer and other analog gadgets for problem solving", Scientific American, vol. 250, no. 6, pp. 19–26
  2. ^ Stauffer, Dietrich (May 15, 1999), Annual Reviews of Computational Physics VI, World Scientific, p. 260, ISBN 981-02-3563-1
  3. ^ Adamatzky, Andrew (July 1, 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, p. 96, ISBN 0-9551170-9-7

외부 링크