표준 라이브러리 QSORT를 안정화합니까?

StackOverflow https://stackoverflow.com/questions/584683

  •  06-09-2019
  •  | 
  •  

문제

나는 Man Page가 그것에 대해 아무 말도하지 않기 때문에 stdlib의 좋은 오래된 Qsort 함수는 안정적이지 않다고 가정합니다. 이것은 내가 말하는 기능입니다.

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

비교 기능을 변경하면 비교하는 주소의 주소를 포함 시키면 안정적이라고 가정합니다. 그 맞습니까?

예 :

int compareFoos( const void* pA, const void *pB ) {
    Foo *pFooA = (Foo*) pA;
    Foo *pFooB = (Foo*) pB;

    if( pFooA->id < pFooB->id ) {
        return -1;
    } else if( pFooA->id > pFooB->id ) {
        return 1;
    } else if( pA < pB ) {
        return -1;            
    } else if( pB > pA ) {
       return 1;
    } else {
       return 0;
    }
}
도움이 되었습니까?

해결책

아니, 당신은 불행히도 그것에 의존 할 수 없습니다. 배열이 있다고 가정 해 봅시다 (점검에 사용 된 각 레코드의 2 개의 필드가 있지만 정렬에 사용되는 첫 번째 필드 만) :

BBBB,1
BBBB,2
AAAA,3

QuickSort는 BBBB, 1과 AAAA, 3을 비교하여 다음을 바꿀 수 있습니다.

AAAA,3
BBBB,2
BBBB,1

다음 단계가 BBBB, 2와 BBBB, 1을 비교하는 것이면 키는 동일하며 BBBB는 BBBB보다 작은 주소가 있으므로 스왑이 발생하지 않습니다. 안정적인 종류의 경우, 당신은 다음과 같아야합니다.

AAAA,3
BBBB,1
BBBB,2

그것을 할 수있는 유일한 방법은 시작 포인터의 주소 (그것의 아님 현재의 주소) 및 다른 키뿐만 아니라 다른 키를 사용하십시오. 그렇게하면 원래 주소는 정렬 키의 작은 부분이되어 BBBB,1 결국 전에 끝날 것입니다 BBBB,2 둘이 어디에 있든 BBBB 분류 과정에서 선이 이동합니다.

다른 팁

표준 솔루션은 원래 배열의 요소에 대한 다양한 포인터를 만들고 (예 : 메모리를 할당하고 채우는 것)입니다. qsort 추가 간접 수준을 사용하고 포인터 비교로 돌아가는이 새로운 배열 가치 그들이 가리키는 것들이 평등 할 때. 이 접근법은 원래 배열을 전혀 수정하지 않는 잠재적 인 부수적 이점이 있지만 원래 배열을 마지막에 정렬하려면 후에 포인터 배열의 순서에 맞게 분출해야합니다. qsort 보고.

정렬 절차 중에 순서가 변경되고 두 요소가 일관된 출력을 갖지 않기 때문에 작동하지 않습니다. 구식 QSORT를 안정적으로 만들기 위해 내가하는 일은 구조물 내부의 초기 색인을 추가하고 QSORT에 전달하기 전에 해당 값을 초기화하는 것입니다.

typedef struct __bundle {
    data_t some_data;
    int sort_score;
    size_t init_idx;
} bundle_t;

/*
 .
 .
 .
 .
*/

int bundle_cmp(void *ptr1, void *ptr2) {
    bundle_t *b1, *b2;
    b1 = (budnel_t *) ptr1;
    b2 = (budnel_t *) ptr2;
    if (b1->sort_score < b2->sort_score) {
        return -1;
    }
    if (b1->sort_score > b2->sort_score) {
        return 1;
    }
    if (b1->init_idx < b2->init_idx) {
        return -1;
    }
    if (b1->init_idx > b2->init_idx) {
        return 1;
    }
    return 0;
}

void sort_bundle_arr(bundle_t *b, size_t sz) {
    size_t i;
    for (i = 0; i < sz; i++) {
        b[i]->init_idx = i;
    }
    qsort(b, sz, sizeof(bundle_t), bundle_cmp);
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top