사용자:YouKnowOne/기수 정렬
컴퓨터 과학 에서 기수 정렬은 비교 정렬이 아닌 정렬 알고리즘 가운데 하나이다. 기수 에 따라 원소를 만들고 버킷에 배포 하여 비교를 방지합니다. 유효 숫자가 두 개 이상인 요소의 경우 모든 숫자가 고려 될 때까지 이전 단계의 순서를 유지하면서 각 숫자에 대해이 버킷 팅 프로세스가 반복됩니다. 이러한 이유로 기수 정렬 은 버킷 정렬 및 디지털 정렬 이라고도합니다.
기수 정렬은 정수, 단어, 천공 카드, 카드 놀이 또는 메일 과 같이 사전 순 으로 정렬 할 수있는 데이터에 적용 할 수 있습니다.
역사[편집]
기수 정렬의 역사는 1887년 Herman Hollerith가 작표기를 만들 때까지 거슬러 올라간다.[1] 기수 정렬 알고리즘은 이미 1923년에 천공 카드를 분류하는 방법으로 널리 사용되었다.[2]
Harold H. Seward은 1954 년 MIT 에서 최초로 메모리 효율적인 컴퓨터 알고리즘을 개발했다. 이전까지는 알 수 없는 크기의 버킷을 가변 할당해야 한다고 믿었기 때문에 전산화 된 기수 정렬은 비현실적인 것으로 생각되었다. Seward의 혁신은 선형 탐색으로 사용하여 필요한 버킷 크기와 오프셋을 미리 결정하여 보조 메모리에서 단일 정적 할당만 할 수 있도록 하는 것이다. 이 선형 탐색은 Seward의 다른 알고리즘인 계수 정렬과 밀접한 관련이 있다.
현대에는 이진 문자열과 정수 정렬에 가장 널리 적용된다. 일부 벤치마크에서 다른 범용 정렬 알고리즘보다 50%에서 3배까지 빠를 때도 있는 것으로 나타났다[3][4][5].
자리 순서[편집]
기수 정렬은 최상위 유효숫자(MSD)나 최하위 유효숫자(LSD)에서 시작하도록 구현할 수 있다. 예를 들어 1234를 사용하면 하면 1(MSD) 또는 4(LSD)로 시작할 수 있다.
LSD 기수 정렬은 일반적으로 짧은 키가 긴 키보다 먼저 나오고 같은 길이의 키는 사전 순으로 정렬된다. 그 결과는 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 와 같은 정수 표현의 일반적인 순서와 일치한다. LSD 정렬은 일반적으로 안정 정렬이다.
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 정렬은 불안정 정렬이므로 중복 키의 원래 순서를 항상 유지하지는 않는다.
순회 순서 외에 MSD와 LSD 정렬은 가변 길이 입력 처리가 다르다. LSD 정렬은 길이별로 무리지어 각 무리를 기수정렬하고 길이 순서로 무리를 연결할 수 있다. MSD 정렬은 짧은 키를 가장 긴 키의 길이로 확장하고 정렬하는 효과를 가지기 때문에 LSD에서 무리를 구성하는 것보다 더 복잡할 수 있다.
하지만 MSD 정렬은 세분화 및 재귀에 더 적합하다. MSD 정렬의 각 단계에서 만들어진 버킷은 이전 단계에서 만든 다른 버킷을 참조하지 않고 그 안에서 다음 최상위 숫자를 사용하여 기수 정렬을 다시 적용할 수 있습니다. 마지막 숫자에 도달하면 모든 버킷을 연결하면 정렬이 완료된다.
복잡도와 성능[편집]
기수 정렬의 시간복잡도는 O(nw)이다. 여기서 n은 키의 수이고 w는 키의 길이이다. LSD는 위에서 설명한대로 가변 길이 키를 여러 무리로 분할하면 w 에 대한 하한인 '평균 키 길이'를 달성할 수 있다.
적당한 도메인에서 최적화 된 기수 정렬은 매우 빠를 수 있다.[6] 사전식 자료로 제한되기는 하지만 많은 응용에서는 제한이 없는 것이나 마찬가지다. 유도 시행 횟수가 병목이 될 정도로 키 크기가 크면 LSD 구현이 어려워 질 수 있다[2] .
- ↑ US 395781 and UK 327
- ↑ 가 나
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp. 168–179.
인용 오류: 잘못된
<ref>태그; "auto"이 다른 콘텐츠로 여러 번 정의되었습니다 - ↑ “I Wrote a Faster Sorting Algorithm”. 2016년 12월 28일.
- ↑ “Is radix sort faster than quicksort for integer arrays?”. 《erik.gorset.no》.
- ↑ “Function template integer_sort - 1.62.0”. 《www.boost.org》.
- ↑ “Efficient Trie-Based Sorting of Large Sets of Strings” (PDF).
[[분류:정렬 알고리즘]] [[분류:번역이 검토되지 않은 문서]]