Reverse a string

[lovecreatesbea...]

/*reverse a string, e.g. from "abc" to "cba". no library function
invoking is allowed.*/

void reverse(char *s){
char *p = s;
char c;
int n1 = 0, n2 = 0;

while (*p++)
n2++;
n2--;

while (n1 < n2){
c = s[n1];
s[n1] = s[n2];
s[n2] = c;
n1++;
n2--;
}
}

void reverse2(char *s){
char *p1 = s, *p2 = s;
char c;

while (*p2)
p2++;
p2--;

while (p1 < p2){
c = *p1;
*p1 = *p2;
*p2 = c;
p1++;
p2--;
}
}

I have written two versions of reverse function. How do you think about
them? Can they be shorter or more efficient.

 

[dcorbit]

http://groups.google.com/groups?as_...1&as_maxd=19&as_maxm=10&as_maxy=2006&safe=off

 

[Jens Thoms Toerring]

/*reverse a string, e.g. from "abc" to "cba". no library function
invoking is allowed.*/

void reverse(char *s){
char *p = s;
char c;
int n1 = 0, n2 = 0;

while (*p++)
n2++;
n2--;

while (n1 < n2){
c = s[n1];
s[n1] = s[n2];
s[n2] = c;
n1++;
n2--;
}
}

void reverse2(char *s){
char *p1 = s, *p2 = s;
char c;

while (*p2)
p2++;
p2--;

while (p1 < p2){
c = *p1;
*p1 = *p2;
*p2 = c;
p1++;
p2--;
}
}

I have written two versions of reverse function. How do you think about
them? Can they be shorter or more efficient.

Well, as far as I can see both look fine. I probably would go for the
second one (I guess it's more like what an experienced C programmer
would write and, anyway, I like pointers;-). And, yes, you can make
it look a bit shorter, e.g.

void reverse3( char *s )
{
char *end_ptr = s;

while ( *end_ptr )
end_ptr++;

while ( s < --end_ptr )
{
char c = *s;
*s++ = *end_ptr;
*end_ptr = c;
}
}

About efficiency: please define what exactly you mean by efficiency
(it could mean e.g. "the fastest running code" or "the code requiring
the smallest amount of memory" etc.). And then "efficiency" can only be
either measured or perhaps checked by analysing the code generated by
the compiler - but that depends on both the compiler (and the options
you use) and the platform you are compiling this on (but that would be
outside the scope of this newsgroup), you can't tell just by looking
at the C source (unless you're doing something obviously stupid;-).

Regards, Jens

 

[CBFalconer]

/*reverse a string, e.g. from "abc" to "cba". no library function
invoking is allowed.*/

void reverse(char *s){
char *p = s;
char c;
int n1 = 0, n2 = 0;

while (*p++)
n2++;
n2--;

while (n1 < n2){
c = s[n1];
s[n1] = s[n2];
s[n2] = c;
n1++;
n2--;
}
}

void reverse2(char *s){
char *p1 = s, *p2 = s;
char c;

while (*p2)
p2++;
p2--;

while (p1 < p2){
c = *p1;
*p1 = *p2;
*p2 = c;
p1++;
p2--;
}
}

I have written two versions of reverse function. How do you think
about them? Can they be shorter or more efficient.

Yes.

 

[lovecreatesbea...]

/*reverse a string, e.g. from "abc" to "cba". no library function
invoking is allowed.*/

void reverse(char *s){
char *p = s;
char c;
int n1 = 0, n2 = 0;

while (*p++)
n2++;
n2--;

while (n1 < n2){
c = s[n1];
s[n1] = s[n2];
s[n2] = c;
n1++;
n2--;
}
}

void reverse2(char *s){
char *p1 = s, *p2 = s;
char c;

while (*p2)
p2++;
p2--;

while (p1 < p2){
c = *p1;
*p1 = *p2;
*p2 = c;
p1++;
p2--;
}
}

I have written two versions of reverse function. How do you think about
them? Can they be shorter or more efficient.

Well, as far as I can see both look fine. I probably would go for the
second one (I guess it's more like what an experienced C programmer
would write and, anyway, I like pointers;-). And, yes, you can make
it look a bit shorter, e.g.

void reverse3( char *s )
{
char *end_ptr = s;

while ( *end_ptr )
end_ptr++;

while ( s < --end_ptr )
{
char c = *s;
*s++ = *end_ptr;
*end_ptr = c;
}
}

Yes, expression like s++ can be used inside the function body, after
the function the argument pointer remains unchanged. And it saves one
temporary variable. I should have realized it. Thank you.

About efficiency: please define what exactly you mean by efficiency
(it could mean e.g. "the fastest running code" or "the code requiring
the smallest amount of memory" etc.). And then "efficiency" can only be
either measured or perhaps checked by analysing the code generated by
the compiler - but that depends on both the compiler (and the options
you use) and the platform you are compiling this on (but that would be
outside the scope of this newsgroup), you can't tell just by looking
at the C source (unless you're doing something obviously stupid;-).

Don't people talk about algorithm efficiency based on source code?
Though I know these functions may be too small and simple.

 

[Richard Heathfield]

(e-mail address removed) said:

Don't people talk about algorithm efficiency based on source code?

No. Algorithm efficiency depends on the algorithm, not the implementation.
All the source code tells a careful reader thereof is how efficiently the
algorithm is implemented, not how efficient the algorithm actually is.

In this case, it's hard to imagine a more efficient way to reverse a single
string than to find the two ends of the string, and then continue to swap
the two so-far-unswapped characters that are furthest from each other until
all characters have been swapped. This has a complexity of O(n).

All the source code tells you is whether or not this has been done properly.
If it has, then at worst you'll need two passes over the data - one to find
the end, and one to do the swapping. If you have the length already, that's
one pass saved.

 

[Peter Nilsson]

size_t is preferable to int.

while (*p++)
n2++;
n2--;

while (n1 < n2){
c = s[n1];
s[n1] = s[n2];
s[n2] = c;
n1++;
n2--;
}
}

void reverse2(char *s){
char *p1 = s, *p2 = s;
char c;

while (*p2)
p2++;
p2--;

If I pass a string of 0 characters, this invokes undefined behaviour.

Well, as far as I can see both look fine. I probably would go for the
second one (I guess it's more like what an experienced C programmer
would write and, anyway, I like pointers;-). And, yes, you can make
it look a bit shorter, e.g.

void reverse3( char *s )
{
char *end_ptr = s;

while ( *end_ptr )
end_ptr++;

while ( s < --end_ptr )

Same problem as OP.

{
char c = *s;
*s++ = *end_ptr;
*end_ptr = c;
}
}

Well, as far as I can see both look fine. ...

Not to me.

And yes, you can make it look a bit shorter, e.g.

void reverse3( char *s )
{
char *end_ptr = s;

while ( *end_ptr )
end_ptr++;

while ( s < --end_ptr )
{
char c = *s;
*s++ = *end_ptr;
*end_ptr = c;
}
}

I would use unsigned char to copy/swap the bytes...

char *reverse4(char *s)
{
unsigned char c, *u, *v;
u = v = (unsigned char *) s;
while (*v) v++;
if (u != v)
for (; u < --v; u++) { c = *u; *u = *v; *v = c; }
return s;
}

 

[lovecreatesbea...]

size_t is preferable to int.

while (*p++)
n2++;
n2--;

while (n1 < n2){
c = s[n1];
s[n1] = s[n2];
s[n2] = c;
n1++;
n2--;
}
}

void reverse2(char *s){
char *p1 = s, *p2 = s;
char c;

while (*p2)
p2++;
p2--;

If I pass a string of 0 characters, this invokes undefined behaviour.

Well, as far as I can see both look fine. I probably would go for the
second one (I guess it's more like what an experienced C programmer
would write and, anyway, I like pointers;-). And, yes, you can make
it look a bit shorter, e.g.

void reverse3( char *s )
{
char *end_ptr = s;

while ( *end_ptr )
end_ptr++;

while ( s < --end_ptr )

Same problem as OP.

{
char c = *s;
*s++ = *end_ptr;
*end_ptr = c;
}
}

Well, as far as I can see both look fine. ...

Not to me.

And yes, you can make it look a bit shorter, e.g.

void reverse3( char *s )
{
char *end_ptr = s;

while ( *end_ptr )
end_ptr++;

while ( s < --end_ptr )
{
char c = *s;
*s++ = *end_ptr;
*end_ptr = c;
}
}

I would use unsigned char to copy/swap the bytes...

char *reverse4(char *s)
{
unsigned char c, *u, *v;
u = v = (unsigned char *) s;
while (*v) v++;
if (u != v)
for (; u < --v; u++) { c = *u; *u = *v; *v = c; }
return s;
}

Thanks Peter. But I think *s is char but *u and *v are unsigned char,
they don't match in your code. You changed the returned type to char *,
this may be better. But the prototype of my original function was given
in some specification.

 

[lovecreatesbea...]

size_t is preferable to int.

while (*p++)
n2++;
n2--;

while (n1 < n2){
c = s[n1];
s[n1] = s[n2];
s[n2] = c;
n1++;
n2--;
}
}

void reverse2(char *s){
char *p1 = s, *p2 = s;
char c;

while (*p2)
p2++;
p2--;

If I pass a string of 0 characters, this invokes undefined behaviour.

Do you mean the p2--; statement?

I can understand that a similar statement like *p2-- = 'x'; there will
leads to UB. But this statement just moves the pointer along the memory
units, and it doesn't write to any of them, so it is OK, right?

 

[Simon Biber]

Do you mean the p2--; statement?
Yeah.

I can understand that a similar statement like *p2-- = 'x'; there will
leads to UB. But this statement just moves the pointer along the memory
units, and it doesn't write to any of them, so it is OK, right?

No, it's not OK. There's a special allowance to make pointers to one
PAST the end of an array, but not one BEFORE the beginning of an array.
The attempt to construct an invalid pointer is undefined behaviour --
while in most cases it's harmless, it may cause a trap on systems that
keep close control over memory, bounds-checking implementations, etc.

By the way, *p2-- = 'x'; in that spot would be no different. That stores
'x' into the first element of the array, not one before the first. The
pointer value that is dereferenced is the one that p2 had before the
decrement, as it's a post-decrement. Perhaps you meant *--p2 = 'x';

 

[Christopher Benson-Manica]

I can understand that a similar statement like *p2-- = 'x'; there will
leads to UB. But this statement just moves the pointer along the memory
units, and it doesn't write to any of them, so it is OK, right?

No. Merely generating a pointer to memory outside the bounds of an
object (except for one past the end of an array) in itself causes UB.

 

[dcorbit]

/*
** Variant of Lawrence Kirby's recursive solution without auxilliary
variable.
** The real beauty of this one is thinking about what makes it work.
** Of course, you would never want to do it this way in real life.
** A great example of an idiotic student exercise, if there ever was
one.
** IMO-YMMV.
*/
#include <assert.h>
void r(char *s)
{
assert(s);
if (s[0] && s[1]) {
r(s+1);
r(s+2); /* Assumes string is nul terminated... */
/* Chester Cheetah says, "It ain't easy -- being cheesy": */
s[0] ^= s[1], s[1] ^= s[0], s[0] ^= s[1];
r(s+1);
}
}