Click here to Skip to main content
15,939,853 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Hi everyone:
I got a question recently. Here is the detail.
I got an array of 2*N elements like this:array[X1,X2...Xn,Y1,Y2,....Yn]
Now I need to sort the array and make it change to this:
array[X1,Y1,X2,Y2......Xn,Yn].
And I wrote a function like this:
C++
   void exchange_array(char *array, int len)
{
	int index;
	char tmp_value = *(array + 1);

	char *ptr_second_half  = array + len/2;
	char *ptr_fist_half    = array + 1;
	
	while ((ptr_fist_half < ptr_second_half)&&(*ptr_fist_half != '\0'))
	{
		char tmp;
		*ptr_fist_half = *ptr_second_half;
		ptr_fist_half++;
		tmp = *ptr_fist_half;
		*ptr_fist_half = tmp_value;
		tmp_value = tmp;
		ptr_fist_half++;
		ptr_second_half++;
	}
}

The "array" is the array we need to handle with,and the "len" is the length of
the array. There seems to be a problem of this function but I just can't fix it.So can any friend give me a solution of this trouble? Thanks!
Posted
Comments
Sergey Alexandrovich Kryukov 15-Oct-12 15:05pm    
The "Solution 1" is not really a solution. So, you don't have one. You need to solve this simple problem by yourself; I'll only point out the problem I can see.
By they way, it smells like one of the stupid interview problems. In real life, a decent developer will simply ask: "how come the array elements came in wrong way?". And fix the root of the problem my introducing proper data structure, instead of writing this pointless code.
--SA

I would abandon the in-place rearranging and use a second array to store the result, namely
C++
void exchange_array(char *array, int len)
{
    assert(!(len%2)); // handle odd-sized array
    int i;
    char * res = new char [len];
    for(i=0;i<len/2;i++)
        res[2*i]=array[i];
    for (i=0; i<len/2; i++)
        res[2*i+1]=array[len/2+i];
    for (i=0; i<len;i++)
        array[i]=res[i];
    delete [] res;
}
 
Share this answer
 
Comments
Stefan_Lang 16-Oct-12 4:08am    
Not sure why anyone voted you down, but unless there is an explicit statement concerning performance or the explicit requirement to program an in-place reordering I consider this the most sensible approach.

I remember an interview with a similar question and I put in all sorts of simple tricks that I could think of, 1 or 2 of them I had to explain to the interviewer. In the end I got turned down, and the reason given was being 'overqualified'. I still wonder if that was just a nice way of saying 'overcomplicated' ;-)
CPallini 16-Oct-12 13:06pm    
Thank you very much.
I tried a bit the in-place approach, but (at least my method) was soon becoming cumbersome. I would really appreciate someone posting an elegant in-place solution.
As I promised, I'm pointing out to your first mistake, which is a pretty bad one.

This is the comparison != '\0' in the loop condition. First of all, this is not the stupid null-terminated string. The 0 value has no special meaning. You should use the value of len to determine the number of iterations, nothing else. Besides, the algorithm can be universal, as it can always work, no matter what's the type of the array element. There is nothing which needs character type to work.

A bonus advice: the problem makes no sense if len is odd. In case it is odd, I would simply throw some exception.

That's it. From this point, please, you are on your own.

—SA
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900