#### Archived

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

# Quick Sort

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

##### Share on other sites
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 on other sites
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 on other sites
quicksort = unstable, O(n log n)

Give this a try (tested and works under borland c++):
  #include void radix_sort(int *int_array, int size) { for(int shift = 0; shift < 32; shift += 8) { std::vector 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::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 on other sites
quote:
Original post by Beer Hunter
quicksort = unstable, O(n log 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 on other sites
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.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

##### Share on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
quote:
Original post by Stoffel
Original post by Beer Hunter
quicksort = unstable, O(n log 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 on other sites
what does this do
for(;

##### Share on other sites
quote:
Original post by omegasyphon
what does this do
for(;

It is an infinite loop. It is the same as

  while(1){ //do stuff here}

##### Share on other sites
oh that didnt come out right but doing this does the what the above post said

  for(;;)

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

• ### Forum Statistics

• Total Topics
628379
• Total Posts
2982344

• 10
• 9
• 15
• 24
• 11