CODEWITHSUNDEEP
carrayssorting
Kean
Kean

Reputation: 602

Can quicksort be used with multiple arrays?

I have a high performance, wait-free vector implementation in C that allows me to index the array linearly, but is implemented using multiple arrays under the hood. Now I need to sort this vector. Obviously I cannot use the qsort() standard function because the array isn't a single blob of memory.

Although it is not implemented thus, pretend that a 60 slot vector was defined as:

struct vector {
  int *buckets[4];
};

struct vector v;
v.buckets[0] = calloc(4, sizeof (int));
v.buckets[1] = calloc(8, sizeof (int));
v.buckets[2] = calloc(16, sizeof (int));
v.buckets[3] = calloc(32, sizeof (int));

I have a simple inline function that can turn a given index value in the range 0 to 59 (for example getval(8) would return buckets[1][4] and getval(9) would return buckets[1][5] etc.

So, although the vector can be indexed linearly, it is not stored linearly. Can quicksort be adapted to sort this vector? If not, any other sorting algorithms I should look at?

Upvotes: 3

Views: 1206

Answers (2)

chqrlie
chqrlie

Reputation: 144780

qsort is not appropriate for your problem as it requires an array of elements. You could use it to sort each of the subarrays, but you would still need a way to merge these in place in your vector structure. radix sort is not directly applicable either.

Apart from the above and much less efficient methods such as insertion and bubble sort, most efficient sort methods require some extra space proportional to the size of the data set. If you are going to allocate potentially large amounts of space, the easiest method seems to allocate a separate array, copy the contents to it, sort it with radix_sort, qsort or any other method and copy the sorted contents back to the original vector structure.

Upvotes: 1

melpomene
melpomene

Reputation: 85767

As long as you have the equivalent of getval(index) and setval(index, value), pretty much any sorting algorithm (including quicksort) will work.

However, you can't use qsort from the standard library because that requires contiguous data. So you have to either code your own sort function or introduce a level of indirection, e.g. by creating an array of indices, sorting it using qsort, then applying the resulting reordering of indices to the underlying array storage.

Upvotes: 6

Related Questions