void QuickSort(int list[], int start, int end)
{
if (start >= end) // base case (list is sorted)
return;
// choose a pivot point
int pivot = list[(start+end)/2];
int leftbound = start;
int rightbound = end;
while (leftbound <= rightbound)
{
// find first element that is greater than pivot on left side
while ((leftbound < end) && (list[leftbound] < pivot))
leftbound++;
// find first element that is smaller than pivot on right side
while ((rightbound > start) && (list[rightbound] > pivot))
rightbound--;
// swap if indexes haven't crossed
if (leftbound <= rightbound)
{
int temp = list[leftbound];
list[leftbound] = list[rightbound];
list[rightbound] = temp;
leftbound++;
rightbound--;
}
}
QuickSort(list, start, rightbound); // sort left
QuickSort(list, leftbound, end); // sort right
}
20 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
Fastest QuickSort?
May 06, 2001 09:02 PM
Does anyone have a quick, small Quicksort function?
This is all I came up with:
Some folks call it a sling blade...I call it a keiser blade.
1,088
May 06, 2001 09:19 PM
This is the one I use (I didn''t write it, but it is incredibly fast compared to MSVC''s or Borland''s standard qsort):
http://druidgames.cjb.net/
|
http://druidgames.cjb.net/
1,088
May 06, 2001 09:20 PM
Well, it got mangled by the source tags, but if you want a copy, I''ll email it to you (complete with the tiny header I wrote for it). Copy/Pasting from IE mangles it even more 
.
http://druidgames.cjb.net/
. http://druidgames.cjb.net/
712
May 07, 2001 02:17 AM
Of course, for a small amount of extra memory, you could use the radix sort, which will always be faster than the fast quicksort. But if memory is a real issue, then the fast quicksort is good.
One thing I''d change on that implementation, though, is to run the insertion sort only after the entire quicksorting process is done. I doubt there''d much of an increase in speed, but doing the insertion sorting in one go looks cleaner to me.
One thing I''d change on that implementation, though, is to run the insertion sort only after the entire quicksorting process is done. I doubt there''d much of an increase in speed, but doing the insertion sorting in one go looks cleaner to me.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement