1

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.

josh
  • 13,793
  • 12
  • 49
  • 58
  • 1
    Almost duplicate: http://stackoverflow.com/questions/3777184/rotate-2d-rectangular-array-in-place/3777262 – Yakov Galka Oct 15 '10 at 16:33
  • 2
    What is the question? Surely we are not going to write all your code for you. Do you have any code to share? Have you run into any specific problems that we can help you with? – abelenky Oct 15 '10 at 16:34
  • 3
    btw: How does a C/C++ array hold both chars and ints, without a lot of typecasting? – abelenky Oct 15 '10 at 16:35
  • @abelenky: i tried outputting the values to another array but couldnt think of an in-place approach. – josh Oct 15 '10 at 16:41
  • @yadab: No, this will transform `i1 i2 i3 ... iN c1 c2 c3 ... cN` to `c1 c2 c3 ... cN i1 i2 i3 ... iN`. – Yakov Galka Oct 15 '10 at 16:48
  • @ybungalobill: I am sorry, I deleted that my mistake. – yadab Oct 15 '10 at 16:53

3 Answers3

4

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.

Yakov Galka
  • 70,775
  • 16
  • 139
  • 220
2

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.
André Caron
  • 44,541
  • 12
  • 67
  • 125
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.

abelenky
  • 63,815
  • 23
  • 109
  • 159