Стабилизация стандартной библиотеки qsort?

Я предполагаю, что хорошая старая функция qsort в stdlib нестабильна, потому что в man-странице ничего не говорится об этом. Это функция, о которой я говорю:

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

Ответы

Ответ 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 во время процесса сортировки.

Ответ 2

Каноническое решение состоит в том, чтобы сделать (т.е. выделить память и заполнить) массив указателей на элементы исходного массива и qsort этот новый массив, используя дополнительный уровень косвенности и вернуться к сравнению значений указателя когда вещи, на которые они указывают, равны. Этот подход имеет потенциальную выгоду, так как вы не изменяете исходный массив вообще, но если вы хотите, чтобы исходный массив был отсортирован в конце, вам придется переставить его в соответствии с порядком в массиве указателей после qsort возвращает.

Ответ 3

Это не работает, потому что во время процедуры сортировки порядок будет изменяться, а два элемента не будут иметь согласованного вывода. То, что я делаю для создания старомодной стабильной 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);
}