#### Archived

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

# Quick Sort

This topic is 6120 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
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:

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 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 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 on other sites
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!]

##### 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 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 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(); }}

##### 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 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.

##### Share on other sites
FYI: std::sort is also quicksort, but inlined and potentially faster than qsort.

##### Share on other sites
Does that mean std::sort doesn''t use recursion? I can''t make sense of anything in the STL headers.....

1. 1
2. 2
3. 3
Rutin
17
4. 4
5. 5
JoeJ
13

• 9
• 14
• 10
• 25
• 9
• ### Forum Statistics

• Total Topics
632645
• Total Posts
3007628
• ### Who's Online (See full list)

There are no registered users currently online

×