Thread: Sorting Algorithm Problem

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    55

    Sorting Algorithm Problem

    Hi, I'm using the bubble sort sorting algorithm with floats. It works correctly.
    However i now need to include infinity, and minus infinity, and NaNs in the program.
    How would i get the user to enter infinity and minus infinity, or NaN, i think i need to use the 'climits' library but I'm not sure how to use it.

    Thanks

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    You will need to treat infinity as a special case on input. For example, map the input "inf" to positive infinity and "-inf" to negative infinity. Standard I/O techniques do not do that, so you will need to write your own code to do it.

    What to you expect a sort algorithm to do when it encounters a NaN? One characteristic of a NaN is that it is not even equal to itself.

    Bear in mind that not all floating point formats can represent infinite values or NaNs.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You have three problems:
    1. Reading infs and nans into your array
    2. How to determine that one or both of the values being compared are nans.
    2. Sorting the array which contains nans.

    I shall elaborate on #3. Although infs (+/-) will sort as expected, nans will not. You will need to write a custom comparator in order to sort them however you choose. Some of the decisions to make are:
    Should all nans be treated as equal to one-another, or should all nans with the same sign bit set be considered equal, or should each representable nan be ordered in a specific way?
    Should nans come before or after all other values, or should nans with the sign bit set come before all others and nans without the sign bit set come after all others?

    Actually it seems very odd that you would be asked to include nans without being given this information.
    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"

  4. #4
    Registered User
    Join Date
    Nov 2010
    Posts
    55
    Hi, i would like to concentrate on positive and negative infinity first, and then later the NaNs.
    I've been instructed that NaNs can be put either at the beginning or the end of the array.

    How would I use inf and -inf, i have no idea where to start.

    Thanks

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    After reading the values in (eg mapping "-inf" to negative infinity and "NaN" to a NaN) it's easy.

    -infinity is less than any other value (except other values of -infinity). Similarly, +infinity is greater than any other value.

    If NaNs are to be placed at the beginning or end of the array, simply deem they are either less than -infinity (to force them to beginning of the array) or greater than +infinity (to force them to the end of the array).

    It all comes down to how you define your ordering criterion (i.e. your comparator).
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Posts
    55
    Thanks for the reply.

    How would i map -inf to negative infinity, and NaN to a NaN?
    could you please tell me more about how i can use the comparator?
    i am new to programming in c++.

    Thanks

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    If the string you read in is "-inf" then set the float to -inf by say assigning -1.f / 0.f to it.
    If the string is "nan" then set the float to say 0.f / 0.f

    A comparator is a function that takes two floats and returns true if the first one should come before the second one once sorted.
    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"

  8. #8
    Registered User
    Join Date
    Nov 2010
    Posts
    55
    Hi, i have been trying a different way.
    I can get the user to enter infinity and -infinity... but say if the user is to enter 5 floats, if the infinity is entered at float 5, the program works correctly and sorts the array perfectly and puts the +inf and -inf in the correct place. However if the inf or - inf is entered at float 1-4 the program goes to the end and does not allow any more floats to be entered.

    How can I overcome this problem, and allow the user to enter as many floats as required even if inf/-inf is entered at the beginning.

    Thanks

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    It sounds like there is a logic error or misplaced bracket in the code. We'd need to take a look at it.
    What compiler are you using, and are you able to step through the code and follow what is happening?
    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"

  10. #10
    Registered User
    Join Date
    Nov 2010
    Posts
    55
    Hi, I am using Microsoft Visual Studio C++ 2010 Express.
    I think the reason is because the array i am writing variables into is of type float, but what i am typing for infinity is of a different type.
    I am using cin >> Array[i], (i being the number of floats the user is to enter), for the user to enter the floats, if the user enters all floats it works perfectly.
    However, if i is 5, if the user enters infinity at any element apart from the last one, the program skips through the rest of the elements and puts a weird numbers for each element.
    Is there anyway i can check to see if the cin has been used for a certain number of times, or once the user has entered the infinity it just continues as normal without skipping through the remaining elements.

    Thanks

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Don't cin directly to the array because that will not allow you to enter infinity etc. Read into a string and then examine and convert that to a value that you can put into your float array manually.
    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"

  12. #12
    Registered User
    Join Date
    Nov 2010
    Posts
    55
    Hi, how do i cin into a string.

    Thanks.

  13. #13
    Registered User
    Join Date
    Nov 2010
    Posts
    55

    Measure Algorithm Running Time

    Hi, i've mostly got it working.
    I want to measure the time for how long the program takes to execute and sort a number of elements, what would be the easiest way to do this?.

    Thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting (asymptotic) complexity problem
    By Petike in forum C++ Programming
    Replies: 8
    Last Post: 01-20-2009, 07:15 AM
  2. what do you think about this simple sorting algorithm?
    By mariano_donati in forum C Programming
    Replies: 9
    Last Post: 02-23-2008, 04:03 AM
  3. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM