Стабилизация стандартной библиотеки qsort?
-
06-09-2019 - |
Вопрос
Я предполагаю, что старая добрая функция 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;
}
}
Решение
Нет, к сожалению, вы не можете полагаться на это.Предположим, у вас есть массив (два поля в каждой записи используются для проверки, но только первое поле используется для сортировки).:
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
строки перемещаются во время процесса сортировки.
Другие советы
Каноническое решение состоит в том, чтобы сделать (т.е.выделить память для и заполнить) массив указателей на элементы исходного массива, и 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);
}