Quick Sort
It probably does use recursion, but remember that qsort takes a function pointer to do its comparison; in C++, that function can be inlined directly into the std::sort code, even if the routine itself has to be out-of-line. Saving cycles in the comparison function of a sorting algorithm is obviously a Very Good Thing--especially when you take into account the fact that a simple comparison function will be dominated by function call overhead.
quote:Original post by Stoffel
Saving cycles in the comparison function of a sorting algorithm is obviously a Very Good Thing--especially when you take into account the fact that a simple comparison function will be dominated by function call overhead.
I wrote a non-recursive (stack base) quicksort function using a template to accept the comparison operator (it used median-of-three for pivot picking, and insertion sort for sets of 16 or less items). When I benchmarked it (in GCC 2.95.3) it was about 16 times faster than the glibc qsort function (with 10,000 items). The glibc qsort function is much faster than the msvcrt qsort function, if you need a comparison basis.
[Resist Windows XP''s Invasive Production Activation Technology!]
quicksort = unstable, O(n log n)
radix sort = stable, O(n)
Give this a try (tested and works under borland c++):
Note: due to the dynamic nature of vectors, the performance of this example will be poor (and probably won''t run in linear time, due to memory fragmentation or something). That was only to give you the idea. The radix sort is better suited to linked lists. I don''t have a link to the theory on this sort right now, so you''ll need to look for yourself.
radix sort = stable, O(n)
Give this a try (tested and works under borland c++):
#include <vector>void radix_sort(int *int_array, int size) { for(int shift = 0; shift < 32; shift += 8) { std::vector<int> bucket[256]; // That''s not a typo. 256 vectors. int *current_int = int_array; for(int i = 0; i < size; i++) { int bucket_no = ((*current_int) >> shift) & 0xFF; bucket[bucket_no].push_back(*current_int); ++current_int; } current_int = int_array; for(int i = 0; i < 256; i++) { std::vector<int>::iterator j; for(j = bucket[i].begin(); j != bucket[i].end(); ++j) { *current_int = *j; ++current_int; } } }} Note: due to the dynamic nature of vectors, the performance of this example will be poor (and probably won''t run in linear time, due to memory fragmentation or something). That was only to give you the idea. The radix sort is better suited to linked lists. I don''t have a link to the theory on this sort right now, so you''ll need to look for yourself.
quote:Original post by Beer Hunter
quicksort = unstable, O(n log n)
radix sort = stable, O(n)
But I thought in practice quicksort was the fastest overall, even as n->inf. Could be wrong, my alg. course was a long time ago.
I think that O(N Log N) is the fastest you can get with a simple compare-and-swap method, whereas radix sort relies on being able to compare part of a value rather than the whole value, as well as requiring extra memory to operate. Although it can be thought of as O(N), it can (perhaps more accurately) also be considered as O(K x N) as there is another factor in there, that depends on the type of data you''re sorting.
Read this: Radix Sort Revisited for details.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]
Read this: Radix Sort Revisited for details.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]
Stoffel - Go to this page, and look down the bottom for Andre Reinald's optimised radix sort for integer arrays. Then compare it to any quicksort you like.
Kylotan - It's true that the radix sort requires extra memory, but if you use it on linked lists, you only need to keep track of the head and tail of each bucket, which isn't much when you have only 256 buckets. Thanks for the link; I didn't think the radix sort could work on floats. But however you look at O(kn), it's still linear time...
I will readily admit, things do change when you're sorting strings. Although the radix sort can be used, I would think it leaves a lot of room for improvement.
Edited by - Beer Hunter on December 21, 2001 1:29:05 AM
Kylotan - It's true that the radix sort requires extra memory, but if you use it on linked lists, you only need to keep track of the head and tail of each bucket, which isn't much when you have only 256 buckets. Thanks for the link; I didn't think the radix sort could work on floats. But however you look at O(kn), it's still linear time...
I will readily admit, things do change when you're sorting strings. Although the radix sort can be used, I would think it leaves a lot of room for improvement.
Edited by - Beer Hunter on December 21, 2001 1:29:05 AM
quote:Original post by Beer Hunter
Kylotan - It''s true that the radix sort requires extra memory, but if you use it on linked lists, you only need to keep track of the head and tail of each bucket, which isn''t much when you have only 256 buckets. Thanks for the link; I didn''t think the radix sort could work on floats. But however you look at O(kn), it''s still linear time...
Well, yeah it''s linear time, but there are plenty of unusuable linear time algos, since the constant is so damn high. In the case of the radix sort, the work is proportionate to (list length * number of digits)
That means the radix sort does best when working with lots of small numbers. If you''re sorting a small or medium sized list which contains large numbers, quicksort is going to be faster.
Radix sort works great with big lists of low numbers, which are a really common application of sorting. It''s not a great /general/ purpose sort, though.
BeerHunter: That page is down!
But I believe you. I think I remember now that my prof said QS is the best in-place sort, so there ya go. My alg course was in ''95, so that''s my excuse. =)
But I believe you. I think I remember now that my prof said QS is the best in-place sort, so there ya go. My alg course was in ''95, so that''s my excuse. =)
AP (Kylotan?) - Yes, the radix sort requires more iterations for larger data types. But what about the extra time taken up by the more complicated comparisons in a quicksort, or any other sort? I''m fairly sure that the quicksort is better at sorting variable-length strings, though.
Stoffel - Try the page again, maybe it was down temporarily. The radix-sort isn''t an in-place sort (well, not on arrays, anyway); for arrays, the quicksort still is the fastest in-place sort.
Stoffel - Try the page again, maybe it was down temporarily. The radix-sort isn''t an in-place sort (well, not on arrays, anyway); for arrays, the quicksort still is the fastest in-place sort.
quote:Original post by Stoffel
Original post by Beer Hunter
quicksort = unstable, O(n log n)
radix sort = stable, O(n)
....
But I thought in practice quicksort was the fastest overall, even as n->inf. Could be wrong, my alg. course was a long time ago.
The quick-sort will actually be quite slow if the data is already sorted (as will the radix method)... ->O(n2).
I always thought it was an odd quirk that an algotihm that sorts randomly data quickly, re-sorts data very slowly...
Magmai Kai Holmlor
"Oh, like you've never written buggy code" - Lee
"What I see is a system that _could do anything - but currently does nothing !" - Anonymous CEO
Edited by - Magmai Kai Holmlor on December 22, 2001 1:01:33 AM
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
