Ổn định qsort thư viện chuẩn?

Question

Tôi giả định rằng chức năng qsort cũ tốt trong stdlib không ổn định, bởi vì trang người đàn ông không nói gì về nó. Đây là hàm tôi đang nói về:

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

Tôi giả sử rằng nếu tôi thay đổi hàm so sánh cũng bao gồm địa chỉ mà tôi so sánh, nó sẽ ổn định. Đúng không?

Ví dụ:

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; 
    } 
} 

Answer 1

Không, bạn không thể dựa vào mà không may. Giả sử bạn có mảng (hai trường trong mỗi bản ghi được sử dụng để kiểm tra nhưng chỉ trường đầu tiên được sử dụng để sắp xếp):

BBBB,1 
BBBB,2 
AAAA,3 

Sắp xếp nhanh có thể so sánh BBBB, 1 với AAAA, 3 và trao đổi chúng, đưa ra:

AAAA,3 
BBBB,2 
BBBB,1 

Nếu bước tiếp theo là so sánh BBBB, 2 với BBBB, 1, các phím sẽ giống nhau và vì BBBB, 2 có địa chỉ nhỏ hơn BBBB, 1, sẽ không xảy ra hoán đổi. Đối với một loại ổn định, bạn nên đã kết thúc với:

AAAA,3 
BBBB,1 
BBBB,2 

Cách duy nhất để làm điều đó sẽ được gắn bắt đầu địa chỉ của con trỏ (không hiện địa chỉ của nó) và sắp xếp sử dụng đó như cũng như các phím khác. Bằng cách đó, địa chỉ ban đầu trở thành phần nhỏ của khóa sắp xếp sao cho số BBBB,1 cuối cùng sẽ kết thúc trước BBBB,2 bất kể hai dòng BBBB đi trong quá trình sắp xếp.

Answer 2

Giải pháp kinh điển là để thực hiện (ví dụ: phân bổ bộ nhớ cho và điền vào) một mảng của con trỏ đến các phần tử của mảng ban đầu, và qsort mảng mới này, sử dụng một cấp thêm về mình và té ngửa ra so sánh con trỏ giá trị khi những thứ họ trỏ đến bằng nhau. Cách tiếp cận này có lợi ích bên tiềm năng là bạn không sửa đổi mảng ban đầu chút nào - nhưng nếu bạn muốn mảng ban đầu được sắp xếp ở cuối, bạn sẽ phải hoán đổi nó để khớp với thứ tự trong mảng con trỏ sau qsort trả về.

Answer 3

Điều này không hoạt động vì trong quá trình sắp xếp, thứ tự sẽ thay đổi và hai phần tử sẽ không có đầu ra nhất quán. Những gì tôi làm để thực hiện tốt ổn định qsort cũ là thêm chỉ số ban đầu bên trong cấu trúc của tôi và khởi tạo giá trị đó trước khi chuyển nó sang 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); 
}