How to leave ordering unchanged on equality using qsort

Question

Straight from the qsort manual it says:

If two members compare as equal, their order in the sorted array is undefined.

However, I want qsort to leave the ordering unchanged on equality. That is to say, leave the ordering of two elements as they are in the original array if they have the same value used for ordering.

I'm not sure how to do this using qsort. I would rather not use an alternative sorting library/ roll my own.

Thanks

--

edit: now I know the distinction between stable and unstable sorts I realise this is a duplicate.

Wishful thinking does not help. Either you accept the constraint, or write your own code. — too honest for this site, Jul 20 '15 at 13:54
I appreciate that, I just wanted to check there wasn't a simple known solution to my problem first. — Andy T, Jul 20 '15 at 13:57

score 3 · Answer 1 · answered Jul 20 '15 at 14:00

You are essentially asking how to implement stable sorting on top of an unstable sort.

There is not much you can do: you only have control over the comparison function, so you'll have to work on that.

One possibility is to attach a second key ID to each element in the array that corresponds to the original index of that element. Then, if two elements compare equal, just return the corresponding order according to their original indexes.

score 3 · Answer 2 · answered Jul 20 '15 at 14:34

As the GNU libc manual explains,

The only way to perform a stable sort with qsort is to first augment the objects with a monotonic counter of some kind.

So unless you can modify your comparison function so that objects you currently consider "equal" may be distinguished, you'll have to explicitly annotate your objects with indices before sorting, and remove the indices when you're done. You could use something like

struct indexed {
    void *obj;
    int index;
}

score 2 · Answer 3 · answered Jul 20 '15 at 13:54

What qsort is telling you here is his algorithm doesn't allow it to guarantee you the resulting sorting order of two equals members.

What you can do is implementing / using another algorithm, or force them to sort the way they was :

If your comparing function shall return equality, look at how they were originally sorted, and sort them the same way.

score 2 · Accepted Answer · answered Jul 20 '15 at 14:17

qsort stands for "Quick Sort", which is a fast but not stable sorting algorithm. Suppose you are sorting in ascending order. In this case, a sorting algorithm is called stable if it won't swap elements that have equal keys. If it may swap elements with equal keys, it is unstable.

There are different solutions to your problem; I'll suggest two of them here.

Solution 1

You may find in Wikipedia some interesting ideas regarding stability of sorting algorithms, including a method for using unstable algorithms when you actually need a stable one: you extend the sorting key: if you are sorting using an integer value, for example.

Suppose you are sorting an array of integers. Instead of that, you create a structure with two elements: the first (KEY) is your integer. The second (AUX_KEY) is a unique index. Before sorting, you linearly set AUX_KEY to reflect the original order. When sorting, pass to qsort a function that will sort using KEY, but will revert to using AUX_KEY if two keys are equal.

Solution 2

Instead of using Quicksort, use a stable algorithm like merge sort, which you probably have in your programming environment (for example, here's the FreeBSD manpage for mergesort; the same may be available in other programming environments under the same name -- please check) or, if you don't need speed too much, use insertion sort (which you can code yourself -- it takes few lines only in pseudocode). Insertion sort takes has quadratic time complexity (takes time proportional to n^2), while mergesort and quicksort have time complexity O(n log(n)).

How to leave ordering unchanged on equality using qsort

4 Answers4