Стабилизация стандартной библиотеки qsort? - PullRequest
Новая
       25

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

15 голосов
/ 25 февраля 2009

Я предполагаю, что старая старая функция 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;
    }
}

Ответы [ 3 ]

29 голосов
/ 25 февраля 2009

Нет, на это нельзя рассчитывать, к сожалению. Предположим, у вас есть массив (два поля в каждой записи, используемые для проверки, но только первое поле, используемое для сортировки): 

BBBB,1
BBBB,2
AAAA,3

Быстрая сортировка может сравнить 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 в процессе сортировки.

7 голосов
/ 24 мая 2011

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

0 голосов
/ 22 июня 2017

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