Search code examples
csortingqsortstable-sort

How to leave ordering unchanged on equality using qsort

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.

Solution

  • 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)).