Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 11 December 2011 - 10:38 PM
Posted 11 December 2011 - 10:52 PM
I'm guessing this is what RandomAccessIterator is about
Approximately N*logN comparisons on average (where N is last-first).
In the worst case, up to N^{2}, depending on specific sorting algorithm used by library implementation.
Posted 11 December 2011 - 11:18 PM
No, it's not. RandomAccessIterator is simply a template parameter. Sort is expecting you to pass it iterators that support random access. This means, for instance, that std::sort cannot be used on a std::list.
Posted 11 December 2011 - 11:51 PM
Posted 12 December 2011 - 12:01 AM
const char* text = "Hello!"; const char* begin = text; const char* end = text+6; std::sort( begin, end ); printf(text);
Posted 12 December 2011 - 12:02 AM
Posted 12 December 2011 - 12:10 AM
Posted 12 December 2011 - 05:38 AM
Posted 12 December 2011 - 09:38 AM
Posted 12 December 2011 - 10:30 AM
Posted 12 December 2011 - 10:39 AM
Posted 12 December 2011 - 11:41 AM
Maybe a dumb question, but why do you need to ensure a n log n run time?
Unless you are sorting VERY large lists in a real-time environment, and you have profiled that this is a verified choke-point in your program (and it matters), you are simply doing "optimization for optimization's sake." And that is nearly always a bad thing.
Posted 12 December 2011 - 05:40 PM
In that case, why not go the whole hog and use an O(N) sorting algorithm instead, which would be about 13 times faster than the O(N log N) one, and 10,000 times faster than the O(N^{^2}) oneActually lists don't need to be that big for an N log N algorithm to be much faster than an N^2 one. For example if you have 10,000 objects the N log N algorithm should be about 750 times quicker (using a base 2 logarithm, and ignoring the constant factors).
Posted 12 December 2011 - 08:53 PM
In that case, why not go the whole hog and use an O(N) sorting algorithm instead, which would be about 13 times faster than the O(N log N) one, and 10,000 times faster than the O(N^{^2}) oneActually lists don't need to be that big for an N log N algorithm to be much faster than an N^2 one. For example if you have 10,000 objects the N log N algorithm should be about 750 times quicker (using a base 2 logarithm, and ignoring the constant factors).
Posted 12 December 2011 - 09:39 PM
^^ fixed that for you (bold bit).AFAIK, there's no such thing as a comparison-based sorting algorithm with worst-case time complexity below O(n log n) (linearithmic)
...
Posted 12 December 2011 - 09:51 PM
^^ fixed that for you (bold bit).AFAIK, there's no such thing as a comparison-based sorting algorithm with worst-case time complexity below O(n log n) (linearithmic)
...
Any data where you can express ordering as a bitwise greater/less-than can be sorted with an integer sort. This includes integers, floating-point numbers, text, etc... pretty much all the fundamental data-types. Composite sorting rules simply place higher-priority rules in more significant bits, however, the complexity of most of these algorithms is related to the size of your integer 'key', so once it increases past a certain point, you'd be better off with the 'inferior' O(N log N) algorithms.
It's very common to see these kinds of O(K.N) sorting algorithms used inside game engines on decently sized data-sets. On smaller data-sets, introsort is good enough (and has lower 'constant' overhead).
Posted 13 December 2011 - 12:12 AM
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.