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

  1. #1
    Beginning game programmer Petike's Avatar
    Join Date
    Jan 2008
    Posts
    64

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    And, you want to look at index 0 too.

    Edit - nah, you're fine. nevermind.
    Last edited by Dino; 01-24-2008 at 03:56 PM.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Petike View Post
    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[]?
    Last edited by Adak; 01-24-2008 at 04:46 PM.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Adak View Post
    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.

  6. #6
    Beginning game programmer Petike's Avatar
    Join Date
    Jan 2008
    Posts
    64

    Re: STRLEN(ARR) == 6???

    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.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Petike View Post
    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.)

  8. #8
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    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 */ 
    	} 
    }

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 01-24-2008 at 04:43 PM.

  11. #11
    Beginning game programmer Petike's Avatar
    Join Date
    Jan 2008
    Posts
    64

    Soluted...

    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.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Adak View Post
    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.)

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by tabstop View Post
    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.
    Last edited by Adak; 01-24-2008 at 07:24 PM.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Adak View Post
    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.

  15. #15
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by Todd Burch View Post
    [...] and show the use of XOR to swap values.
    Why? (Search the board for "XOR swap" for my answer.)
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. wxWidgets link problem
    By cboard_member in forum C++ Programming
    Replies: 2
    Last Post: 02-11-2006, 02:36 PM
  2. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  3. Problem with function pointers
    By vNvNation in forum C++ Programming
    Replies: 4
    Last Post: 06-13-2004, 06:49 AM
  4. structure vs class
    By sana in forum C++ Programming
    Replies: 13
    Last Post: 12-02-2002, 07:18 AM
  5. I need help with passing pointers in function calls
    By vien_mti in forum C Programming
    Replies: 3
    Last Post: 04-24-2002, 10:00 AM