quicksort (n arrays should be treated as 1 and values remapped as needed)

I have a linked list of arrays (struct at bottom of post)

Each array may have values like the below example

Array1[] = {6,36,8,23};
Array2[] = {8,23,5,73};
Array3[] = {2,5,1,9};

I need to sort these so that all 3 arrays are treated as 1 large array...

I need to use quicksort so that it uses in-place processing... I am working with very large arrays and cannot afford to use additional memory..

The result should be something like this

Array1[] = {1,2,5,5};
Array2[] = {6,8,8,9};
Array3[] = {23,23,36,73};

Currently i am only 开发者_JAVA百科able to sort each array individually... but thats not exactly what i need :(

struct iSection {
    unsigned long     Section_Count; // Total # of points in this block of memory

    int              *Section_Arr;   // Point cloud for current block of memory
    struct iSection  *Next;          // Pointer to next section
} iSection;


struct iDatabase {
    struct iSection     *First_Section;
    struct iSection     *Last_Section;
} iDatabase;

It's not that hard, more an interfacing issue then an algorithmics issue.

Write a wrapper container that provides an interface for accessing members and writing (say operator[] in C++) and internally it maps the size_t index argument to the right array. This wrapper class does need the size of every array though to be able to correctly map the index.

An example pseudocode operator[] would be:

int& JointDatabase::operator[](size_t index) {
    // database is an iDatabase
    iSection *cur = database.First_Section;

    while (cur != database.Last_Section && index >= cur->Section_Count) {
        index -= cur->Section_Count;
        cur = cur->Next;
    }

    return cur->Section_Arr[index];
}

Then use this wrapper class as you would use a normal container in your Quicksort algorith.

If you can make sure that Array1, Array2, and Array3 are declared one after another and in continuous memory layout, then you can give the Array1 (the first one) in the sort() and give the combined size of all the arrays.

To check the continuous alignment you can use following trick.

template<size_t SIZE1, size_t SIZE2, size_t SIZE3>
bool Check(int (&a1)[SIZE1], int (&a2)[SIZE2], int (&a3)[SIZE3])
{
  return (&a3[SIZE3 - 1] - &a1[0]) == (SIZE1 + SIZE2 + SIZE3);
}

Usage,

bool aligned = Check(Array1, Array2, Array3);

This is an example for 3 arrays, you can make it according to your need. And you can pass Array1,2,3 or Array3,2,1 depending on your machine.

Tested only in my brain:

struct ArrayWrapper {
    int** arrays;
    int* running_sums;
    ArrayWrapper(int **arrays, int *arrays_length, int N) {
        running_sums = new int*[N+1];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            running_sums[i+1] = sum;
            sum += arrays_length[i];
        }
    }
    int& operator[] (int index) {
        int array_start = binary search `running_sum` for the closest number to `index` (round down)
        return arrays[array_start][index - running_sums[array_start]]
    }
}

so if you have something like:

array1 = {...} 
array2 = {...}
...
arrayN = {...}

arrays = {array1, array2, ..., arrayN}
arrays_length = {array1_length, array2_length, ..., arrayN_length}

ArrayWrapper wrapper = new ArrayWrapper(arrays, arrays_length, N);
// wrapper then can be treated like normal array:
wrapper[10] = x;
x = wrapper[10];