Archived

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

NightwingX

Quick Sort

Recommended Posts

LordKronos    122
If you just want to use quick sort, try the qsort routine that is part of the C++ library. If you want the algorithm/how it works, try a searching in a search engine. I did, and here is what I came up with:

http://www.cs.usask.ca/research/research_groups/aries/projects/applets/tutorials/sorting/quick/java/index.shtml

This uses a java applet to graphicly demonstrate it. it even lets you step through the program line by line and examine the variable values at each step

Share this post


Link to post
Share on other sites
Floppy    122
The Quicksort is extremely easy (why not use the shell sort? or some other "divide and conquer" method?)

Here's the code:
  
void quicksort(itemType a[], int l, int r)
{
int i, j;
itemType v;

if(r > l)
{
v = a[r];
i = l-1;
j = r;

for(;;)
{
while(a[++i] < v);
while(a[--j] > v);
if(i >= j) break;
swap(a, i, j);
}

swap(a, i, r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
}


Edited by - Floppy on December 18, 2001 8:04:42 PM

Edited by - Floppy on December 18, 2001 8:05:15 PM

Share this post


Link to post
Share on other sites
Null and Void    1088
The C standard library has the quicksort function implemented as "qsort" (you can look that up easily). The "sort" algorithm (in C++) may use a quicksort algorithm (I''m not sure, though) It''s a somewhat complex algorithm to explain (there''s a couple varieties of it). I think there''s a tutorial here on gamedev about the quicksort algorithm, otherwise try google (it''s always done well for me ).

[Resist Windows XP''s Invasive Production Activation Technology!]

Share this post


Link to post
Share on other sites
Floppy    122
The quicksort is really easy to explain if you just follow through the code.

Make a small list of number, and then do what the code would do if you inputted those values. Just follow the code keeping track of the variables, etc. It''s really simple.

If you don''t want a recursive quicksort algorithm you''ll need to use a stack to push and pop the values off the stack. If you really need it I could get if for you.

Share this post


Link to post
Share on other sites
Floppy    122
Fine Null and Void you did it!!!

Here is the non-recursove implementation:
  
void quicksort(itemType a[], int l, int r)
{
int i; Stack<int> sf(50);

for(;;)
{
while(r > l)
{
i = partition(a, l, r);
if(i-l > r-i){sf.push(l); sf.push(i-1); l = i+1;}
else{sf.push(i+1); sf.push(r); r = i-l;}
}
if(sf.empty()) break;
r = sf.pop(); l = sf.pop();
}
}

There is your non-recursive quiskort()

Share this post


Link to post
Share on other sites
ugenn    122
quote:
Original post by NightwingX
Were can I find the quick sort agrothim? Can anybody explain to me how this works?


    
//Now for my next trick

for(;;)
{
//We all live in a world of errors

}


Basically, in a nutshell, the quicksort uses a divide n conquer strategy by first partitioning the list into 2 sublists where all the values in one list are lesser than those in the other and then calling itself recursively on these sublists (well, non- recursively is also possible if you use your own stack ADT).
Some psuedocode to illustrate...

qsort( list, int lo, int hi )
{
if lo >= hi return // termination condition
pivot = partition( list, lo, hi )
qsort( list, lo, pivot-1 )
qsort( list, pivot+1, hi )
}

Goto google.com and do a search for quicksort if you need more in-depth explaination.
Rgds.

Share this post


Link to post
Share on other sites
Stoffel    250
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.

Share this post


Link to post
Share on other sites
Null and Void    1088
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!]

Share this post


Link to post
Share on other sites
Beer Hunter    712
quicksort = unstable, O(n log n)
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.

Share this post


Link to post
Share on other sites
Stoffel    250
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.

Share this post


Link to post
Share on other sites
Kylotan    10007
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 ]

Share this post


Link to post
Share on other sites
Beer Hunter    712
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Stoffel    250
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. =)

Share this post


Link to post
Share on other sites
Beer Hunter    712
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.

Share this post


Link to post
Share on other sites
Shannon Barber    1681
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

Share this post


Link to post
Share on other sites
Beer Hunter    712
Magmai - if you always use the first element as the pivot, then yes, quicksort -> O(n2). That is why we don''t use the first element as the pivot


void quicksort(int *sort_array, int size) {
    quicksort2(sort_array, 0, size - 1); // "almost" sort the array.
    insertion_sort(sort_array, size);
}

void quicksort2(int *sort_array, int lo, int hi) {
    if((hi - lo) <= 4) return; // the insertion sort copes with this.
    int med = (lo + hi) >> 1;
    if(sort_array[lo] > sort_array[hi]) swap(lo, hi);
    if(sort_array[lo] > sort_array[med]) swap(lo, med);
    if(sort_array[med] > sort_array[hi]) swap(med, hi);
// now use "med" as the pivot.

...there are other ways to do it, but this is a start.

Share this post


Link to post
Share on other sites