QSORT(3)

명칭
qsort, heapsort, mergesort - 정렬 함수

프로그램 라이브러리
libc

서식
#include <stdlib.h> void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) int heapsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) int mergesort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))

해설
qsort() 함수는, 파티션 교환 정렬의 수정판, 듯 하는에 퀵 소트입니다. heapsort() 함수는, 선택 정렬의 수정판입니다. mergesort() 함수는, 이미 줄지어 있는 개소가 있는 데이터를 정렬 하는, 지수 검색에 의한 merge 정렬의 수정판입니다.

qsort() 함수와 heapsort() 함수는, base 에 의해 초기 멤버가 가리켜지고 있다 nmemb 오브젝트의 배열을 정렬 합니다. 각 오브젝트의 사이즈는, size 그리고 지정합니다. mergesort() 도 똑같이 동작합니다만, size 하 “sizeof(void *) / 2” 보다 크지 않으면 안됩니다.

배열 base 의 내용은, compar 하지만 가리키는 비교 함수에 따라 승순으로 정렬 됩니다. 이 함수에서는, 비교하는 오브젝트를 가리키는, 2 개의 인수가 필요합니다.

비교 함수는, 최초의 인수가 다음의 인수보다 작은 경우는 0 보다 작은 정수, 동일한 경우는 0, 큰 경우는 0 보다 큰 정수를 되돌릴 필요가 있습니다.

qsort() 함수와 heapsort() 함수는 불안정합니다. 즉 2 개의 멤버가 동일한 경우, 정렬가 끝난 배열내에서의 순서는 부정이 됩니다. mergesort() 함수는 안정입니다.

qsort() 함수는, 파티션 교환 정렬의 일종인, C.A.R. Hoare 의 ``퀵 정렬''알고리즘을 실장하고 있습니다. 특히 D.E. Knuth 의 알고리즘 Q 를 참조해 주세요. qsort() 에는, 평균으로 O N lg N 의 시간이 걸립니다. 이 실장에서는, 메디안 선택을 사용해, O N**2 라고 한다 최악의 케이스의 동작을 회피합니다.

heapsort() 함수는, 선택 정렬의 일종인, J.W.J. William 의 ``heap soft''알고리즘을 실장하고 있습니다. 특히 D.E. Knuth 의 알고리즘 H 를 참조해 주세요. heapsort() 에는, 최악의 케이스로 O N lg N 의 시간이 걸립니다. 메모리를 거의 여분으로 사용하지 않는다고 하는 점만이 qsort() 보다 우수합니다. 한편, qsort() (은)는 메모리를 할당하지 않습니다만, 재귀를 사용해 실장되고 있습니다.

mergesort() 함수에서는, nmemb * size 바이트의 메모리가 여분으로 필요합니다. 스페이스에 여유가 있는 경우에만 사용해 주세요. mergesort() (은)는, 이미 줄지어 있는 개소가 있는 데이터를 취급하도록(듯이) 최적화되고 있습니다. 최악의 케이스의 시간은 O N lg N 로, 최선의 케이스는 O N 입니다.

통상은, heapsort() 보다 mergesort() (분)편이 빠르고, mergesort() 보다 qsort() (분)편이 고속으로. 사용할 수 있는 메모리량이나 이미 줄지어 있는 데이터량에 의해, 이 상황은 변화합니다.

반환값
qsort() 함수는 값을 되돌리지 않습니다.

에러
heapsort() 함수와 mergesort() 함수는, 이하와 같은 경우에 에러가 됩니다.

[EINVAL]
    size 인수가 0 인지, mergesort() 의 size 인수가 “sizeof void * / 2” 보다 작은 경우.

[ENOMEM]
    heapsort() 인가 mergesort() 하지만 메모리를 할당할 수 없었던 경우.

호환성
구버젼의 qsort() 그럼, 비교 routine가 qsort(3) (을)를 호출할 수 없었습니다. 현재는 호출할 수 있습니다.

관련 항목
sort(1), radixsort(3) Hoare, C.A.R., 1962, Quicksort, The Computer Journal, 5:1, pp. 10-15. Williams, J.W.J, 1964, Heapsort, Communications of the ACM, 7:1, pp. 347-348. Knuth, D.E., 1968, The Art of Computer Programming, Vol. 3, Sorting and Searching, pp. 114-123, 145-149. Mcilroy, P.M., Optimistic Sorting and Information Theoretic Complexity, Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992. Bentley, J.L., Engineering a Sort Function, bentley@research.att.com, January 1992.

표준
qsort() 함수는, isoC 에 적합하고 있습니다.