I am allowed to use an extra array to perform a stable quicksort unlike the general quicksort algorithm. I know how to select the pivot at random and partition accordingly but I'm not able to figure out how to make use of the additional array to make it stable.
-
1What is an unstable quicksort?Ed Heal– Ed Heal2015-09-20 02:22:58 +00:00Commented Sep 20, 2015 at 2:22
Add a comment
|
2 Answers
The most trivial way that comes to mind is to store the initial indices in the array (1, 2, 3, etc) and swap them around as you swap the data.
Then in the comparison, if the two elements are equal, compare their indices too, thus making it stable.
3 Comments
R.. GitHub STOP HELPING ICE
Alternatively, don't modify your data in the array at all, but start out by making a new array of pointers to the original array elements. Then simply sort the array of pointers, first comparing the pointed-to object, then comparing pointers as a tie-breaker. This is a nice technique to have since it works for sorting data where the original copy cannot be modified. However if you really do need to reorder the original array, that's an extra (slightly nontrivial) step at the end.
Blindy
Yeah, it's about what you'll use more, the ordered array or the original mapping. I assumed that since you're sorting you'll need the sorted array :)
rcgldr
If using O(n) additional space, a merge sort could be used, and it's already stable. If an array of indices or pointers is to be used, normally two arrays of indices or pointers are used, but a single array of indices or pointers is enough if those indices or pointers are used like a linked list, where each index or pointer points to the next element. The end of each list would be index == -1 or pointer == null. Local variables are used to keep track of the start of lists within the merge algorithm, and a single start of list value is returned by the merge algorithm.
As suggested by Blindy and R, you can sort just the indices, then a variation of cycle sort can be used to sort the original array in place, with the side effect the that the sorted indices will be rearranged back to 0 to n-1. Every move places an element in place, so the time complexity is O(n).
void reorder_according_to(int array[], size_t indices[], size_t len)
{
size_t i, j, k;
int t;
for(i = 0; i < len; i++){
if(i != indices[i]){
t = array[i];
k = i;
while(i != (j = indices[k])){
array[k] = array[j];
indices[k] = k;
k = j;
}
array[k] = t;
indices[k] = k;
}
}
}
5 Comments
R.. GitHub STOP HELPING ICE
For various technical reasons, this function would be better if tweaked to take
TYPE *array, TYPE **pointers, size_t len.R.. GitHub STOP HELPING ICE
Indeed, but it should probably still follow best practices like using
size_t for sizes/indices since int could overflow. :-) Using pointers is more of a technical detail (with the qsort API, you have to sort pointers, not indices, since qsort has no additional context argument to pass thru to the comparison function) but it doesn't matter if you're using this with your own sort that does have a clean way to sort indices.R.. GitHub STOP HELPING ICE
Uhg. In the absence of an explicit contract that you have a limit on the size/number of elements,
size_t is the only correct/safe thing to use. Frustrating that somebody is recommending against that on SO... :-(R.. GitHub STOP HELPING ICE
Nice. I hope you didn't feel like I was badgering you about it. I'd just rather example code on SO either be safely usable as-written or have comments (in the answer or as comments on the answer) reflecting concerns that someone wanting to use the code should address before using it.
rcgldr
In this case, it's not an issue. In X86-X64 64 bit mode, there may be somewhat of a performance advantage using 32 bit unsigned integers versus 64 bit unsigned integers (size_t). Also 32 bit unsigned integers would be able to index an array of size 4 GB, and 4 GB of 64 bit indexes would take 32 GB of memory, plus the size of the array, so from a practical standpoint, size_t isn't helping much, but it might make the example more clear.