Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is it possible to rearrange an array in place in O(N)?

If I have a size N array of objects, and I have an array of unique numbers in the range 1...N, is there any algorithm to rearrange the object array in-place in the order specified by the list of numbers, and yet do this in O(N) time?

Context: I am doing a quick-sort-ish algorithm on objects that are fairly large in size, so it would be faster to do the swaps on indices than on the objects themselves, and only move the objects in one final pass. I'd just like to know if I could do this last pass without allocating memory for a separate array.

Edit: I am not asking how to do a sort in O(N) time, but rather how to do the post-sort rearranging in O(N) time with O(1) space. Sorry for not making this clear.

like image 755
int3 Avatar asked Nov 05 '09 19:11

int3


People also ask

Can we sort an array in O n time?

Yes. If you do not have any limitations regarding space complexity then you can sort the array with o(n) time complexity.

How do you rearrange an array element in C++?

Approach used in the below program is as followsDeclare a variable as max_val and set it with arr[size - 1] + 1. Start loop FOR from i to 0 till i less than size. Inside the loop, check IF i % 2 = 0 then set arr[i] to arr[i] + (arr[max] % max_val) * max_val and decrement the max by 1.


1 Answers

I think this should do:

static <T> void arrange(T[] data, int[] p) {
    boolean[] done = new boolean[p.length];        
    for (int i = 0; i < p.length; i++) {
        if (!done[i]) {
            T t = data[i];
            for (int j = i;;) {
                done[j] = true;

                if (p[j] != i) {
                    data[j] = data[p[j]];
                    j = p[j];
                } else {
                    data[j] = t;
                    break;
                }
            }                
        }
    }
}

Note: This is Java. If you do this in a language without garbage collection, be sure to delete done.

If you care about space, you can use a BitSet for done. I assume you can afford an additional bit per element because you seem willing to work with a permutation array, which is several times that size.

This algorithm copies instances of T n + k times, where k is the number of cycles in the permutation. You can reduce this to the optimal number of copies by skipping those i where p[i] = i.

like image 123
meriton Avatar answered Oct 13 '22 21:10

meriton