비교를 수정하여 qsort를 안정되게 만드시겠습니까?

Question

가능한 중복 :
Stabilizing the standard library qsort?

그냥 내 빌려 영업을 수정하여의 int에 대한 qsort가 안정적으로 만들 수 있습니까? 그게 내 코드 야. 나는 이것을 약 5-7 크기의 아주 작은 배열에 사용하고 있습니다.

static int compare(const void *a, const void *b) 
{ 
    const int A(*(const int*)(a)); 
    const int B(*(const int*)(b)); 

    return B - A; 
} 

Answer 1

당신이 C++를 사용하는 경우, stable_sort 기능은 안정적이고 (nlogn) 성능 O를 가지고있다.

그렇지 않으면 in-place quicksort가 그 본질 상 불안정합니다 (저는 그렇게 믿습니다). 그러나 여분의 배열을 사용하여 정보를 저장하는 간단한 변형은 안정적입니다. 한 번 나는 내 컴퓨터에 입력 경우에 qsort() 및 stable_sort()에 의해 생성 된 결과가 다른 것을 발견하기 때문에

나는 불안정 qsort() 중 하나 이상 버전을 사용했습니다.

Answer 2

quicksort와 같은 불안정한 정렬 알고리즘을 사용할 수 없으며 비교 연산자를 변경하여 안정화 할 수 없습니다. 안정적인 정렬 알고리즘을 사용하여 을으로 시작해야합니다. 그런 다음 비교는 중요하지 않습니다 (C++의 약한 순서가 엄격한 한).

Answer 3

정렬하려는 배열이 너무 작 으면 다른 정렬 알고리즘을 사용하는 것이 좋습니다. 예 : 답변 : Fast stable sort for small arrays (under 32 or 64 elements) 및 Fast algorithm implementation to sort very small list.