Thread: How do you reverse an array?

Originally Posted by dwks

It can be done with a simple loop. It depends on what the OP wants.

Code:

void reverse_array(int *array, int number) {
    int x, t;

    for(x = 0; x < number; x ++, number --) {
        t = array[x];
        array[x] = array[number];
        array[number] = t;
    }
}

Your code will attempt to acccess an element beyond the end of the array if you pass it an array containing only a single element.


Quzah.

Originally Posted by quzah

Your code will attempt to acccess an element beyond the end of the array if you pass it an array containing only a single element.


Quzah.

If I'm not mistaken, it accesses one past the end whenever number > 0, but replacing the for statement with

Code:

for(x = 0; x < --number; x++) {

should fix it.

Edit: Actually, it's not just a one-past-the-end problem, but that number is one too high. Since x and number represent indices to the first and second elements to be swapped, and they start at the beginning and one past the end, resp., x should be incremented at the end of the body, and number decremented at the beginning.

Edit: Pointer version:

Code:

void reverse_array(int *p1, int *p2) {
  int tmp;

  if (p1 == p2) return;
  while (p1 < --p2) {
    tmp = *p1;
    *p1++ = *p2;
    *p2 = tmp;
  }
}

Originally Posted by robatino

Code:

void reverse_array(int *p1, int *p2) {
  int tmp;

  if (p1 == p2) return;
  while (p1 < --p2) {
    tmp = *p1;
    *p1++ = *p2;
    *p2 = tmp;
  }
}

the line with if can be safely removed due to while condition

Originally Posted by vart

the line with if can be safely removed due to while condition

No it can't, because if p1 == p2 then --p2 would generate a bad pointer to one before the start of the array, triggering undefined behavior even if it isn't dereferenced.

Well to be truthful, it's a very odd function. How are you calling it? Passing the head and tail of the array? The head and one-past the tail of the array (which you're not allowed to do really, as the only way you're supposed to ever use that is as a comparison to its value).

I like the "start of array, and its size" as arguments better myself. At the same time I understand the need to keep one's self entertained.


Quzah.

Well I think you're OK with it. There was quite a lengthy discussion on the topic here one time. But who knows if that thread is even in the database any more due to crashes / thread loss. It went something like this:

Code:

if( p < array + len ) /* ok */

p2 = array + len;
if( p < p2 ) /* probably ok */

I can't remember it all, and I'm too tired to look it up now. But there was quite a bit of discussion on what you can and can't do with an array's "one past" element / address.


Quzah.

Quzah et al are right, my code doesn't work some of the time. robatino's fix works.

As I understand it, any two pointers to the same array between the start and one past the end, inclusive, can be compared or subtracted from each other, so both of your examples should be good. Also, any of these pointers except the one past the end can be dereferenced.

Strangely enough, I think that the one-past-end pointer can only be compared with equality, not < or >. This is so that you can have an array at the very end of memory; one-past-the-end would wrap around to zero. You could still == and != it but < and > wouldn't work. It would probably be a good idea to dig up the thread Quzah mentioned.

And all of this because of the simple question, "How do you reverse an array?"

9 When two pointers are subtracted, both shall point to elements of the same array object,
or one past the last element of the array object; the result is the difference of the
subscripts of the two array elements. The size of the result is implementation-defined,
and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header.
If the result is not representable in an object of that type, the behavior is undefined.

Quzah.