정수 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 일반적인 고려 사항
3. 실용적인 알고리즘
4. 이론적인 알고리즘
참조

1. 개요

정수 정렬은 정수를 정렬하는 알고리즘으로, 정렬할 데이터의 수, 키의 크기, 컴퓨터의 워드 크기에 따라 시간 복잡도가 달라진다. 계산 모델로는 포인터 머신과 랜덤 액세스 머신이 사용되며, 외부 메모리 모델에서는 비교 정렬보다 빠르지 않다. 실용적인 알고리즘으로는 비둘기집 정렬, 계수 정렬, 기수 정렬 등이 있으며, 이론적인 알고리즘으로는 반 엠데 보아스 트리, Y-fast 트라이, 압축 정렬 알고리즘 등이 있다. 또한, 전이분할 모델을 이용한 융합 트리 정렬 알고리즘도 존재한다.

더 읽어볼만한 페이지

정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.

정수 정렬

2. 일반적인 고려 사항

정수 정렬 알고리즘의 성능은 정렬할 데이터의 개수, 키 값의 범위, 사용되는 컴퓨터의 구조 등 여러 요인에 따라 달라진다.

비둘기집 정렬, 계수 정렬, 기수 정렬과 같은 고전적인 정수 정렬 알고리즘은 널리 사용되며 실용적이다.^[5] 그러나 이후의 연구는 대부분 이론적인 개선에 초점을 맞추었기 때문에, 여기서 나온 알고리즘들은 현재의 64비트 컴퓨터 구조에서는 실용적이지 않은 경우가 많다. 일부 연구에서는 이러한 알고리즘들이 키당 128비트 이상의 데이터에 대해서는 기수 정렬보다 나은 성능을 보일 수 있다고 보고하기도 한다.^[6] 하지만 대규모 데이터 집합에서는 많은 정수 정렬 알고리즘이 메모리에 거의 무작위로 접근하는 패턴을 보이기 때문에, 메모리 계층을 고려하여 설계된 비교 정렬 알고리즘에 비해 불리할 수 있다.^[7]

정수 정렬은 DARPA 고생산성 컴퓨팅 시스템 이산 수학 벤치마크 제품군의 6가지 벤치마크 중 하나이며,^[8] NAS 병렬 벤치마크 제품군의 11개 벤치마크 중 하나이다.

2. 1. 계산 모델

정수 정렬 알고리즘은 일반적으로 포인터 머신 또는 랜덤 액세스 머신 모델에서 작동하도록 설계되었다. 이 두 모델의 주요 차이점은 메모리를 주소 지정하는 방식이다. 랜덤 액세스 머신은 레지스터에 저장된 모든 값을 메모리 읽기 및 쓰기 연산의 주소로 사용할 수 있으며, 연산당 단위 비용이 발생한다. 이러한 기능을 통해 테이블 조회를 사용하여 데이터에 대한 특정 복잡한 연산을 빠르게 구현할 수 있다. 반면에, 포인터 머신 모델에서는 읽기 및 쓰기 연산에서 포인터에 저장된 주소를 사용하며, 이러한 포인터에 대한 산술 연산은 허용되지 않는다. 두 모델 모두에서 데이터 값을 더할 수 있으며, 비트 단위 부울 연산과 이진 시프트 연산도 일반적으로 연산당 단위 시간 내에 수행할 수 있다. 그러나 서로 다른 정수 정렬 알고리즘은 정수 곱셈도 단위 시간 연산으로 허용되는지 여부에 대해 서로 다른 가정을 한다.^[3] 병렬 랜덤 액세스 머신과 같은 다른 보다 특수한 계산 모델도 고려되었다.^[4]

안데르손(Andersson), 밀테르센(Miltersen), 토룹(Thorup) (1999)은 일부 정수 정렬 알고리즘에 필요한 곱셈 또는 테이블 조회를 하드웨어에서 더 쉽게 구현할 수 있지만 일반적으로 범용 컴퓨터에서는 사용할 수 없는 사용자 지정 연산으로 대체할 수 있음을 보여주었다. 토룹(Thorup) (2003)은 이러한 특수 연산을 비트 필드 조작 명령으로 대체하는 방법을 보여줌으로써 이를 개선했다. 이러한 명령은 이미 펜티엄 프로세서에서 사용할 수 있다.

2. 2. 정렬 대 정수 우선순위 큐

우선순위 큐는 숫자 우선순위를 가진 항목 모음을 유지하기 위한 자료 구조로, 최소 우선순위 값을 가진 항목을 찾고 제거하는 연산을 수행한다. 이진 힙과 같은 비교 기반 우선순위 큐는 업데이트당 로그 시간(logarithmic time)이 걸리지만, van Emde Boas 트리 또는 버킷 큐와 같은 다른 구조는 우선순위가 작은 정수인 입력을 처리할 때 더 빠를 수 있다. 이러한 자료 구조는 선택 정렬 알고리즘에서 사용될 수 있으며, 이는 모음에서 가장 작은 요소를 반복적으로 찾아 제거하고 찾아낸 순서대로 요소를 반환하여 요소 모음을 정렬한다. 우선순위 큐는 이 알고리즘에서 요소 모음을 유지하는 데 사용될 수 있으며, *n*개의 요소 모음에 대한 이 알고리즘의 시간은 우선순위 큐를 초기화하는 시간과 *n*개의 찾기 및 제거 연산을 수행하는 시간으로 제한될 수 있다. 예를 들어, 선택 정렬에서 우선순위 큐로 이진 힙을 사용하면 *O*(*n* log *n*) 시간이 걸리는 비교 정렬 알고리즘인 힙 정렬 알고리즘이 된다. 반대로, 버킷 큐와 함께 선택 정렬을 사용하면 일종의 비둘기집 정렬이 되고, van Emde Boas 트리 또는 기타 정수 우선순위 큐를 사용하면 다른 빠른 정수 정렬 알고리즘이 된다.

정렬 알고리즘에서 정수 우선순위 큐를 사용하는 대신, 반대 방향으로 진행하여 정수 정렬 알고리즘을 정수 우선순위 큐 자료 구조 내의 서브루틴으로 사용할 수 있다. 만약 정수 정렬을 키당 *T*(*n*) 시간에 수행할 수 있다면, 동일한 시간 제한이 우선순위 큐 자료 구조에서 삽입 또는 삭제 연산 시간에도 적용된다.^[1]

2. 3. 사용성

고전적인 정수 정렬 알고리즘인 비둘기집 정렬, 계수 정렬, 기수 정렬은 널리 사용되고 실용적이다.^[5] 이후의 연구는 실용성보다는 최악의 경우 분석에 대한 이론적 개선에 더 집중했으며, 이 연구에서 나온 알고리즘은 현재의 64비트 컴퓨터 아키텍처에서는 실용적이지 않다고 여겨진다. 하지만 실험 결과에 따르면, 이러한 방법 중 일부는 키당 128비트 이상의 데이터에 대해 기수 정렬보다 개선될 수 있다.^[6] 또한, 대규모 데이터 집합의 경우, 많은 정수 정렬 알고리즘의 거의 임의적인 메모리 접근 패턴은 메모리 계층을 염두에 두고 설계된 비교 정렬 알고리즘에 비해 불리하게 작용할 수 있다.^[7]

정수 정렬은 DARPA 고생산성 컴퓨팅 시스템 이산 수학 벤치마크 제품군의 6가지 벤치마크 중 하나이며,^[8] NAS 병렬 벤치마크 제품군의 11개 벤치마크 중 하나이다.

3. 실용적인 알고리즘

비둘기집 정렬과 계수 정렬은 모두 $O(n+K)$ 시간에 $n$ 개의 데이터 항목을 $0$ 에서 $K-1$ 범위의 키로 정렬한다. 기수 정렬은 비둘기집 정렬이나 계수 정렬보다 더 큰 키에 대해 작동하는 정렬 알고리즘으로, 데이터에 대해 여러 번의 패스를 수행한다.

3. 1. 비둘기집 정렬 (버킷 정렬)

비둘기집 정렬(종종 버킷 정렬이라고도 함)은 데이터 항목에 대한 포인터를 키를 테이블에 대한 인덱스로 사용하여 컬렉션 자료형(예: 연결 리스트)으로 표현되는 버킷 테이블에 분산시킨다. 그런 다음 모든 버킷을 연결하여 출력 목록을 형성한다.^[9] 입력 데이터에 대한 단순 루프와 가능한 키 집합에 대한 단순 루프만 포함하므로 전체 시간 제한을 가진다.

3. 2. 계수 정렬

비둘기집 정렬과 유사하게, 계수 정렬은 시간에 개의 데이터 항목을 에서 범위의 키로 정렬한다. 계수 정렬은 버킷 테이블 대신 카운터 테이블을 사용하여 각 키에 대한 항목 수를 결정한다. 그런 다음, 누적 합 계산을 사용하여 각 키의 값이 배치되어야 하는 정렬된 출력에서 위치 범위를 결정한다. 마지막으로 입력에 대한 두 번째 패스에서 각 항목은 출력 배열에서 해당 키의 위치로 이동된다.^[10] 이 알고리즘은 입력 데이터에 대한 단순 루프 (시간 ) 와 가능한 키 집합에 대한 단순 루프 (시간 ) 만 포함하므로 전체 시간은 이다.

3. 3. 기수 정렬

기수 정렬은 비둘기집 정렬이나 계수 정렬보다 더 큰 키에 대해 작동하는 정렬 알고리즘으로, 데이터에 대해 여러 번의 패스를 수행한다. 각 패스는 작은 키에만 적합한 다른 정렬 알고리즘(예: 비둘기집 정렬 또는 계수 정렬)을 사용하여 키의 일부만으로 입력을 정렬한다. 기수 정렬 알고리즘은 키를 부분으로 나누기 위해 선택한 기수에 따라 각 키에 대한 위치 기수법을 계산한다. 그런 다음 알고리즘의 i번째 패스에 사용되는 키의 일부는 가장 낮은 유효 숫자부터 시작하여 가장 높은 유효 숫자로 진행하면서 전체 키에 대한 위치 기수법에서 i번째 숫자이다. 이 알고리즘이 제대로 작동하려면 데이터에 대한 각 패스에 사용되는 정렬 알고리즘이 안정적이어야 한다. 즉, 동일한 숫자를 가진 항목은 서로 위치를 변경해서는 안 된다. 가장 효율적으로 사용하려면 기수를 데이터 항목 수인 n에 가깝게 선택해야 한다. 또한 n에 가까운 2의 거듭제곱을 기수로 사용하면 빠르고 비트 시프트 및 마스크 연산만 사용하여 각 패스의 키를 빠르게 계산할 수 있다. 이러한 선택과 비둘기집 정렬 또는 계수 정렬을 기본 알고리즘으로 사용하면 기수 정렬 알고리즘은 0에서 K - 1 범위의 키를 가진 n개의 데이터 항목을 O(n log_n K) 시간에 정렬할 수 있다.^[11]

4. 이론적인 알고리즘

이론적으로 비교 정렬, 비둘기집 정렬, 기수 정렬보다 더 나은 성능을 보이는 정수 정렬 알고리즘들이 개발되었다.^[6] 이는 정렬할 항목의 수, 키의 범위, 기계 워드 크기를 정의하는 매개변수들의 조합이 충분히 큰 경우에 해당한다. 어떤 알고리즘이 최고의 성능을 보이는지는 이러한 매개변수들의 값에 따라 달라진다.^[6]

하지만, 이러한 이론적인 장점에도 불구하고, 이 알고리즘들은 실제 정렬 문제에서 발생하는 일반적인 범위의 매개변수 값에 대해서는 개선된 성능을 보이지 않는다.^[6]

4. 1. 작은 키를 위한 알고리즘

반 엠더 보아스 트리는 0에서 ''K'' - 1 범위 내의 ''n''개의 키 집합을 시간 ''O''(''n'' log log ''K'')에 정렬하는 우선 순위 큐로 사용할 수 있다. 이는 ''K''가 충분히 클 때 기수 정렬보다 이론적으로 개선된 것이다. 그러나 반 엠더 보아스 트리를 사용하려면 ''K'' 워드의 직접 주소 지정이 가능한 메모리가 필요하거나 해시 테이블을 사용하여 시뮬레이션해야 하며, 이 경우 공간이 선형으로 줄어들지만 알고리즘이 확률화된다. 유사한 성능(해시 테이블 형태의 확률화 필요 포함)을 가진 또 다른 우선 순위 큐는 Y-fast 트라이이다.^[1]

Kirkpatrick과 Reisch는 기수 정렬의 각 패스가 선형 시간 내에 최대 키 크기를 ''n''의 인수로 줄이는 범위 축소 기술로 해석될 수 있다는 것을 관찰했다. 그들의 기술은 선형 시간 내에 키 크기를 이전 값의 제곱근으로 줄인다(키를 나타내는 데 필요한 비트 수를 절반으로 줄임). 기수 정렬과 마찬가지로, 그들은 키를 밑 ''b''가 대략 인 두 자리 기수-''b'' 숫자로 해석한다. 그런 다음 정렬할 항목을 큰 키를 가지는 숫자로, 선형 시간 내에 대규모의 초기화되지 않은 직접 주소 지정 메모리 또는 해시 테이블을 사용하여 버킷으로 그룹화한다. 각 버킷에는 대표가 있으며, 가장 큰 키를 가진 버킷의 항목이다. 그런 다음 대표의 높은 자릿수와 비대표의 낮은 자릿수를 키로 사용하여 항목 목록을 정렬한다. 이 목록의 항목을 다시 버킷으로 그룹화하면 각 버킷을 정렬된 순서로 배치할 수 있으며, 정렬된 목록에서 대표를 추출하면 버킷을 정렬된 순서로 연결할 수 있다. 따라서 선형 시간 내에 정렬 문제는 키가 이전 크기의 제곱근인 훨씬 작은 또 다른 재귀 정렬 문제로 축소된다. 키가 버킷 정렬에 충분히 작아질 때까지 이 범위 축소를 반복하면 실행 시간이 인 알고리즘이 생성된다.^[3] 워드 RAM 계산 모델의 Han과 Thorup의 복잡한 확률적 알고리즘을 사용하면 이러한 시간 경계를 까지 더 줄일 수 있다.^[2]

4. 2. 큰 워드를 위한 알고리즘

Albers-Hagerup|알버스-하게루프^영어의 비보존적 압축 정렬 알고리즘은 켄 배처의 비토닉 정렬 네트워크를 기반으로 하는 서브루틴을 사용하며, 각 키가 단일 기계 워드에 압축될 만큼 충분히 짧은 키의 정렬된 두 시퀀스를 병합한다.^[12] 압축 정렬 알고리즘의 입력은 워드당 하나씩 저장된 항목의 시퀀스로, 이 서브루틴을 반복적으로 사용하여 각 워드에 압축된 항목 수를 두 배로 늘려 압축된 형태로 변환한다. 시퀀스가 압축된 형태가 되면 Albers와 Hagerup은 병합 정렬의 한 형태를 사용하여 정렬한다. 두 시퀀스를 병합하여 단일 더 긴 시퀀스를 형성할 때, 동일한 비토닉 정렬 서브루틴을 사용하여 두 시퀀스의 가장 작은 나머지 요소로 구성된 압축된 워드를 반복적으로 추출할 수 있다. 이 알고리즘은 단일 워드가 Ω(log ''n'' log log ''n'')개의 키를 포함할 수 있을 때, 즉, 어떤 상수 ''c'' > 0에 대해 log ''K'' log ''n'' log log ''n'' ≤ ''cw''일 때 입력을 선형 시간에 정렬할 수 있을 만큼 압축된 표현으로 충분한 속도 향상을 얻는다.^[13]

4. 3. 적은 항목을 위한 알고리즘

셀-프로브 모델을 사용한 적은 항목에 대한 빠른 정렬의 초기 결과는 Ajtai, Fredman, Komlós가 제시했다.^[1] (이는 알고리즘의 복잡성이 수행하는 메모리 접근 횟수에 의해서만 측정되는 인공 모델이다.)^[1] Fredman과 Willard는 이를 바탕으로 Q-힙과 원자 힙이라는 두 가지 데이터 구조를 설명했다.^[2] Q-힙은 이진 트라이의 비트 병렬 버전으로, 인 개의 항목 집합에 대해 우선순위 큐 연산과 후임자 및 이전자 쿼리를 모두 상수 시간에 수행할 수 있다.^[2] 여기서 는 데이터 구조를 구현하는 데 필요한 미리 계산된 테이블의 크기이다.^[2] 원자 힙은 각 트리 노드가 Q-힙으로 표현되는 B-트리이다.^[2] 이 힙은 항목 집합에 대해 상수 시간 우선순위 큐 연산(따라서 정렬)을 허용한다.^[2]

Andersson, Hagerup, Nilsson, Raman은 임의 알고리즘인 시그니처 정렬을 제공하여 상수 에 대해 한 번에 최대 개의 항목 집합을 선형 시간으로 정렬할 수 있다.^[3] Kirkpatrick과 Reisch의 알고리즘과 마찬가지로, 그들은 신중하게 선택된 에 대한 기수 의 숫자로 키를 표현하여 범위 축소를 수행한다.^[3] 그들의 범위 축소 알고리즘은 각 숫자를 시그니처로 대체한다.^[3] 시그니처는 서로 다른 숫자 값이 서로 다른 시그니처를 갖도록 비트의 해시 값이다.^[3] 이 충분히 작으면 이 대체 프로세스에 의해 형성된 숫자는 원래 키보다 훨씬 작아 Albers와 Hagerup의 보수적이지 않은 패킹 정렬 알고리즘이 선형 시간 내에 대체된 숫자를 정렬할 수 있다.^[3] 대체된 숫자의 정렬된 목록에서 선형 시간 내에 키의 압축된 트라이를 형성할 수 있으며, 트라이의 각 노드의 자식은 크기의 키만 사용하여 재귀적으로 정렬할 수 있으며, 그 후 트리 순회를 통해 항목의 정렬된 순서를 생성한다.^[3]

4. 4. 전이분할 알고리즘

Fredman과 Willard(1993)는 정수 정렬 알고리즘에 대한 전이분할 모델 분석을 도입했는데, 여기서 정수 키의 범위에 대해서는 아무것도 가정하지 않으며 알고리즘의 성능은 데이터 값의 수의 함수로만 제한해야 한다. 이러한 유형의 첫 번째 알고리즘은 Fredman과 Willard의 융합 트리 정렬 알고리즘으로, 시간에 실행된다. 이는 비교 정렬보다 개선된 것이다.

그들의 연구 이후, 더 나은 알고리즘이 개발되었다. 예를 들어, Kirkpatrick–Reisch 범위 감소 기술을 반복적으로 적용하여 시간에 정렬하는 것이 가능하다. 그러나 이 알고리즘의 범위 감소 부분은 큰 메모리 또는 해시 테이블 형태의 무작위화를 필요로 한다.

Han과 Thorup(2002)는 무작위 시간 에 정렬하는 방법을 보여주었다. 그들의 기술은 서명 정렬과 관련된 아이디어를 사용하여 데이터를 서명 정렬이 각 하위 목록을 효율적으로 정렬할 수 있을 만큼 작은 크기의 많은 작은 하위 목록으로 분할하는 것을 포함한다. 유사한 아이디어를 사용하여 시간과 선형 공간에서 정수를 결정론적으로 정렬하는 것도 가능하다.

참조

_[1] 논문 Han Thorup 2002
_[2] 논문 Fredman Willard 1993
_[3] 논문 Fredman Willard 1993
_[4] 논문 Reif 1985
_[5] 논문 McIlroy Bostic McIlroy 1993
_[6] 논문 Rahman Raman 1998
_[7] 논문 Pedersen 1999
_[8] 웹사이트 DARPA HPCS Discrete Mathematics Benchmarks http://www.cse.sc.ed[...] 2016-03-10
_[9] 논문 Goodrich Tamassia 2002
_[10] 서적 Cormen Leiserson Rivest Stein 2001
_[11] 서적 Comrie 1929–1930
_[12] 논문 Kirkpatrick Reisch 1984
_[13] 논문 Kirkpatrick Reisch 1984
_[14] 논문 Andersson Hagerup Nilsson Raman 1998
_[15] 논문 Han 2004
_[16] 논문 Thorup 2002
_[17] 논문 Han Thorup 2002

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com