Rearranging array elements

Question

Not sure if it is a duplicate. Given a data structure having first N integers and next N chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN. I need an in-place algorithm to rearrange the elements as A = i1 c1 i2 c2 ... iN cN.

Answer 1

I believe this is a standard sort problem.

All you need is a good comparison function, then use qsort.

Are you familiar with qsort?
Have you created any piece of a comparison function you can share with us?

Edit
As commentors have pointed out, qsort, std::sort, and other similar routines need objects of identical size. Since the question calls for an array of ints and chars, which are of different sizes and is not strictly possible in C/C++, more information is needed.

Exactly how is this array declared? How big are the ints and how big are the chars? Does the existence of chars imply that N is limited to 255?

Once again, some code would really help.

Answer 2

Your problem is equivalent to transposing a 2xN matrix in-place. You can read the theory here: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Maybe in the special case of 2xN matrix a simpler algorithm exists, however I can't think of any. The general idea is to follow the cycles of the permutation.

Answer 3

There seem to be 3 problems in this question.

1. Insert both types of items in the same list. There are several ways to do this, but it won't be pretty.
2. partition the data to separate chars and ints.
3. sort each partition to order chars and order ints.