استقرار مكتبة القياسية Qsort؟

Question

أفترض أن وظيفة QSort القديمة الجيدة في Stdlib ليست مستقرة، لأن صفحة الرجل لا تقول شيئا عن ذلك. هذه هي الوظيفة التي أتحدث عنها:

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

Answer 1

لا، لا يمكنك الاعتماد على ذلك لسوء الحظ. دعونا نفترض أن لديك مجموعة صفيف (حقلين في كل سجل يستخدم للتحقق ولكن الحقل الأول فقط المستخدم للفرز):

BBBB,1
BBBB,2
AAAA,3

قد تقارن QuickSort BBBB، 1 مع AAAA، 3 وتبادلها، إعطاء:

AAAA,3
BBBB,2
BBBB,1

إذا كانت الخطوة التالية كانت مقارنة BBBB، 2 مع BBBB، 1، ستكون المفاتيح هي نفسها، ومنذ، نظرا لأن BBBB، 2 لديه عنوان أقل من BBBB، 1، لن يحدث أي مبادلة. لسبب مستقر، يجب أن تكون قد انتهت مع:

AAAA,3
BBBB,1
BBBB,2

الطريقة الوحيدة للقيام بذلك ستكون هي إرفاق بدءا عنوان المؤشر (وليس لها حاضر العنوان) والفرز باستخدام ذلك وكذلك المفاتيح الأخرى. بهذه الطريقة، يصبح العنوان الأصلي جزءا بسيطا من المفتاح الفرز بحيث BBBB,1 سوف ينتهي في نهاية المطاف من قبل BBBB,2 بغض النظر عن مكانين BBBB خطوط تذهب خلال عملية الفرز.

Answer 2

الحل الكنسي هو جعل (أي تخصيص الذاكرة وملء) مجموعة من المؤشرات إلى عناصر الصفيف الأصلي، و qsort هذه المجموعة الجديدة، باستخدام مستوى إضافي من عدم الإنذار والعودة إلى مقارنة المؤشر القيم عندما تكون الأشياء التي يشيرون إليها متساوون. يحتوي هذا النهج على المنفعة الجانبية المحتملة أنك لا تعدل الصفيف الأصلي على الإطلاق - ولكن إذا كنت تريد فرز الصفيف الأصلي في النهاية، فسيتعين عليك السماح لها بمطابقة الطلب في صفيف المؤشرات بعد qsort عائدات.

Answer 3

هذا لا يعمل لأنه أثناء إجراء الفرز، سيتغير الطلب ولن يتمتع عنصران بإخراج متسق. ما أقوم به لجعل QSort STable جيدة من الطراز القديم هو إضافة الفهرس الأولي داخل بنية وتهيئة هذه القيمة قبل اجتيازها إلى 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);
}