How do you reverse an array?

This is a discussion on How do you reverse an array? within the C Programming forums, part of the General Programming Boards category; Originally Posted by dwks It can be done with a simple loop. It depends on what the OP wants. Code: ...

  1. #16
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by dwks View Post
    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.
    Hope is the first step on the road to disappointment.

  2. #17
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by quzah View Post
    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;
      }
    }
    Last edited by robatino; 03-30-2007 at 10:28 PM.

  3. #18
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,454
    Quote Originally Posted by robatino View Post
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by vart View Post
    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.
    Last edited by robatino; 03-31-2007 at 01:54 AM.

  5. #20
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  6. #21
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by quzah View Post
    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).
    Quzah.
    It's the start and one past the end of the array, resp. I don't know what you mean by only using it as a comparison to its value. If it means don't dereference it, I don't, since it's decremented before that happens.

  7. #22
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Last edited by quzah; 03-31-2007 at 02:20 AM.
    Hope is the first step on the road to disappointment.

  8. #23
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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. My function was written to imitate the C++ Standard Library's interface, using pointers/iterators to the beginning and one past the end of a container (it has to be one past the end to allow zero-length containers).

  9. #24
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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?"
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #25
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    I don't think this is correct, since it's not really necessary to allow an array at the very end of memory, because it would only save a few bytes, at the expense of losing the ability to do a general compare with one-past-the-end. I don't have a copy of the Standard, but did some googling, and found the following links:

    http://c0x.coding-guidelines.com/6.5.6.html
    http://archives.devshed.com/forums/d...s-1151250.html

    The second link basically claims something I never heard of, which is that although the result of pointer subtraction is ptrdiff_t (defined in <stddef.h>), which I knew, it's not guaranteed that ptrdiff_t is actually big enough to hold the result of the subtraction (!), and that if it isn't, the result is undefined. What this seems to mean is that one can't reliably do pointer subtraction at all, but just comparisons <, <=, >, >=, ==, != (as long as both pointers point to elements of the same array, or one-past-the-end of the array). But I'm pretty sure that the one-past-the-end pointer has the same status as the other elements of an array as far as these comparisons is concerned. Can someone with a copy of the Standard find some relevant passages?

  11. #26
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-25-2008, 12:50 AM
  2. Reverse Print Vector Array help
    By guda in forum C++ Programming
    Replies: 2
    Last Post: 11-11-2002, 05:47 PM
  3. how do I reverse order of my array
    By jgonzales in forum C++ Programming
    Replies: 6
    Last Post: 09-25-2002, 03:48 PM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM
  5. read into array and spit out in reverse order
    By steven in forum C Programming
    Replies: 4
    Last Post: 09-07-2001, 02:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21