CODEWITHSUNDEEP
sorting
ksm001
ksm001

Reputation: 4022

Efficiently sort an array of integers when having extra information about the final sorted array

Suppose we have this array of integers called data

 3
 2
 4
 5
 2

Also we have the following array of the same size called info

 1
 4
 0
 2
 3

Each value of info represents an index on the first array. So for example the first value is 1 which means that in position 0 the final sorted array will have the value data[info[0]].

By following this logic the final sorted array will be the following:

data[info[0]] => 2
data[info[1]] => 2
data[info[2]] => 3
data[info[3]] => 4
data[info[4]] => 5

I would like to make an in place sorting of the data array, without using any extra memory of size N where N is the size of the data array. In addition I would like the amount of total operations to be as small as possible.

I've been trying to think of a solution to my problem however I couldn't think of anything that wouldn't use extra memory. Keep in mind that these are my own restrictions for a system that I'm implementing, if these restrictions can't be kept then I will probably have to think of something else.

Any ideas would be appreciated.

Thank you in advance

Upvotes: 0

Views: 122

Answers (2)

Will Ness
Will Ness

Reputation: 71099

why not simply

for i in 0..n-1 : 
   info[i] := data[info[i]]

and info now holds the sorted array. If it must be in data, just copy it back, next: 

for i in 0..n-1 : 
    data[i] := info[i]

2*n copies, overall.

Upvotes: 2

Daniel Fischer
Daniel Fischer

Reputation: 183968

If the info array need not remain intact, you can use that as additional storage and sort in O(n):

for(int i = 0; i < n; ++i) {
    int where = info[i];
    if (where == i) continue;
    info[i] = data[i];
    data[i] = i < where ? data[where] : info[where];
}

If an element of data is already in its correct place, we skip that index. Otherwise, remember the element in the info array, and write the correct element into data, fetching it from data if it comes from a larger index, and from info if it comes from a smaller index.

Of course that simple method requires the types of the info and data arrays to be the same, and in general does 3*n copies.

If the data elements cannot be stored in the info array, we can follow the cycles in info:

for(int i = 0; i < n; ++i) {
    // Check if this is already in the right place, if so mark as done
    if (info[i] == i) info[i] = -1;

    // Nothing to do if we already treated this index
    if (info[i] < 0) continue;

    // New cycle we haven't treated yet
    Stuff temp = data[i];    // remember value
    int j = info[i], k = i;
    while(j != i) {
        // copy the right value into data[k]
        data[k] = data[j];
        // mark index k as done
        info[k] = -1;
        // get next indices
        k = j;
        j = info[j];
    }
    // Now close the cycle
    data[k] = temp;
    info[k] = -1;
}

That does n - F + C copies of data elements, where F is the number of elements that already were in the right place (fixed points of the sorting permutation) and C is the number of cycles of length > 1 in the sorting permutation. That means the number of copies is at most 3*n/2.

Upvotes: 1

Related Questions