Thread: Having trouble sorting an Array that has a zero in it.

  1. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    13

    Having trouble sorting an Array that has a zero in it.

    Hey guys, I was just wondering if someone could take a look at my code real quick. I'm sorting an array, and when it comes to a zero it obviously prints zero's from that point on. I'm using a simple selection sort, and it works fine as long as there are no zero's in the array. Could suggest a fix to this problem???

    insert
    Code:
    void sortArray (float nums[], int last)
    
    {
        int smallest;
        int temp;
    
        for (int current = 0; current < last; current++)
            {
                smallest = current;
    
                for (int walk = current + 1; walk <= current; walk++)
                    
                    if (nums[walk] < nums[smallest] && nums[smallest] != 0)
                        smallest = walk;
                    
                    else if (nums[smallest] == 0)
                        smallest = walk++; //Here's where I think my problem is...
    
                        temp = nums[current];
                        nums[current] = nums[smallest];
                        nums[smallest] = temp;
            }
    return;
    }
    I want it to just print the 0 and resume sorting, but I've been looking at it for hours and can't seem to think of something to make that happen.

    Thanks so much for any help...

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I prefer to use braces even when they are optional, so this is how I would style your function:
    Code:
    void sortArray(float nums[], int last)
    {
        int smallest;
        int temp;
    
        for (int current = 0; current < last; current++)
        {
            smallest = current;
    
            for (int walk = current + 1; walk <= current; walk++)
            {
                if (nums[walk] < nums[smallest] && nums[smallest] != 0)
                {
                    smallest = walk;
                }
                else if (nums[smallest] == 0)
                {
                    smallest = walk++;
                }
            }
    
            temp = nums[current];
            nums[current] = nums[smallest];
            nums[smallest] = temp;
        }
    }
    Now, observe this line:
    Code:
    for (int walk = current + 1; walk <= current; walk++)
    walk is set to current + 1, hence walk > current, thus walk <= current is always false, so the inner loop's body is never entered. Therefore, we can simplify your code to:
    Code:
    void sortArray(float nums[], int last)
    {
        int smallest;
        int temp;
    
        for (int current = 0; current < last; current++)
        {
            smallest = current;
            temp = nums[current];
            nums[current] = nums[smallest];
            nums[smallest] = temp;
        }
    }
    Since smallest == current, the swap is a self-swap, which has no net effect. The loop does no other work, and the function has no other code. Therefore, we can simplify your function to:
    Code:
    void sortArray(float nums[], int last) {}
    Is this really the code that you compiled and tested?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I don't understand the special treatment for zero. The simple nums[ walk ] < nums[ smallest ] should be the only comparison. Also, it's only after you find the smallest that you swap. After that, one element has been sorted, so you continue from the second leftmost element, and so on, until all the elements have been selected.

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    13
    Quote Originally Posted by laserlight View Post
    I prefer to use braces even when they are optional, so this is how I would style your function:
    Code:
    void sortArray(float nums[], int last)
    {
        int smallest;
        int temp;
    
        for (int current = 0; current < last; current++)
        {
            smallest = current;
    
            for (int walk = current + 1; walk <= current; walk++)
            {
                if (nums[walk] < nums[smallest] && nums[smallest] != 0)
                {
                    smallest = walk;
                }
                else if (nums[smallest] == 0)
                {
                    smallest = walk++;
                }
            }
    
            temp = nums[current];
            nums[current] = nums[smallest];
            nums[smallest] = temp;
        }
    }
    Now, observe this line:
    Code:
    for (int walk = current + 1; walk <= current; walk++)
    walk is set to current + 1, hence walk > current, thus walk <= current is always false, so the inner loop's body is never entered. Therefore, we can simplify your code to:
    Code:
    void sortArray(float nums[], int last)
    {
        int smallest;
        int temp;
    
        for (int current = 0; current < last; current++)
        {
            smallest = current;
            temp = nums[current];
            nums[current] = nums[smallest];
            nums[smallest] = temp;
        }
    }
    Since smallest == current, the swap is a self-swap, which has no net effect. The loop does no other work, and the function has no other code. Therefore, we can simplify your function to:
    Code:
    void sortArray(float nums[], int last) {}
    Is this really the code that you compiled and tested?
    Yes...it now prints the array, but it doesn't sort from lowest to highest. Ran it with another file with no zero's and it sorted it just fine. I've been at this for hours, lol. I just can't get it to sort the negative numbers, then the zero, and then follow with the positive numbers...driving me crazy!!![/QUOTE]

  5. #5
    Registered User
    Join Date
    Jun 2011
    Posts
    13
    Quote Originally Posted by Cgmgator View Post
    Yes...it now prints the array, but it doesn't sort from lowest to highest. Ran it with another file with no zero's and it sorted it just fine. I've been at this for hours, lol. I just can't get it to sort the negative numbers, then the zero, and then follow with the positive numbers...driving me crazy!!!
    [/QUOTE]

    You're right, I actually had

    [CODE:]

    for (int walk = current + 1; walk <= last; walk++)

    [/CODE]

    Before I tried to do a bubble sort...my eyes are starting to hurt, but it actually wasn't working before that.

  6. #6
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Laser gave you a great starting point for how to evaluate your code and then whiteflags basically spelled out the selection sort algorithm for you.

    The selection sort algorithm is:

    1. Find the minimum element in the list

    2. Swap it with the element in the first position of the list

    3. Repeat the steps above for all remainder elements of the list starting at the second position.

    Now compare that with your implementation:

    Code:
    for (int current = 0; current < last; current++)
            {
                smallest = current;
    
                for (int walk = current + 1; walk <= current; walk++)
                    
                    if (nums[walk] < nums[smallest] && nums[smallest] != 0)
                        smallest = walk;
                    
                    else if (nums[smallest] == 0)
                        smallest = walk++; //Here's where I think my problem is...
    
                        temp = nums[current];
                        nums[current] = nums[smallest];
                        nums[smallest] = temp;
            }
    What do you think is going on here?
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  7. #7
    Registered User
    Join Date
    Jun 2011
    Posts
    13
    I think when smallest gets to a value of 0, it stores the 0 in temp, then for some reason the 0 gets passed to the rest of the printed arrays...I added the if..else statement to try to find some way to deal with zero, but I am really missing something.

  8. #8
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    I think so to. Let's take a look at what whiteflags said:
    I don't understand the special treatment for zero. The simple nums[ walk ] < nums[ smallest ] should be the only comparison. Also, it's only after you find the smallest that you swap. After that, one element has been sorted, so you continue from the second leftmost element, and so on, until all the elements have been selected.
    When evaluating numbers the microprocessor is smart enough to understand -5 < -3 < 0 < 3...ect. You don't need any special cases there. Simply implement the algorithm listed above. When you first start your search simply set the smallest number to the first value in the array and begin the search.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  9. #9
    Registered User
    Join Date
    Jun 2011
    Posts
    13
    I wonder if maybe my problem is the value that I passed for the last index in the array. I defined the SIZE = 90. I set a count to stop at 90. Would my value of last be the SIZE - count? Or maybe last = count - 1?

  10. #10
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    The problem is your implementation of your selection sort.

    Lets say I made an array of 5 numbers: -3, -5, 0, 5, 2.

    Now in order to sort my array using selection sort I would:

    1. start with the first value of my array and make that my min. (so minus 3)
    2. start looking at everyother value in the array excluding my starting point (so I would start with -5 or my starting point + 1)
    3. Compare the two values, is my min > the next value?
    3.a if Yes I would swap those values.
    4. Continue comparing the rest of the list.
    5. Start over at step 2 but make my new min be the next array value to look at.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  11. #11
    Registered User
    Join Date
    Jun 2011
    Posts
    13
    Does this look right? I am so sorry to keep bothering you guys, but I won't be able to sleep until I get this right...

    Code:
    void sortArray(float nums[], int last)
    {
        int smallest;
        int temp;
    
        for (int current = 0; current < last; current++)
        {
            smallest = current;
    
            for (int walk = current + 1; walk <= last; walk++)
                if (nums[walk] < nums[smallest])
                smallest = walk;
    
            temp = nums[current];
            nums[current] = nums[smallest];
            nums[smallest] = temp;
        }
    
    return;

  12. #12
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    You are starting to get there. Let's take a look at your code:
    Code:
    void sortArray(float nums[], int last)
    {
        int smallest;
        int temp;
    
        for (int current = 0; current < last; current++)
        {
            smallest = current;
    1. you actually only need to iterate the outer loop through last-1 since the inner loop will evaluate the last member
    2. instead of storing the index store the actual value here since it will make the swap easier, aka smallest=nums[current]. Also note that your array is float here so I reccommend making smallest a float as well.

    Code:
     for (int walk = current + 1; walk <= last; walk++){
                if (nums[walk] < nums[smallest]){
                     smallest = walk;
                     temp = nums[current];
                     nums[current] = nums[smallest];
                     nums[smallest] = temp;
                }
    }
    In red are where you need your brackets so the compiler knows where the dependent lines of code are for your loop.

    In bold, walk < last; don't exceed the bounds of your array.

    In blue let's take a look at your swapping:
    1. make temp a float as well.
    2. Save num[smallest] in your temp variable
    3. Make num[walk] your new num[smallest]
    4. place temp back in your array at num[walk]
    Last edited by AndrewHunter; 06-29-2011 at 12:33 AM.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by AndrewHunter
    2. instead of storing the index store the actual value here since it will make the swap easier, aka smallest=nums[current]. Also note that your array is float here so I reccommend making smallest a float as well.
    I think storing the index is fine. In fact, storing the actual value will make the swap harder because you need to know where the smallest element is so as to assign the first element's value to it.

    Quote Originally Posted by AndrewHunter
    In blue let's take a look at your swapping:
    1. make temp a float as well.
    2. Save num[smallest] in your temp variable
    3. Make num[walk] your new num[smallest]
    4. place temp back in your array at num[walk]
    Good catch with the type of temp. I am curious why you outlined a swap algorithm that mirrors Cgmgator's swap implementation. Even more interesting is why you added those braces where you did

    Also, Cgmgator: what is last? The index of the last element?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Quote Originally Posted by laserlight View Post
    I think storing the index is fine. In fact, storing the actual value will make the swap harder because you need to know where the smallest element is so as to assign the first element's value to it.
    As always laser, thankyou for the insight. I guess I just never thought about it that way....

    Quote Originally Posted by laserlight View Post
    ... I am curious why you outlined a swap algorithm that mirrors Cgmgator's swap implementation. Even more interesting is why you added those braces where you did
    ...
    Huh, I guess I did. Silly me. As for the braces I didn't see the need to do the swap if none is required.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Judging by how you've named the second parameter, yes it is fine.
    However you should note that with it like this you'll need to pass in size-1 as the second parameter. Standard library algorithms eliminate the need for the -1 and are minutely more efficient as a result.

    Oh right yeah the type of 'temp' needs correcting. I noticed that earlier but forgot to say.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Adding nodes to an array at the top & array sorting
    By Wolf` in forum C++ Programming
    Replies: 1
    Last Post: 06-25-2010, 12:48 PM
  2. Replies: 9
    Last Post: 04-07-2010, 10:03 PM
  3. Trouble sorting a list
    By pliang in forum C++ Programming
    Replies: 1
    Last Post: 07-17-2005, 06:54 AM
  4. 2D array sorting from min. to max.
    By khaled_helmy in forum C Programming
    Replies: 1
    Last Post: 10-14-2004, 02:17 PM
  5. Trouble with array sorting
    By dcj1978 in forum C++ Programming
    Replies: 3
    Last Post: 09-19-2003, 12:16 PM

Tags for this Thread