Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

vaneger

fastest sorting???

This topic is 5242 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i know the fastest sort is log 2 n such as quicksort or mergesort, but my question is how can you make those run faster.... yes you are stuck with X executions where x is log base 2 n but you can speed up those executions via goto and labels instead of recursion ( also you then dont get stack overflows ) . can multithreading help make these sorts faster? for instance where each part of teh sort would have been a recursive call, make it a new thread instead?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Quicksort is O(n^2).

Share this post


Link to post
Share on other sites
no i messed up before merge/quicksort is O (n(log base 2 n)), quick sort is most definatly not n squared that is like selection sort quick sort is much much faster than that but merge sort sees to have the fastest results, but can i make it faster using threads?

Share this post


Link to post
Share on other sites
Quicksort is O(n log n) on average, O(n^2) worst-case. Its performance is already due to the simplicity of its inner loop, so there isn''t much you can do to make a correctly implemented quicksort go faster. ''Simple'' multithreading won''t help, as the costs of spawning a new thread will dominate. And unless you have a multiprocessor system, the threads will have to share your one CPU anyway, adding context-switching costs to the mix. So, it''s really not worth it.

On the other hand, if you were using a real parallel machine (with independent CPU nodes and bus lines, not just a SMP system), there would indeed be techniques you could apply to make the sort go faster. A number of libraries are available for that purpose (e.g. OpenMP). Languages like Fortran even integrate parallel control flow statements (FORALL, WHERE).

So, in the end, you''re better off just using an existing quicksort (or hybrid sorting algorithms) implementation (C : qsort(), C++ : std::sort()), rather than worry overmuch over how to make it faster.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites
Actually, the fastest sorting algorithm is the insertion sort. O(n) best case. Of course, average and worst case are O(n^2), but if you know the behavior of what you are sorting sometimes insertion is the best. For example, the current game I''m working on sorts all the sprites based on bounding positions every frame so they are drawn in the proper order. Since most of the time the sprites will already be in order, or at worst one or two sprites are out of order, insertion sort is significantly faster than any other.

Share this post


Link to post
Share on other sites
That''s why you have hybrid sorting routines which adapt their sorting algorithm to the data they''re given. Common sort() implementation use insertion sort for small ranges, where it actually is faster than quicksort, and use quicksort to break down larger ranges into smaller ones where insertion sort is used.

Share this post


Link to post
Share on other sites
quote:
Original post by Fruny
Quicksort is O(n log n) on average, O(n^2) worst-case.
Quicksort can be implemented with O(n log n) worst case. Some common implementations just happen to have O(n^2) worst case because the constant is smaller then and the worst case is rare.

Share this post


Link to post
Share on other sites
Different sorts are best for different things ...

Certain sorts will be very slow with very random data, others will be slow with pre-sorted data, and yet more will be slow with reverse sorted data (i.e. data which is in the reverse order to which it should be on a 1:1 basis).

Profile the code & tailor it to use an algorithm to suit your needs

Tom L

Share this post


Link to post
Share on other sites
Quicksort is not effective for fewer than about 50 items, after that, its average performance actually begins to show, and yes, it is O(n*log(n))

MergeSort is somewhat more complex, and guarantees O(n*log(n)) time complexity and O(n) space complexity for ANY AND ALL inputs, and it generally isn't hard to code, but it's hard to optimize (a somewhat redundant algorithm). An exception, is bottom-up imlementations on linked lists, where mergesort really shines.

InsertionSort is linear in the number of inversions, so in the worst case (string is reverse-sorted to begin with) it is O(n^2). However, for partially sorted lists, it is VERY fast, and it is also extremely simple and robust.

HeapSort also guarantees O(n*log(n)) time complexity and O(n) space complexity. It is easy to implement on arrays, and is great if you'll be using the sorted set for something like a spatial sweep, because it is designed to provided lowest (or highest) element at each step.

RADIX sort is very very fast: O(n) for integers and strings, however, it's a little confusing to code.

RADIX' little brother is BucketSort, which is also O(n+h) and is used on discreet sets. h is the range of values that are in the set (so if you know you're sorting twenty integers from 17 to 37, then that's an ideal case because it's O(n+n)=O(n))

BubbleSort is the most awful algorithm you could hope to use. it is O(n^3), its only positive feature is that a single sweep will find you either the maximum value or the minimum value, so you can use it to find the highest or lowest few values if that's all your interested in. However, if you have about 1000 values, even this is too complex for you to use, in which case you should just go with heap-sort.

EDIT: confused bubble sort with quick sort

George D. Filiotis

I am a signature virus. Please add me to your signature so that I may multiply.

[edited by - symphonic on March 8, 2003 9:33:00 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!