Skip to main content
gamedev.net
🔒 Locked

Quick Sort

Started by NightwingX Dec 18, 2001 at 6:43 PM 27 replies 4.8k views
Original Post
NightwingX
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

}
LordKronos
LordKronos
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
Ron FrazierKronos Softwarewww.kronos-software.comMiko & Molly - Taking Puzzle Games to A Whole New Dimension
Floppy
Floppy
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
Null and Void
Null and Void
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!]
Floppy
Floppy
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.
Floppy
Floppy
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()
ugenn
ugenn
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.
Stoffel
Stoffel
FYI: std::sort is also quicksort, but inlined and potentially faster than qsort.
NuffSaid
NuffSaid
Does that mean std::sort doesn''t use recursion? I can''t make sense of anything in the STL headers.....
==========================================In a team, you either lead, follow or GET OUT OF THE WAY.
Stoffel
Stoffel
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.
Null and Void
Null and Void
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!]
Beer Hunter
Beer Hunter
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.
Stoffel
Stoffel
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.
Kylotan
Kylotan
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 ]
Beer Hunter
Beer Hunter
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
Stoffel
Stoffel
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. =)
Beer Hunter
Beer Hunter
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.
Shannon Barber
Shannon Barber
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
The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.