Transport a matrix stored in a 1-dimensional array without using additional memory

Question

Possible duplicate:
In place of matrix transposition

Recently attended a Technical Written Interview. The following question has passed.

I have an array, as they say

testArray = {a1,a2,a3,...an,b1,b2,b3,....bn,c1,c2,c3,.....,cn} 

I need to sort this array as `

 testArray = {a1,b1,c1,a2,b2,c2,a3,b3,c3,.....,an,bn,cn} 

Limitation: I must not use additional memory, I must not use the built-in function. Must write the complete code, it can be in any language and can also use any data structure.

eg:

 Input: {1,2,3,4,5,6,7,8,9}, n = 3 Output: {1,4,7,2,5,8,3,6,9} 

I could not get any solution within the constraint, can anyone provide a solution or suggestion?

Answer 1

This is just a matrix transfer operation. And there is even a problem and a solution for transposing the matrix in place on Wikipedia.

No extra space is possible, since you need to at least go through the array. O(1) additional memory is possible with a strong penalty for time complexity.

The solution is based on the algorithm of the next cycle on the Wikipedia page: for each cell we find the cell with the lowest index in the cycle. If the cell with the lowest index is greater than or equal to (> =) the index of the current cell, we will exchange chains. Otherwise, we ignore the cell, as it is correctly replaced. The (poorly analyzed) upper bound in time complexity can reach O ((MN) ² ) (we go through M * N cells, and the cycle can only be as long as the total number of cells).

Answer 2

Impossibility

It is impossible to implement this algorithm without the additional use of memory and arbitrary length, because an iterator is required to traverse the list, which occupies a space.

Finding the right index to share

For fixed array lengths and fixed n you can use the matrix transpose algorithm. and to replace the elements y

The algorithm you are looking for is a matrix transpose algorithm. so you need to swap each element exactly once, iterating through it.

http://en.wikipedia.org/wiki/Transpose

basically you need to swap the mth element in the nth component with the nth element in the mth component. This can be done using a double loop.

 m = length(array)/n; for (i = 0; i < m; i++) for (j = 0; j < n; j++) { index_1 = i * m + j; index_2 = j * m + i swap(index_1, index_2); } 

Note For fixed m and n, this cycle can be fully unrolled, and therefore m, i, j can be replaced by a constant.

Memory-less conversion

To exchange each element without using additional space, you can use the XOR replacement algorithm, as indicated in the comments:

 X := X XOR Y Y := Y XOR X X := X XOR Y 

Answer 3

The easiest way to replace two numbers (a and b) without using a temporary variable:

  b = b + a; a = b - a; b = b - a; 

If you write this in a function, then you are part of this path. How do you keep track of which variable to exchange inside arrays without using a temporary variable is slipping away from me right now.

Keep in mind voters: it really doesn't need to sort the array, just replace the correct values.

Edit: this will work with large values ​​in Java (and in C / C ++, unless you turn on some very aggressive compiler optimizers - the behavior is undefined, but defaults to a reasonable value ). Values ​​will simply wrap around.

The second edit is some (rather unverified) code to flip the array around, I think, 4 integers above the memory limit. It is technically massively unthreadsafe, but it will only be parallelized because you will only get access to each location of the array once maximum:

 static int[] a = {1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,16}; static int n = 4; public static void main(String[] args) { for(int i = 0; i < a.length/n; i++) // 1 integer for(int j = 0; j < n; j++) // 1 integer if(j > i) swap(i*n+j, j*n+i); } static void swap(int aPos, int bPos) // 2 integers { if(a[aPos] != a[bPos]) { a[bPos] = a[aPos] + a[bPos]; a[aPos] = a[bPos] - a[aPos]; a[bPos] = a[bPos] - a[aPos]; } } 

Sorry if this misunderstands the question; I read it carefully and could not decide what was needed, except for this.

Answer 4

Check out the quick sort algorithm

For more information about the available algorithms, go to the Sort page.