Problem: Bubblesort - "strlen" in the function...

Hi,
I have a problem with sorting, concretely with bubblesort.

I have this sorting function:

Code:

void bubblesort(char arr[])   /* Function to sort an array */
{
  int i, j;   /* Indexes */
  char tmp;   /* Temporary variable */

  for (i = strlen(arr); i > 0; i--)
    for (j = 0; j < i; j++)
      if (arr[j] > arr[j + 1]) {   /* Changing the value of neighbouring elements */
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
}

...and I call this function with this:

Code:

bubblesort(str);

For example, that in "str" there is string "spkjua".
I would like to sort this "chars" alphabetically (so after that, in the "str" there will be "ajkpsu").

Everything is allright when I replace the 6-th line:

Code:

  for (i = strlen(arr); i > 0; i--)

with for example

Code:

  for (i = 6; i > 0; i--)

...thus I only changed "strlen(arr)" to "6" and it works. But with "strlen(arr)" it doesn't work, but I think IT IS THE SAME, because "strlen(arr)" will return me the value "6".

So does anybody know why the program doesn't work correctly with the "strlen(arr)" in the function?

P.S.: I didn't forget to write "#include <string.h>" at the beginning.

Thanks.

Petike.

Are you sure about the 6? You might be sorting your \0 terminator right to the front of the string. You would probably want strlen(arr)-1.

And, you want to look at index 0 too.

Edit - nah, you're fine. nevermind.

Originally Posted by Petike

Hi,
I have a problem with sorting, concretely with bubblesort.

I have this sorting function:

Code:

void bubblesort(char arr[])   /* Function to sort an array */
{
  int i, j;   /* Indexes */
  char tmp;   /* Temporary variable */

  for (i = strlen(arr); i > 0; i--)
    for (j = 0; j < i; j++)
      if (arr[j] > arr[j + 1]) {   /* Changing the value of neighbouring elements */
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
}

...and I call this function with this:

Code:

bubblesort(str);

For example, that in "str" there is string "spkjua".
I would like to sort this "chars" alphabetically (so after that, in the "str" there will be "ajkpsu").

Everything is allright when I replace the 6-th line:

Code:

  for (i = strlen(arr); i > 0; i--)

with for example

Code:

  for (i = 6; i > 0; i--)

...thus I only changed "strlen(arr)" to "6" and it works. But with "strlen(arr)" it doesn't work, but I think IT IS THE SAME, because "strlen(arr)" will return me the value "6".

So does anybody know why the program doesn't work correctly with the "strlen(arr)" in the function?

P.S.: I didn't forget to write "#include <string.h>" at the beginning.

Thanks.

Petike.

You didn't pass the size of the array, to the bubblesort function. Edit: OK, you just wanted to pass a pointer with arr[]

Is strlen(arr) the length of the string in arr[0], or do you think it could be the length of the pointer address to the first element of arr[]?

Originally Posted by Adak

You didn't pass the size of the array, to the bubblesort function.

Is strlen(arr) the length of the string in arr[0], or do you think it could be the length of the pointer address to the first element of arr[]?

The name of an array, is an address to the array's first element. It is not the contents of the array's first element. strlen(arr] is undoubtedly undefined behavior, since arr is an address, and not a string at all.

But, strlen takes a pointer to a char. That's what a string is, after all. That should be fine.

When I put

Code:

printf("%d\n", strlen(arr))

to the function, it wrote the number "6" (by the way "strlen(arr)" gives me the length of string WITHOUT the '\0' character).

So, "strlen(arr) == 6".

And the program goes fine only when I put the number "6" to cycle, and not when I put there "strlen(arr)", but WHYYYY???


By the way, thanks for answers.

Petike.

Originally Posted by Petike

When I put

Code:

printf("%d\n", strlen(arr))

to the function, it wrote the number "6" (by the way "strlen(arr)" gives me the length of string WITHOUT the '\0' character).

So, "strlen(arr) == 6".

And the program goes fine only when I put the number "6" to cycle, and not when I put there "strlen(arr)", but WHYYYY???


By the way, thanks for answers.

Petike.

It works fine here. But note, whether you use 6 or strlen(arr), if you have arr="abcdef", arr[6] = '\0'. (Array indexes start at 0.) So you need to back up one. (If 6 is working for you, you must have a seven-letter string, or something.)

Adak: i do believe his use of strlen is correct. strlen count the number of characters until the '\0' character. Maybe you mix it with sizeof but even that...

Petike: What do you mean by not working ? Crashing at execution ? Working but not producing the right output ? In this case, which output does it gives you ? Have you try the debugger ?

Like tabstop said, you should have something like "i = strlen(arr)-1" instead of "i = strlen(arr)". This should solve your problem.

...thus I only changed "strlen(arr)" to "6" and it works. But with "strlen(arr)" it doesn't work, but I think IT IS THE SAME, because "strlen(arr)" will return me the value "6".

This is hard to believe. If strlen return 6, than "i = strlen(arr)" or "i = 6" is the exact same thing. There's no reason for one expression "working" correctly and the other not.

Use of strlen is correct. He just needed to back off the strlen(arr) by a byte.

Petike - here's a twist on your code, with an "early out" if the data is in pretty good sorted order to start with. Also, I removed the tmp variable and show the use of XOR to swap values.

Code:

void bubblesort(char arr[] )   /* Function to sort an array */
{
	int i, j;   /* Indexes */
	int changed ;  /* "data was changed this loop" flag  */ 
	
	for (i = strlen(arr)- 1; i > 0; i--) {
		changed = 0 ; 	
		for (j = 0; j < i; j++)
			if (arr[j] > arr[j + 1]) {   /* Changing the value of neighbouring elements */
				
				/* Swap characters */  
				arr[j]   ^= arr[j+1] ; 
				arr[j+1] ^= arr[j] ; 
				arr[j]   ^= arr[j+1] ; 
				
				changed = 1 ;        /* we did change something */  
			}
		if (!changed) break ;   /* leave now - everything is in order */ 
	} 
}

Just looked it up, and K&R says you're right.

If the array[] had two strings in it, and the first string had an '\0' end of string marker, it would surely be goofed to use strlen(array) then, wouldn't it?

e.g.:

Code:

"fisrt string\0 second string\0"

In the same array element, of course.

@foxman: I've never seen strlen(array) used before. It's right, but I'll have to get acquainted with it a bit before I trust it.

Ahhh, I know where is the problem.
I was using

Code:

if (arr[j] > arr[j + 1])

and there is "j + 1", I did't realize "+ 1", and that is "\0" character.

Now it is allright.


Thanks for all your help.

Petike.

Originally Posted by Adak

Just looked it up, and K&R says you're right.

If the array[] had two strings in it, and the first string had an '\0' end of string marker, it would surely be goofed to use strlen(array) then, wouldn't it?

e.g.:

Code:

"fisrt string\0 second string\0"

In the same array element, of course.

Each array element is a char. So they can't all be in the same array element?

I suppose you could initialize a string to that quoted thing, but that would give you a string of "first string" and some extra, but unrelated, memory that would happen to make sense when interpreted as characters. (In other words, if you tried to use in a library function or whatever, you would never get the second part.)

Originally Posted by tabstop

Each array element is a char. So they can't all be in the same array element?

I suppose you could initialize a string to that quoted thing, but that would give you a string of "first string" and some extra, but unrelated, memory that would happen to make sense when interpreted as characters. (In other words, if you tried to use in a library function or whatever, you would never get the second part.)

This is what I mean:

Code:

char array[] = { "the\0 candle" };

So what can strnlen(array). tell us about the size of the array?

I don't believe it can be accurate, but I'll try it in a bit, and see.

Sorry about the same "element", clearly the wrong word, I meant in the same dimension.

Originally Posted by Adak

This is what I mean:

Code:

char array[] = { "the\0 candle" };

So what can strnlen(array). tell us about the size of the array?

I don't believe it can be accurate, but I'll try it in a bit, and see.

Sorry about the same "element", clearly the wrong word, I meant in the same dimension.

Well, strlen is not supposed to give you the size of the array, but the size of the string that the array contains. (Think of all those 80-character (or BUFSIZ-character, or whatever) arrays you've used -- you want strlen to report the size of the string in the buffer, not 80 (or BUFSIZ, or whatever). In your example, array points to the string "the". It is true that you've allocated 12 characters in memory, and put something in all of them, but in a string context, array and the string literal "the\0 candle" aren't the same thing.[1] You get strlen(array) == 3 and sizeof(array)==12.

[1] Edit to add: I mean that in a string context, array does not represent the full string "the\0 candle", but only up to the terminating \0.

Originally Posted by Todd Burch

[...] and show the use of XOR to swap values.

Why? (Search the board for "XOR swap" for my answer.)