Jump to content
  • Advertisement

Archived

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

NightwingX

Quick Sort

This topic is 6021 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

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

}
  

Share this post


Link to post
Share on other sites
Advertisement
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
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
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
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
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
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

  • 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!