큐빅
Cubesort |
 |
| 클래스 | 정렬 알고리즘 |
|---|---|
| 데이터 구조 | 배열 |
| 최악의 경우 공연 | O(n log n) |
| 최악의 경우 공간 복잡성 | θ(n) |
큐보트는 정렬할 키로부터 자체 균형 다차원 배열을 구축하는 병렬 정렬 알고리즘이다.축의 길이가 비슷하기 때문에 구조는 입방체를 닮았다.각 키를 삽입한 후 큐브를 배열로 빠르게 변환할 수 있다.[1]
C로 쓰여진 큐빅 구현은 2014년에 출판되었다.[2]
작전
큐보트의 알고리즘은 각 축에 대한 특수 이항 검색을 사용하여 요소를 삽입할 위치를 찾는다.축이 너무 커지면 갈라진다.삽입할 때마다 작은 배열에 대해 4개의 이진 검색만 수행되므로 참조의 인접성이 최적이다.많은 소형 동적 어레이를 사용함으로써 단일 대형 어레이에 높은 삽입 비용을 피할 수 있다.
참조
- ^ Cypher, Robert; Sanz, Jorge L.C (1992). "Cubesort: A parallel algorithm for sorting N data items with S-sorters". Journal of Algorithms. 13 (2): 211–234. doi:10.1016/0196-6774(92)90016-6.
- ^ "Cubesort".
외부 링크
- 큐브포트 설명 및 구현(C)
- 알고리즘과 연산: 제7회 국제 심포지엄, IACH 96, 오사카...Tetsuo Asano 외, pp 187-197, https://books.google.com/books?id=vilOl8JCpFUC&pg=PA188&lpg=PA188&hl=en&f=false(자세한 언급) 편집
