Efficient sorting with custom mapping but no callback function

Question

I need an efficient sort that doesn't have a callback, but is just as customizable as using qsort (). I want it to work as an iterator, where it continuously calls the sort API in a loop until it completes, doing the comparison in a loop, and not turning off the callback function. Thus, the user comparison is local to the calling function (and therefore has access to local variables, potentially more efficiently, etc.). I implemented this for inefficient sorting, but it needs to be efficient, so prefer quick derivative sorting.

Has anyone done something like this? I tried to do this for quick sorting, but trying to turn the algorithm from the inside damaged my brain too much.

Below is an example of use.

// 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 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

Take the existing qsort implementation and update it to reference the Sorter object for your local variables. Instead of calling the comparison function passed to it, it will update its state and return to the caller.

- qsort - Sorter. , ( ). QSort QSort , , 2 .

Answer 2

, , , . .

, , . n- , , . qsort , , .

, , qsort , , . .

Answer 3

inlineble inlineble compare. , , . , , , - . , , .

, , . , . , . , , .

, STB (https://github.com/nothings/stb). , , C.

Answer 4

What you ask is already done - it is called std::sort, and it is already in the C ++ standard library. Better support for this (among many other things) is part of why well-written C ++ is usually faster than C.

Answer 5

You can write a preprocessor macro to display the sort subroutine, and a macro is a comparison expression as an argument.

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