Archived

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

vaneger

fastest sorting???

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
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
Quicksort can never be implemented in worst case O(nlgn)(AFAIK)[EDIT: YES it can, im a moron ], BUT Randomized Quicksort(which is really the original quicksort as it was originally put forward) runs in *expected* O(nlgn) time(which is pretty good).
There is also the median-of-three method for choosing the pivot element, which also helps avoid the worst case behavior(but the worst case remains n^2).

If you have no clue about the data you are sorting, Randomized quicksort is indeed the best bet. But as already mentioned, if you are sorting something that is almost in order, insertion sort will be faster.
If the key to be sorted on is number of limited size then Radix sort can sort it in O(n).


[edited by - ziphnor on March 8, 2003 7:30:27 AM]

[edited by - ziphnor on March 8, 2003 5:15:58 PM]

Share this post


Link to post
Share on other sites
After I read this thread, I was on the john and thinking about a fast sorting algorithm. And I recalled the hash table data structure from my Data Structures book by Ron Penton. Basically a hash table "mashes" a value of a key down to fit into its corresponding array that has less indices than the large number key. This can be done my moduloing all the keys that you want to store in an array. Take this example: you have 3 numbers, 123, 6 and 1000, and keep in mind that these are access keys for something else. Obviously, making an array of size 1001 is very tedious and memory hungry, correct? Well, with a hash table algo, you can "compress" the range of the keys to a manageable size. Assume the size of the array is 5 indices. You''d mash these keys by moduloing each key number by the size of the array. Let''s do that: 1000 % 5 = 0(index 0), 123 % 5 = 3(index 3), 6 % 5 = 1(index 1). As one can see, the array will not be in order of number size, which is what we want...hmmmm. How about dividing instead of moduloing. Try that and you''ll see that it works, but the size of the array is minimized by the largest value divided by the size of the array. Retrieving the value is simply a reverse process: 1000 / 5 = 200(index 200), 200 * 5 = 1000. As you can see, I borrowed some ideas from hash tables and made them my own. I do not know if this has been done for sorting or if this even works at all. But if it has been done, then maybe it is called Hash Sorting.

As many of you know, if you know about hash tables, there is a problem of "collision." That is, if you divide two multiples of 5 by the size of the array, 5, then you will end up with the same index, even when moduloing. As stated in my Data Structures book, then may be overcome by using prime numbers for the size of the array. One can easily see the advantages of this. Why use prime #''s? Because they can only be divided by one and them selve to obtain an integer result. So, 7 is prime, so is 3. 211 / 1 = 211, 211 / 211 = 1. But what if you are dividing in a non factoral number of 211, like the index size, 5? Well, somehow you''d take the integer part of that number. And that''s up to YOU to figure out

Share this post


Link to post
Share on other sites
Multithreading will not get you anywhere any faster, as multithreading will not increase the CPU frequency of your computer. Multithreading will only make things slower. (Unless you are using a computer with multiple CPUs)



Update GameDev.net system time campaign - success at last

[edited by - dalleboy on March 8, 2003 10:58:10 AM]

Share this post


Link to post
Share on other sites
I''d suggest checking out:

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

It has some great java applets showing the different sort algorithms and source is included (in java... but it''s quite simple to port to C)

Hope this helps

~Shaun

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:

Quicksort can never be implemented in worst case O(nlgn)(AFAIK), BUT Randomized Quicksort(which is really the original quicksort as it was originally put forward) runs in *expected* O(nlgn) time(which is pretty good).
There is also the median-of-three method for choosing the pivot element, which also helps avoid the worst case behavior(but the worst case remains n^2).



You can also set a cutoff for what size of ranges of indeces you want to sort. Meaning instead of recurring down until you have one element, recur until you have 5 or 10. Stop at this point and when the rest of Quicksort is done, run Selectionsort. Selection sort works best when the elements are ''almost'' sorted, which is what the Quicksort with a cutoff will yield.

Share this post


Link to post
Share on other sites
quote:
Original post by Ziphnor
Quicksort can never be implemented in worst case O(nlgn)(AFAIK)
Yes, median-of-three won''t cut it. But all you need is a median-of-n in O(n) time and bam, you''ve got yourself a O(n log n) worst case quicksort. I don''t have a link handy to such median finding algo but I know it exists.

Share this post


Link to post
Share on other sites
DOH... Forgot that it was possible to calculate the median in linear time, silly me ;( You are right of course.

Its particular embarrasing as i attended a lecture yesterday where this very fact was used in another algorithm

[edited by - ziphnor on March 8, 2003 5:17:16 PM]

Share this post


Link to post
Share on other sites
Hashing is the premise of radix sorting.

The bubble sort takes the least amount code, I crammed one into about 10 bytes of VAX assembly.

- Magmai Kai Holmlor

"Oh, like you''ve never written buggy code" - Lee

[Look for information | GDNet Start Here | GDNet Search Tool | GDNet FAQ | MSDN RTF[L] | SGI STL Docs | STFW | Asking Smart Questions ]

[Free C++ Libraries | Boost | ACE | Loki | MTL | Blitz++ | wxWindows| Spirit(xBNF)]
[Free C Libraries | zlib ]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
In almost all cases, it is best to stick with the STL std::sort() or STL std::stablesort() functions.

sort() uses a combination of a semi-iterative/recursive 3-median quicksort, heapsort and insertionsort. Both quicksort and insertion sort have really nice tweaks such as not having to be guarded against running off the end of the array.

stablesort() uses a fully iterative mergesort and insertionsort. It can be faster than sort() but I usually find it to be slower (on ix68 and sparc machines).

Both of these perform better as the data becomes more and more sorted, though insertion sort is still roughly 2 times faster for fully sorted data. However, I find that at 96% sortedness, insertion sort does extremely poorly so it''s best to stick with sort() even if you suspect your data to be partially sorted.

Of course, there is the famous radix sort which is O(n). This only holds because your ints and floats have an upper bound in size. I have found that radix sort is extremely extremely fast for sorting linked-lists of ints and IEEE floats. It will also beet the STL sort() by roughly two times for arrays of ints (32 bit) and floats, but not for doubles. I think I used 256 buckets and bit operations to extract each byte of the int. IEEE floats require extra bit flipping if you want to sort negative numbers, otherwise you can simply cast them to ints. The array based radix sort uses a temp array to copy to and from. This means that, much like merge sort, it is susceptible to more cache misses for a given size array when compared to inplace algorithms like heap and quicksort.

Conclusion: If you are sorting ints or floats, look at radix sort. Otherwise stick to the STL sorting algorithms (they are templated). Unless you want to try my Parallel Adaptive Sort, but that is still in the works.

Marek

PS If you have a parallel sorting algorithm that I can compare mine against. Send me an email: m.olszewski @ utoronto.ca.

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
The bubble sort takes the least amount code, I crammed one into about 10 bytes of VAX assembly.



And, just IMHO, it should be the first sort shown to students precisely because it''s so simple. Then other sorts will be easier to comprehend.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Marek

PS If you have a parallel sorting algorithm that I can compare mine against. Send me an email: m.olszewski @ utoronto.ca.



Aha, I recognize that name This guy is continuing (in a rather different direction, apparently) on my (undergrad) thesis work, and knows what he''s talking about here.

(It''s worth noting that stablesort() will guarantee, well, a stable sort - i.e. if x comes before y in the original list, and x "equals" y according to the comparison function, then x will be before y in the sorted list. Removing this guarantee sometimes allows faster sorting, but when this property is needed, make sure you have it. )

To elaborate: for my thesis I tried to develop AI to optimize divide-and-conquer algorithms, by choosing the ''subalgorithm'' to use at each step. I happened to choose sorting as my "test problem", so it basically attempted to do what std::sort() does, except gathering a bunch of raw data in order to determine the cutoff points for switching the sorting method - and also not using very sophisticated sorting code, because I was writing it all myself :/ A fine example of how not to do real-world work, but it made for interesting study. (It was also my last - in the sense of most recent, but hopefully I won''t have to again! - attempt at using C++, which has never worked out very well for me. I figured I needed the template generics though. Oh well.)

BTW, the code I wrote is available at http://jove.prohosting.com/~zahlman/DaCAlOpE/DaCAlOpE.tar.gz.
You will need to download the "c4.5" decision tree code yourself, because of the author''s licensing terms.

Share this post


Link to post
Share on other sites
One convenient thing about mergesort is that it always takes the same amount of time on a given list length.

Could be usefull in a realtime application, like a game, if worst case behaviour is critically bad and nlogn best case is sufficient.

Share this post


Link to post
Share on other sites