Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re^5: Sort mechanics problems ... (efficiency)

by tye (Sage)
on Jun 02, 2016 at 07:32 UTC ( [id://1164739]=note: print w/replies, xml ) Need Help??


in reply to Re^4: Sort mechanics problems ...
in thread Sort mechanics problems with objects and potentially contradicting comparisons (would cause infinite loop)

No.

As documented, the results are "not well-defined". It is far better for a sort algorithm to not go into an infinite loop. Sort algorithms are heavily optimized (for good reasons) to do as few comparisons as possible. Those optimizations are predicated on the assumption that you actually have a well-ordered set with a well-defined comparison operation. Because that is what people generally have when they call an optimized 'sort'.

The good sorting algorithms are so optimized that they are actually unable to even notice that your comparison operation is not well-defined. If a 'sort' sees $a < $b, then it would be a waste of resources if it later needed to check if $b < $a. So efficient sorting algorithms never do that. If they even see $a < $b and $b < $c, then they also won't bother comparing $a to $c.

If you want some kind of 'sort' that is guaranteed to detect the well-definedness of the comparison, then that 'sort' will always be O(n*n), no matter the input.

But even if you had one of those, having one that can go into an infinite loop would just be stupid. That only makes even a little sense if checking $a < $b a second time might give you a different answer than the first time. And if that really matters to you, then your 'sort' can never ever return, because just because $a < $b the first 10,000 times you checked, it might not stay that way.

- tye        

  • Comment on Re^5: Sort mechanics problems ... (efficiency)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1164739]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (4)
As of 2024-04-26 00:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found