эффективная сортировка с пользовательским сравнением, но без функции обратного вызова

Question

Мне нужна эффективная сортировка, которая не имеет обратного вызова, но настраивается так же, как и использование qsort (). Я хочу, чтобы он работал как итератор, где он непрерывно вызывает API-интерфейс сортировки в цикле до тех пор, пока это не будет сделано, выполняя сравнение в цикле, а не в функции обратного вызова. Таким образом, пользовательское сравнение является локальным для вызывающей функции (и, следовательно, имеет доступ к локальным переменным, потенциально более эффективно и т. Д.). Я реализовал это для неэффективной сортировки выбора, но нужно, чтобы она была эффективной, поэтому я предпочитаю быструю сортировку.

Кто-нибудь делал что-нибудь подобное? Я пытался сделать это для быстрой сортировки, но попытка вывернуть алгоритм наизнанку слишком сильно повредила мой мозг.

Ниже показано, как это может выглядеть при использовании.

// the array of data we are sorting
MyData array[5000], *firstP, *secondP;

// (assume data is filled in)

Sorter sorter;

// initialize sorter
int result = sortInit (&sorter, array, 5000,
        (void **)&firstP, (void **)&secondP, sizeof(MyData));

// loop until complete
while (sortIteration (&sorter, result) == 0) {
    // here's where we do the custom comparison...here we
    // just sort by member "value" but we could do anything
    result = firstP->value - secondP->value;
    }

Answer 1

Вывод функции сортировки наизнанку, как вы предлагаете, вряд ли сделает это быстрее. Вы торгуете косвенным обращением в функции сравнения для косвенного обращения в указателях предметов.

Похоже, вы хотите, чтобы ваша функция сравнения имела доступ к информации о состоянии. Быстрый быстрый способ создания глобальных переменных или глобальной структуры, при условии, что у вас не более одного потока, идущего одновременно. Функция qsort не вернется, пока все данные не будут отсортированы, поэтому в однопоточной среде это должно быть безопасно.

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

Answer 2

Простым решением является использование встроенной функции сортировки и встроенного обратного вызова сравнения. При компиляции с оптимизацией оба вызова сливаются друг с другом точно так, как вы хотите. Единственным недостатком является то, что ваш выбор алгоритма сортировки ограничен, потому что, если вы выделите или выделите больше памяти, вы потенциально потеряете какую-либо выгоду от этого. Метод с небольшими издержками, подобный этому, лучше всего работает с небольшим набором данных.

Вы можете использовать универсальную функцию сортировки с методом сравнения, размером, смещением и шагом. Таким образом, пользовательское сравнение может быть выполнено параметром, а не обратным вызовом. Таким образом, вы можете использовать любой алгоритм. Просто используйте макрос для заполнения наиболее распространенного случая, потому что у вас будет много аргументов функции.

Также проверьте библиотеку STB (https://github.com/nothings/stb). Он имеет функцию сортировки, аналогичную этой, среди многих других полезных инструментов на языке С.

Answer 3

Возьмите существующую реализацию qsort и обновите ее, чтобы она ссылалась на объект Sorter для его локальных переменных. Вместо вызова переданной функции сравнения она обновит свое состояние и вернется к вызывающей стороне.

Из-за рекурсии в qsort вам необходимо сохранить какой-либо стек состояний в вашем объекте Sorter. Вы можете сделать это с помощью массива или связанного списка, используя динамическое распределение (менее эффективное). Поскольку большинство реализаций qsort используют хвостовую рекурсию для большей половины и делают рекурсивный вызов qsort для меньшей половины точки поворота, вы можете отсортировать не менее 2 ⁿ элементов, если ваш массив может содержать n состояний. 1005 *

Answer 4

Вы можете написать макрос препроцессора для вывода процедуры сортировки, а макрос взять выражение сравнения в качестве аргумента.

#define GENERATE_SORT(name, type, comparison_expression) \
  void name(type* begin, type* end) \
  { /* ... when needed, fill a and b and use comparison_expression */ }

GENERATE_SORT(sort_ints, (*a<*b))

void foo()
{
    int array[10];
    sort_ints(array, array+10);
}

Answer 5

То, что вы просите, уже сделано - оно называется std::sort и уже находится в стандартной библиотеке C ++. Лучшая поддержка этого (среди прочего) является частью того, почему хорошо написанный C ++, как правило, быстрее, чем C.