RADIXSORT(3)

명칭
radixsort - 기수 정렬

프로그램 라이브러리
libc

서식
<limits.h> <stdlib.h> int radixsort(const unsigned char **base, int nmemb, const unsigned char *table, unsigned endbyte) int sradixsort(const unsigned char **base, int nmemb, const unsigned char *table, unsigned endbyte)

해설
radixsort() 함수와 sradixsort() 함수는, 기수 정렬 (라디크스소트)를 실장하고 있습니다.

이 함수는, 초기 멤버가 base 에 의해 참조되고 있는 바이트 캐릭터 라인에의 포인터의 배열을 정렬 합니다. 바이트 캐릭터 라인에는 임의의 값을 포함할 수 있습니다. 각 캐릭터 라인의 마지막에는, 유저가 정의한 값 endbyte 하지만 붙습니다.

어플리케이션에서는, table 인수를 지정하는 것으로 정렬 순서를 지정할 수 있습니다. NULL (은)는 아니다 table (은)는, 각 바이트치의 정렬 웨이트를 포함한, UCHAR_MAX + 1 바이트의 배열을 참조하고 있을 필요가 있습니다. 캐릭터 라인의 종단 바이트의 정렬 웨이트는, 0 이나 255 (역순정렬)가 아니면 안됩니다. 복수의 바이트의 정렬 웨이트가 동일한 일도 있습니다. table 인수는, 다른 캐릭터를 동일하게 정렬 하는 어플리케이션으로 편리합니다. 예를 들어 A 로부터 Z 의 각각의 웨이트와 a 로부터 z 의 각각의 웨이트를 동일하게 하면(자), 대문자와 소문자의 구별을 하지 않는 정렬가 생깁니다. table 하지만 NULL 인 경우, 배열의 내용은, 참조하는 바이트 캐릭터 라인의 ASCII 순서에 따라 승순에 정렬 됩니다. 이 때, endbyte 의 정렬 웨이트는 0 입니다.

sradixsort() 함수는 안정입니다. 즉, 2 개의 요소가 동일한 경우, 이러한 요소의 순서는 정렬가 끝난 배열에서도 변화하지 않습니다. sradixsort() 함수는, nmemb 포인터를 수용하기에 충분한 메모리를 여분으로 사용합니다.

radixsort() 함수는 불안정합니다만, 메모리를 여분으로 사용하지 않습니다.

이 함수는, 최상정도 바이트 기수 정렬의 일종입니다. D.E. Knuth 의 알고리즘 R 와 섹션 5.2. 5, 엑서사이즈 10 을 참조해 주세요. 이 함수에는, 캐릭터 라인의 바이트수에 비례한 시간이 걸립니다.

반환값

에러

[EINVAL]
    table 의 endbyte 엘리먼트의 값이 0 이나 255 가 되어 있지 않습니다.

sradixsort() 함수는, 에러가 발생하면(자), 프로그램 라이브러리 routine malloc(3) 그리고 지정되어 있는 에러를 errno (으)로 설정하는 일이 있습니다.

관련 항목
sort(1), qsort(3)

Knuth, D.E., 1968, The Art of Computer Programming, Sorting and Searching, Vol. 3, pp. 170-178. Paige, R., 1987, Three Partition Refinement Algorithms, SIAM J. Comput. , Vol. 16, No. 6. McIlroy, P., 1993, Engineering Radix Sort, Computing Systems, Vol. 6:1, pp. 5-27.

역사
radixsort() 함수는, 4.4BSD 에 처음 등장했습니다.