기수 정렬
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
기수 정렬은 각 자릿수를 기준으로 정렬을 반복하여 데이터를 정렬하는 알고리즘이다. 1887년 허먼 홀러리스의 작표기에서 그 기원을 찾을 수 있으며, 1923년 천공 카드를 분류하는 데 널리 사용되었다. 기수 정렬은 최상위 자릿수(MSD) 또는 최하위 자릿수(LSD)부터 시작하여 정렬을 수행하며, LSD 방식은 일반적으로 짧은 키가 긴 키보다 먼저 나오고, 같은 길이의 키는 사전식 순서로 정렬된다. 시간 복잡도는 O(nw)이며, 사전식 데이터에 적합하여 특정 도메인에서 빠른 성능을 보이지만, 큰 키 크기에서는 병목 현상이 발생할 수 있다. 기수 정렬은 병렬 컴퓨팅에 유용하며, 제자리, 안정, 하이브리드 방식 등 다양한 구현 변형이 존재한다.
기수 정렬의 역사는 1887년 허먼 홀러리스가 작표기를 개발하면서 시작되었다.[19] 1923년에는 천공 카드 분류 방법으로 널리 사용되었다.[20]
기수 정렬은 1887년 허먼 홀러리스가 작표기를 만들 때까지 거슬러 올라간다.[19] 1923년에 천공 카드를 분류하는 방법으로 널리 사용되었다.[20]
기수 정렬의 시간 복잡도는 O(''nw'')이다. 여기서 ''n''은 키의 수이고, ''w''는 키의 길이이다. 최하위 자릿수(LSD) 방식은 가변 길이 키를 여러 그룹으로 나누어 ''w''를 '평균 키 길이'로 최적화할 수 있다.
예를 들어, 170, 45, 75, 90, 2, 24, 802, 66과 같은 수열이 주어졌을 때, 1의 자리에 대해 정렬하면 170, 90, 2, 802, 24, 45, 75, 66이 된다. 이어서 10의 자리에 대해 정렬하면 2, 802, 24, 45, 66, 170, 75, 90이 된다. 마지막으로 100의 자리에 대해 정렬하면 2, 24, 45, 66, 75, 90, 170, 802가 되어 정렬이 완료된다.[1]
2. 역사
1954년 매사추세츠 공과대학교의 해럴드 H. 시워드(Harold H. Seward)가 최초로 메모리 효율적인 컴퓨터 알고리즘을 개발했다. 이전에는 알 수 없는 크기의 버킷을 가변 할당해야 한다고 믿었기 때문에 전산화된 기수 정렬은 비현실적인 것으로 여겨졌다. 시워드의 혁신은 선형 탐색을 통해 필요한 버킷 크기와 오프셋을 미리 결정하여 보조 메모리에 단일 정적 할당만 할 수 있도록 한 것이다. 이 선형 탐색은 시워드의 다른 알고리즘인 계수 정렬과 밀접하게 관련되어 있다.
현대에는 이진 문자열과 정수 정렬에 가장 널리 적용된다. 일부 벤치마크에서는 다른 범용 정렬 알고리즘보다 50%에서 3배까지 빠른 것으로 나타났다.[21][22][23]
3. 알고리즘
1954년 매사추세츠 공과대학교(MIT)의 해럴드 H. 시워드는 최초로 메모리 효율적인 컴퓨터 알고리즘을 개발했다. 이전까지는 알 수 없는 크기의 버킷을 가변 할당해야 한다고 믿었기 때문에 전산화된 기수 정렬은 비현실적인 것으로 생각되었다. 시워드의 혁신은 선형 탐색을 사용하여 필요한 버킷 크기와 오프셋을 미리 결정하여 보조 메모리에서 단일 정적 할당만 할 수 있도록 하는 것이었다. 이 선형 탐색은 시워드의 다른 알고리즘인 계수 정렬과 밀접한 관련이 있다.
현대에는 이진 문자열과 정수 정렬에 가장 널리 적용된다. 일부 벤치마크에서 다른 범용 정렬 알고리즘보다 50%에서 3배까지 빠를 때도 있는 것으로 나타났다.[21][22][23]
기수 정렬은 최상위 자릿수 (MSD) 또는 최하위 자릿수 (LSD)부터 시작하도록 구현할 수 있다. 예를 들어, '1234'의 경우 1 (MSD) 또는 4 (LSD)부터 시작할 수 있다.
LSD 기수 정렬은 짧은 키가 긴 키보다 먼저 오고, 동일한 길이의 키는 사전식순서로 정렬되는 특징이 있다. 이는 '1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11'과 같은 정수 표현의 일반적인 순서와 일치한다. MSD 기수 정렬은 문자열 또는 고정 길이 정수 표현을 정렬하는 데 가장 적합하다. 'b, c, e, d, f, g, ba'와 같은 시퀀스는 'b, ba, c, d, e, f, g'로 정렬된다.
이 알고리즘은 데이터 종류가 유한하고 최대값, 최소값이 명확하다는 전제를 두고 있으며, 모든 입력 데이터가 "3자리 정수"나 "2자리의 알파벳" 등 정해진 형식임을 알고 있어야 한다.
3. 1. 최하위 자릿수(LSD) 기수 정렬
LSD (최하위 자릿수) 기수 정렬은 일반적으로 짧은 키가 긴 키보다 먼저 나오고, 같은 길이의 키는 사전 순으로 정렬된다. 그 결과는 '''[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]'''과 같은 정수 표현의 일반적인 순서와 일치한다. LSD 정렬은 일반적으로 안정 정렬이다.[2]
LSD 기수 정렬의 동작 방식은 다음과 같다.
1. 가장 오른쪽(마지막) 숫자부터 시작하여 해당 숫자를 기준으로 정렬한다.
2. 다음 왼쪽 숫자를 기준으로 정렬한다.
3. 마지막으로 가장 왼쪽 숫자를 기준으로 정렬한다.
각 단계는 각 항목이 다른 요소와 비교하지 않고 자체 버킷에 배치될 수 있으므로 데이터를 한 번만 통과하면 된다.
예를 들어, '''[170, 45, 75, 90, 2, 802, 2, 66]'''를 정렬하는 과정은 다음과 같다.
1. 1의 자리를 기준으로 정렬:
'''[{170, 90}, {2, 802, 2}, {45, 75}, {66}]'''
2. 10의 자리를 기준으로 정렬:
'''[{''0''2, 802, ''0''2}, {45}, {66}, {170, 75}, {90}]'''
:두 개의 2는 암묵적으로 숫자 ''0''이 앞에 붙어 802가 그 사이에 위치한다.
3. 100의 자리를 기준으로 정렬:
'''[{''00''2, ''00''2, ''0''45, ''0''66, ''0''75, ''0''90}, {170}, {802}]'''
:1자리 또는 2자리 숫자는 모두 ''0''이 앞에 붙는다.
일부 기수 정렬 구현은 키를 해당 버킷으로 이동하기 전에 각 버킷에 속하는 키의 수를 먼저 계산하여 버킷에 대한 공간을 할당한다. 각 숫자가 나타나는 횟수는 배열에 저장된다.
계수를 사용하여 항상 버킷 경계를 미리 결정할 수 있지만, 일부 구현에서는 대신 동적 메모리 할당을 사용한다.
3. 2. 최상위 자릿수(MSD) 기수 정렬
기수 정렬은 최상위 유효숫자(MSD)에서 시작하여 정렬을 수행할 수 있다. 예를 들어, '1234'를 정렬할 때 1(MSD)부터 시작할 수 있다.
MSD 기수 정렬은 문자열이나 고정 길이 정수 표현 정렬에 적합하다. 예를 들어, '''[b, c, e, d, f, g, ba]'''는 '''[b, ba, c, d, e, f, g]'''로 정렬된다. 사전식 순서로 10진법의 가변 길이 정수를 정렬하면 1부터 10까지의 숫자는 '''[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]'''로 출력된다. 더 짧은 키는 왼쪽 정렬되고 오른쪽이 공백 문자로 채워지는 것과 같다. MSD 정렬은 특정 구현 방식에서는 불안정 정렬이 될 수 있으므로 중복 키의 원래 순서를 항상 유지하지는 않는다.[1]
MSD 정렬은 분할 및 재귀에 더 적합하다. MSD 정렬의 각 단계에서 만들어진 버킷은 이전 단계에서 생성된 다른 버킷을 참조하지 않고 그 안에서 다음 최상위 숫자를 사용하여 기수 정렬을 다시 적용할 수 있다. 마지막 숫자에 도달하면 모든 버킷을 연결하면 정렬이 완료된다.[1]
다음은 입력 목록이 '''[170, 045, 075, 025, 002, 024, 802, 066]'''이고, 선행 0이 있는 고정 폭 숫자 문자열일 때 MSD 기수 정렬의 예시이다.
첫 번째 자릿수로 정렬하면 다음과 같다. (버킷은 대괄호로 표시)
:'''[{045, 075, 025, 002, 024, 066}, {170}, {802}]'''
:170과 802는 해당 버킷에 남은 것이 전부이므로 이미 정렬이 완료되어 더 이상 재귀가 필요하지 않다.
다음 자릿수로 정렬하면 다음과 같다.
:'''[{ {002}, {025, 024}, {045}, {066}, {075} }, 170, 802]'''
마지막 자릿수로 정렬하면 다음과 같다.
:'''[ 002, { {024}, {025} }, 045, 066, 075 , 170, 802]'''
마지막으로 연결하면 정렬이 완료된다.
:'''[002, 024, 025, 045, 066, 075, 170, 802]'''
4. 복잡도 및 성능
특정 영역에서 최적화된 기수 정렬은 매우 빠를 수 있다.[24] 사전식 데이터에 제한이 있지만, 많은 응용에서 이는 문제가 되지 않는다. 다만, 키 크기가 커서 유도 시행 횟수가 병목 현상이 될 정도면 LSD 구현이 어려워질 수 있다.[2]
5. 예시
5. 1. LSD 기수 정렬 (단계별)
LSD 기수 정렬은 가장 낮은 자릿수(1의 자리)부터 시작하여 가장 높은 자릿수(100의 자리)까지 각 자릿수에 대해 정렬을 수행하는 방식이다.
1. 1의 자리에 대한 정렬: 주어진 숫자들을 1의 자리를 기준으로 정렬한다.
2. 10의 자리에 대한 정렬: 앞서 1의 자리를 기준으로 정렬된 숫자들을 10의 자리를 기준으로 다시 정렬한다.
(두 개의 2에는 802 앞에 숫자 '0'이 암묵적으로 붙는다.)
3. 100의 자리에 대한 정렬: 마지막으로, 100의 자리를 기준으로 정렬한다.
(한 자리 또는 두 자리 숫자에는 모두 170과 802 앞에 '0'이 암묵적으로 붙는다.)
각 단계에서 데이터는 한 번만 순회하며, 다른 요소와 비교 없이 자체 버킷에 배치된다.[18]
5. 2. MSD 기수 정렬 (단계별)
입력 목록은 다음과 같다.
'''[170, 045, 075, 025, 002, 024, 802, 066]'''
첫 번째 자릿수에 따라 분류하면 다음과 같다.
'''[{045, 075, 025, 002, 024, 066}, {170}, {802}]'''
:170과 802는 해당 버킷에 남은 것이 전부이므로 이미 정렬이 완료되어 더 이상 재귀가 필요하지 않다.
다음 자릿수에 따라 분류하면 다음과 같다.
'''[{ {002}, {025, 024}, {045}, {066}, {075} }, 170, 802]'''
마지막 자릿수에 따라 분류하면 다음과 같다.
:'''[ 002, { {024}, {025} }, 045, 066, 075 , 170, 802]'''
이제 남은 것은 연결뿐이다.
:'''[002, 024, 025, 045, 066, 075, 170, 802]'''
6. 구현 변형
기수 정렬은 1887년 허먼 홀러리스의 계산기 연구에서 시작되었다.[1] 1923년경부터 천공 카드를 정렬하는 방법으로 널리 사용되었다.[2]
매사추세츠 공과대학교(MIT)의 해럴드 H. 시워드는 1954년에 이 정렬 방식에 대한 최초의 메모리 효율적인 컴퓨터 알고리즘을 개발했다. 이전에는 알려지지 않은 크기의 버킷을 가변적으로 할당해야 했기 때문에 실용적이지 않다고 여겨졌으나, 시워드는 선형 스캔을 통해 필요한 버킷 크기와 오프셋을 미리 결정하여 보조 메모리의 단일 정적 할당을 가능하게 했다.
현대에 기수 정렬은 주로 이진 문자열 및 정수에 적용된다. 일부 벤치마크에서는 다른 정렬 알고리즘보다 50%에서 3배까지 더 빠른 것으로 나타났다.[3][4][5]
기수 정렬은 최상위 자릿수(MSD) 또는 최하위 자릿수(LSD)부터 시작하도록 구현할 수 있다.
- LSD 기수 정렬: 짧은 키가 먼저 오고, 같은 길이의 키는 사전식순서로 정렬된다. 이는 정수 표현의 일반적인 순서와 일치하며, 일반적으로 안정 정렬이다.
- MSD 기수 정렬: 문자열 또는 고정 길이 정수 표현 정렬에 적합하다. 가변 길이 정수를 정렬할 때, 짧은 키를 왼쪽 정렬하고 오른쪽에 공백을 채우는 방식으로 처리하면 숫자 크기 순서와 다르게 정렬될 수 있다. MSD 정렬은 중복 키의 원래 순서를 항상 유지해야 하는 경우 반드시 안정적이지는 않다.
MSD와 LSD 정렬은 가변 길이 입력 처리 방식에서 차이를 보인다. LSD는 길이별 그룹화 후 정렬, 그룹 연결 방식으로 처리하는 반면, MSD는 모든 짧은 키를 가장 큰 키의 크기로 확장하여 정렬하므로 그룹화가 더 복잡할 수 있다. 그러나 MSD는 분할 및 재귀에 더 적합하여, 각 버킷을 자체적으로 기수 정렬할 수 있다.
6. 1. In-place MSD 기수 정렬
이진 MSD 기수 정렬은 이진 퀵 정렬이라고도 하며, 입력 배열을 두 개의 빈(0s 빈과 1s 빈)으로 분할하여 제자리에서 구현할 수 있다. 0s 빈은 배열의 시작 부분에서 커지고, 1s 빈은 배열의 끝 부분에서 커진다. 0s 빈 경계는 첫 번째 배열 요소 앞에, 1s 빈 경계는 마지막 배열 요소 뒤에 놓인다. 첫 번째 배열 요소의 최상위 비트를 검사하여 1이면 첫 번째 요소를 1s 빈 경계 앞의 요소(배열의 마지막 요소)와 교환하고, 1s 빈은 1s 경계 배열 인덱스를 감소시켜 하나만큼 크기를 늘린다. 이 비트가 0이면 첫 번째 요소는 현재 위치에 있고, 0s 빈은 요소 하나만큼 커진다. 다음 검사되는 배열 요소는 0s 빈 경계 앞의 요소(즉, 0s 빈 또는 1s 빈에 속하지 않은 첫 번째 요소)이다. 이 과정은 0s 빈과 1s 빈이 서로 만날 때까지 계속된다. 그런 다음 0s 빈과 1s 빈은 각 배열 요소의 다음 비트를 기준으로 재귀적으로 정렬된다. 재귀적 처리는 최하위 비트가 정렬에 사용될 때까지 계속된다.[7][8] 부호 있는 2의 보수 정수를 처리하려면 최상위 비트를 반대로 처리하고 나머지 비트를 부호 없는 방식으로 처리해야 한다.제자리 MSD 이진 기수 정렬은 더 큰 기수로 확장하여 제자리 기능을 유지할 수 있다. 계수 정렬은 각 빈의 크기와 시작 인덱스를 결정하는 데 사용된다. 현재 요소를 해당 빈에 넣은 다음 빈 경계를 확장하기 위해 교환(스와핑)이 사용된다. 배열 요소를 스캔할 때 빈을 건너뛰고 빈 사이의 요소만 처리하며, 전체 배열이 처리되고 모든 요소가 해당 빈에 배치될 때까지 반복한다. 빈의 수는 사용된 기수와 동일하다(예: 16진수의 경우 16개). 각 패스는 단일 숫자(예: 16진수의 경우 숫자당 4비트)를 기반으로 하며, 최상위 숫자부터 시작한다. 그런 다음 각 빈은 모든 숫자가 정렬에 사용될 때까지 다음 숫자를 사용하여 재귀적으로 처리된다.[9][10]
위에서 설명한 제자리 이진 기수 정렬이나 n-비트 기수 정렬은 안정적인 알고리즘이 아니다.
6. 2. Stable MSD 기수 정렬
MSD 기수 정렬은 안정적인 알고리즘으로 구현될 수 있지만, 입력 배열과 동일한 크기의 메모리 버퍼를 사용해야 한다. 이 추가 메모리를 통해 입력 버퍼를 첫 번째 배열 요소부터 마지막 요소까지 스캔하여 배열 요소를 동일한 순서로 대상 빈(bin)으로 이동할 수 있다. 따라서 동일한 요소는 입력 배열과 동일한 순서로 메모리 버퍼에 배치된다.[11] MSD 기반 알고리즘은 재귀의 첫 번째 레벨에서는 추가 메모리 버퍼를 출력으로 사용하지만, 다음 재귀 레벨에서는 입력과 출력을 바꿔 출력 결과를 다시 입력 버퍼로 복사하는 오버헤드를 피한다.[11] 각 빈은 제자리 MSD 기수 정렬에서 수행되는 것처럼 재귀적으로 처리된다.[11] 마지막 자릿수 정렬이 완료된 후, 출력 버퍼가 원래 입력 배열인지 확인하고 그렇지 않은 경우 한 번의 복사를 수행한다.[11] 자릿수 크기를 키 크기를 자릿수 크기로 나눈 값이 짝수가 되도록 선택하면 마지막 복사를 피할 수 있다.[11]6. 3. Hybrid 접근 방식
기수 정렬은 각 재귀 단계의 첫 번째 단계에서 계수 정렬을 사용하는 2-패스 방식과 같이 큰 상수 오버헤드를 갖는다.[1] 따라서 버킷의 크기가 작아지면 삽입 정렬과 같은 다른 정렬 알고리즘을 사용해야 한다.[1] 삽입 정렬의 좋은 구현은 작은 배열에 대해 빠르고, 안정적이며, 제자리 정렬이 가능하며, 기수 정렬의 속도를 크게 향상시킬 수 있다.[1]7. 병렬 컴퓨팅 응용
이 재귀 정렬 알고리즘은 각 버킷을 독립적으로 정렬할 수 있으므로 병렬 컴퓨팅에 특히 유용하다.[12] 이 경우 각 버킷은 사용 가능한 다음 프로세서로 전달된다. 단일 프로세서는 시작 시(가장 중요한 숫자) 사용된다. 두 번째 또는 세 번째 숫자까지 모든 사용 가능한 프로세서가 참여할 가능성이 높다. 이상적으로, 각 하위 분할이 완전히 정렬됨에 따라 더 적은 수의 프로세서가 활용된다. 최악의 경우, 모든 키가 서로 동일하거나 거의 동일하여 키를 정렬하는 데 병렬 컴퓨팅을 사용하는 데 이점이 거의 또는 전혀 없을 것이다.
재귀의 최상위 레벨에서 병렬 처리 기회는 알고리즘의 계수 정렬 부분에 있다. 계수는 고도로 병렬적이며 parallel_reduce 패턴에 적합하며 메모리 대역폭 한계에 도달할 때까지 여러 코어에서 작업을 잘 분할한다. 이 알고리즘 부분에는 데이터 독립적인 병렬 처리가 있다. 그러나 후속 재귀 레벨에서 각 버킷을 처리하는 것은 데이터 종속적이다. 예를 들어, 모든 키가 동일한 값을 갖는 경우, 요소가 있는 버킷이 하나만 있고 병렬 처리가 불가능하다. 임의 입력의 경우 모든 버킷이 거의 동일하게 채워지고 많은 양의 병렬 처리 기회를 얻을 수 있다.[12]
더 빠른 병렬 정렬 알고리즘을 사용할 수 있다. 예를 들어, 최적 복잡도 O(log(''n''))는 세 명의 헝가리인과 리처드 콜[13][14]의 알고리즘이고, 배처의 비토닉 병합 정렬은 O(log2(''n''))의 알고리즘 복잡도를 갖는데, 이는 모두 CREW-PRAM에서 기수 정렬보다 낮은 알고리즘 시간 복잡도를 갖는다. 가장 빠른 알려진 PRAM 정렬은 1991년 데이비드 M. W. 파워스에 의해 설명되었으며, 분할을 암시적으로 수행하여 ''n''개의 프로세서가 있는 CRCW-PRAM에서 O(log(n)) 시간에 작동할 수 있는 병렬화된 퀵 정렬과 동일한 트릭을 사용하여 O(''k'')에 작동하는 기수 정렬이 있는데, 여기서 ''k''는 최대 키 길이이다.[15] 그러나 PRAM 아키텍처나 단일 순차 프로세서 모두 사이클당 증가하는 상수 팬아웃 게이트 지연 수가 O(log(''n'')) 없이 실제로 확장 가능한 방식으로 구축될 수 없으므로, 실제로 배처의 비토닉 병합 정렬의 파이프라인 버전과 O(log(''n'')) PRAM 정렬은 모두 클럭 사이클 측면에서 O(log2(''n''))이며, 파워스는 배처의 것이 그의 병렬 퀵 정렬 및 기수 정렬 또는 콜의 병합 정렬보다 게이트 지연 측면에서 더 낮은 상수를 가질 것이라고 인정한다. 키 길이 독립적인 정렬 네트워크 O(nlog2(''n''))의 경우 말이다.[16]
8. 트리 기반 기수 정렬
기수 정렬은 입력 집합으로부터 트리(또는 기수 트리)를 구성하고, 전위 순회를 수행하여 구현할 수도 있다. 이는 힙 정렬과 힙 자료 구조의 관계와 유사하다. 이는 특정 데이터 유형에 유용할 수 있으며, 버스트 정렬을 참조하라.
9. 응용
컴퓨터 내부에서는 어떤 데이터도 이진법이므로, 이를 그대로 이용하여 2진 또는 2n진 기수 정렬을 할 수 있다.[18]
음수를 포함하는 일반적인 정수의 경우 (부호 있는 수 표현 참조), 각 표현마다의 성질에 따라 약간의 주의가 필요하지만, 기본적인 부분은 동일하게 수행할 수 있다.
부동소수점 형식에서는, 표준 규격 IEEE 754 형식의 경우 float a, b가 주어졌을 때, a>b>0이면 *(int*)&a>*(int*)&b가 되므로, 지수 부분과 가수 부분으로 나눌 필요도, 정수로 근사할 필요도 없다. 임의의 부동소수점 형식의 경우에는, 적당한 팩터를 곱하여 정수로 근사한 후 기수 정렬을 적용한 후, 원래 값을 버블 정렬 등으로 정렬하거나, 내부 표현을 지수부·가수부로 나누고, 지수부를 가수부의 상위 키로 하여 기수 정렬을 수행한다(수치의 내부 표현 형식에 의존한다).
컴퓨터 이외의 응용으로는, 주변부에 구멍이 뚫린 종이 카드, 구멍 바깥쪽 부분을 정보에 따라 잘라낸 것(펀치 카드#핸드 소트 펀치 카드)의 정렬 방법이 있다. 이는 전자식 컴퓨터가 탄생하기 전부터 있었던 방법이다. 구멍에 꼬챙이를 통과시켜 들어 올리면, 그 구멍 부분을 잘라낸 카드가 남고, 잘라내지 않은 카드가 골라진다. 그렇게 골라낸 카드를 한쪽으로 모은다. 이진법의 아래 자릿수부터 이 조작을 반복하면 기수 정렬이 된다.
참조
[1]
특허
[1]
특허
[2]
서적
The Art of Computer Programming
Addison-Wesley
[3]
웹사이트
I Wrote a Faster Sorting Algorithm
https://probablydanc[...]
2016-12-28
[4]
웹사이트
Is radix sort faster than quicksort for integer arrays?
https://erik.gorset.[...]
[5]
웹사이트
Function template integer_sort - 1.62.0
https://www.boost.or[...]
[6]
웹사이트
Efficient Trie-Based Sorting of Large Sets of Strings
https://citeseerx.is[...]
2023-08-24
[7]
간행물
Algorithms in C++
[8]
웹사이트
Algorithm Improvement through Performance Measurement: Part 2
http://www.drdobbs.c[...]
[9]
웹사이트
Algorithm Improvement through Performance Measurement: Part 3
http://www.drdobbs.c[...]
[10]
웹사이트
Parallel In-Place Radix Sort Simplified
http://www.drdobbs.c[...]
[11]
웹사이트
Algorithm Improvement through Performance Measurement: Part 4
http://www.drdobbs.c[...]
[12]
웹사이트
Parallel In-Place N-bit-Radix Sort
http://www.drdobbs.c[...]
[13]
서적
Efficient Parallel Algorithms
Cambridge University Press
[14]
서적
Parallel Algorithms
Chapman & Hall
[15]
간행물
Parallelized Quicksort and Radixsort with Optimal Speedup
https://sites.cs.ucs[...]
Proceedings of International Conference on Parallel Computing Technologies
[16]
간행물
Parallel Unification: Practical Complexity
http://david.wardpow[...]
Australasian Computer Architecture Workshop
1995-01
[17]
문서
[18]
서적
C言語による最新アルゴリズム事典
技術評論社
[19]
특허
[19]
특허
[20]
서적
The Art of Computer Programming
Addison-Wesley
[21]
웹인용
I Wrote a Faster Sorting Algorithm
https://probablydanc[...]
2016-12-28
[22]
웹인용
Is radix sort faster than quicksort for integer arrays?
https://erik.gorset.[...]
[23]
웹인용
Function template integer_sort - 1.62.0
https://www.boost.or[...]
[24]
웹인용
Efficient Trie-Based Sorting of Large Sets of Strings
http://goanna.cs.rmi[...]
2020-09-04
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com