Make qsort stable just by modifying comparison?

Question

Possible Duplicate:
Stabilizing the standard library qsort?

Is it possible to make qsort stable for ints just by modifying my comp op? That's my code. I'm using this on really small arrays of around 5-7 of size.

static int compare( const void *a, const void *b )
{
    const int A(*(const int*)(a));
    const int B(*(const int*)(b));

    return B - A;
}

If your `int`s are of "reasonable" size and no overflow may happen - yes. — valdo, Apr 23 '12 at 20:16
@valdo: Are you sure you've understood the question? You think the C standard library function qsort() is a stable sort? Got any reference for that? — John Zwinck, Apr 23 '12 at 20:19
Why do you care if your sorting algorithm is stable when your data is just plain integers? Stability only matters if you have distinguishable elements which compare as equal. — Adam Rosenfield, Apr 23 '12 at 20:22
The answer is "no". I'd post this as an answer rather than a comment, but I can't even imagine how you could possibly think this might work, so I'm not sure what I would need to explain to convince you that it doesn't. — David Schwartz, Apr 23 '12 at 20:22

zw324 · Accepted Answer · 2012-04-23T20:26:39.143

If you are using C++, the stable_sort function is stable and have O(nlogn) performance.

Otherwise, in-place quicksort is by its nature, unstable (I believe so). The trivial variant that use an extra array to store information is stable, however.

I've used at least one version of qsort() that is unstable, because once I found that the result produced by qsort() and stable_sort() for a input case on my machine were different.

score 2 · Answer 2 · answered Apr 23 '12 at 20:24

2

You can't take an unstable sorting algorithm such as quicksort and make it stable just by changing the comparison operator. You have to start with a stable sorting algorithm, and then the comparison doesn't matter (as long as it's strict weak ordering in C++).

answered Apr 23 '12 at 20:24

Mark B

95,107
10
109
188

4

You can build a stable sort on top of an unstable one by constructing an array of pointers to the original elements, and sorting the array of pointers instead, with ties broken by pointer comparison. – R.. GitHub STOP HELPING ICE Apr 23 '12 at 23:26

score 0 · Answer 3 · edited May 23 '17 at 10:34

0

If the arrays that you're sorting really are all that small, then you might be better off using another sort algorithm. See e.g. the answers to : Fast stable sort for small arrays (under 32 or 64 elements) and Fast algorithm implementation to sort very small list.

edited May 23 '17 at 10:34

Community

1
1

answered Apr 23 '12 at 20:44

Edward Loper

15,374
7
43
52

Make qsort stable just by modifying comparison?

3 Answers3