//Now for my next trick
for(;;)
{
//We all live in a world of errors
}
Quick Sort
Author
Were can I find the quick sort agrothim? Can anybody explain to me how this works?
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
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
The Quicksort is extremely easy (why not use the shell sort? or some other "divide and conquer" method?)
Here's the code:
Edited by - Floppy on December 18, 2001 8:04:42 PM
Edited by - Floppy on December 18, 2001 8:05:15 PM
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
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!]
). [Resist Windows XP''s Invasive Production Activation Technology!]
quote:Original post by Floppy
swap(a, i, r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
Ahh, recursion
! Heh. I''d personally advise using a stack instead of recursion for a production-quality quicksort implementation . [Resist Windows XP''s Invasive Production Activation Technology!]
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.
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.
Fine Null and Void you did it!!!
Here is the non-recursove implementation:
There is your non-recursive quiskort()
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()
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 trickfor(;;){ //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.
Does that mean std::sort doesn''t use recursion? I can''t make sense of anything in the STL headers.....
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
