-3
stdlib.h에있는 qsort() 함수는 실제로 이름에서 알 수 있듯이 quicksort 알고리즘을 사용합니까?qsort()는 어떤 정렬 알고리즘을 사용합니까?
A
답변
6
qsort() 함수는 라이브러리 구현자가 선택하는 정렬 알고리즘을 사용하여 구현 될 수 있지만 알고리즘의 최적성에 가깝습니다. O (N) 알고리즘을 사용하는 것은 허용되지만 주요 QoI (구현 품질) 문제가 발생합니다.
qsort() 인터페이스를 사용하면 비교가 매우 비쌉니다. 이동 횟수를 줄이기 위해 비교 횟수를 늘리는 정렬 알고리즘 (포인터를 섞지 않으면 비용이 많이들 수 있음)은 성능이 저하 될 수 있습니다. 그러나 이것은 라이브러리 구현자가 관심을 갖는 문제입니다. 라이브러리 구현이 무서운 것을 발견하지 못하면 (요즘은 거의 불가능합니다.) 라이브러리를 사용하고 걱정하지 마십시오.
C++ sort 알고리즘은 C의 qsort 주변에서 링을 실행할 수 있습니다.
+0
+1 많은 구현은 정렬되는 데이터와 그 분석에 따라 혼합 된 알고리즘의 듀오 또는 트리오를 사용합니다. 내가 사용하는 Apple LLVM 4.2 체인 구현은 작은 파티션을위한 버블 정렬을 실제로 구현하는 * 놀라운 구현을 제공합니다 (예를 들어, 14 개 요소보다 작은 슬라이스에 대해 생각합니다. 그러나 반드시 확인해야합니다). 예를 들어 . – WhozCraig
+0
확실히 qsort는 일반적으로 quicksort였습니다. 물론 평균 케이스 O (N log N)이지만 최악 케이스 O (N^2)입니다. 요즘 QoI 문제로 간주 되나요? – Steve314
+0
@WhozCraig 거품 형일까요? 그게 놀랄 것입니다. 일반적인 생각은 삽입 방식이 훨씬 더 효율적이라는 것입니다 ... –
1
C11 표준은 지정하지 않습니다. 그래서 어떤 합리적인 O (n log n)라도 받아 들일 수 있습니다.
반드시 그렇지는 않습니다. 구현 정의입니다. –