 |  |  |  |  |  |  |  |
Quicksort/Insertion sort Hyrbid?
 |
Recently we have been asked to create a hybrid sort based upon quicksorting down to a certain point and insertion sorting from then on. We are to calculate the efficency based upon previous tests. I had very little problems implementing a quicksort algorithm, but for the life of me, I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?
•
•
•
•
Originally Posted by Jpowers22
Recently we have been asked to create a hybrid sort based upon quicksorting down to a certain point and insertion sorting from then on. We are to calculate the efficency based upon previous tests. I had very little problems implementing a quicksort algorithm, but for the life of me, I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?
C Syntax (Toggle Plain Text)
Sorry, I have to get back to work. If you could please post code, I can take a look later and help you out more.
I always find it instructive to see what others have done, and then apply my own style and ideas to the problem. In the case of a Quicksort/Insertion sort hybrid, you could look in Google for some other folk's source code, or if you have VC++, you can look at the source code for their 'qsort()' function. It is not recursive and therefore a bit ugly, but it works great. They've got tuning variables in there for figuring out at what point the insertion sort kicks in.
Like I say, don't copy their code but learn from it.
Like I say, don't copy their code but learn from it.
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
This is code I used for Left most sorting an array of randomly generated data integer elements.
Basically I want, the program to recurse to the point where insertion sort is more optimal than quicksort...and I honestly don't even have a clue where to start.
{
q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
This is code I used for Left most sorting an array of randomly generated data integer elements.
Basically I want, the program to recurse to the point where insertion sort is more optimal than quicksort...and I honestly don't even have a clue where to start.
Assuming you have an insertion sort routine, try this modification to your code:
and then just tinker with INSERTION_SORT_THRESHOLD's value to see what happens. For example, make it zero to disable the insertion sort, make it huge to ONLY do an insertion sort, and then try something like 5 or 10.
On Windows, you can use GetTickCount() to return the time since boot in miliseconds (mod 32 bits), and that can make for a simple elapsed time counter:
This isn't perfect for production code because the tick count will flip over eventually, but for your testing on where to put the insertion sort threshold this should do fine.
C Syntax (Toggle Plain Text)
and then just tinker with INSERTION_SORT_THRESHOLD's value to see what happens. For example, make it zero to disable the insertion sort, make it huge to ONLY do an insertion sort, and then try something like 5 or 10.
On Windows, you can use GetTickCount() to return the time since boot in miliseconds (mod 32 bits), and that can make for a simple elapsed time counter:
C Syntax (Toggle Plain Text)
This isn't perfect for production code because the tick count will flip over eventually, but for your testing on where to put the insertion sort threshold this should do fine.
>I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?
Oddly enough, I posted the full implementation for an optimized quicksort in the code snippets on this site. One of the optimizations is terminating recursion on small subfiles and then calling insertion sort on the "almost" sorted file. An alternative is to use insertion sort during recursion, but that typically has less desirable properties than waiting until after the recursive steps. Because you're testing performance, it couldn't hurt to implement both and see what you get.
I also give examples of two other improvements to the basic algorithm, one common and the other not so common because it's rather difficult and not well known.
>to recurse to the point where insertion sort is more optimal than quicksort
This really needs to be tweaked by the implementor, but a cutoff somewhere between 5 and 25 will work nicely in general and that's where you usually find yourself setting it.
Oddly enough, I posted the full implementation for an optimized quicksort in the code snippets on this site. One of the optimizations is terminating recursion on small subfiles and then calling insertion sort on the "almost" sorted file. An alternative is to use insertion sort during recursion, but that typically has less desirable properties than waiting until after the recursive steps. Because you're testing performance, it couldn't hurt to implement both and see what you get.
I also give examples of two other improvements to the basic algorithm, one common and the other not so common because it's rather difficult and not well known.
>to recurse to the point where insertion sort is more optimal than quicksort
This really needs to be tweaked by the implementor, but a cutoff somewhere between 5 and 25 will work nicely in general and that's where you usually find yourself setting it.
I'm here to prove you wrong.
One interesting way to figure out optimizations is through experimentation. You can time each pass for each implementation, record results and then plot them side by side on a graph. You can make adjustments accordingly to the insertion sort version's threshold to see if there's improvements.
•
•
•
•
Originally Posted by subtronic
One interesting way to figure out optimizations is through experimentation. You can time each pass for each implementation, record results and then plot them side by side on a graph. You can make adjustments accordingly to the insertion sort version's threshold to see if there's improvements.
Thats what I did, I found that the threshold value for the size of arrays I was dealing with would show increased efficiency at around 25 and lower.
•
•
Join Date: Oct 2004
Posts: 4,013
Reputation: 
Solved Threads: 929
•
•
•
•
Originally Posted by Narue
>I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?
Oddly enough, I posted the full implementation for an optimized quicksort in the code snippets on this site. One of the optimizations is terminating recursion on small subfiles and then calling insertion sort on the "almost" sorted file. An alternative is to use insertion sort during recursion, but that typically has less desirable properties than waiting until after the recursive steps. Because you're testing performance, it couldn't hurt to implement both and see what you get.
I also give examples of two other improvements to the basic algorithm, one common and the other not so common because it's rather difficult and not well known.
>to recurse to the point where insertion sort is more optimal than quicksort
This really needs to be tweaked by the implementor, but a cutoff somewhere between 5 and 25 will work nicely in general and that's where you usually find yourself setting it.
I checked your excellent sorting snippet, and have a question. Is there a way to time this, milliseconds is much to slow? I know one could increase the size of the array, but that's not challenging. Something like a microsecond or nanosecond timer would help.
May 'the Google' be with you!
•
•
•
•
Originally Posted by vegaseat
Narue,
I checked your excellent sorting snippet, and have a question. Is there a way to time this, milliseconds is much to slow? I know one could increase the size of the array, but that's not challenging. Something like a microsecond or nanosecond timer would help.
|
Other Threads in the C Forum
- Previous Thread: 6 Line class -> Me pounding head into wall
- Next Thread: Func like getlastkey() or something like that?
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest C Posts
- Today's Posts
- Unanswered Threads
#include adobe ansi api array asterisks binarysearch changingto char character cm copyimagefile cprogramme creafecopyofanytypeoffileinc createcopyoffile csyntax database directory dynamic execv feet fgets file fork forloop frequency function getlasterror givemetehcodez global grade graphics gtkgcurlcompiling hacking hardware highest histogram i/o include incrementoperators infiniteloop input interest kernel keyboard kilometer license linked linkedlist linux linuxsegmentationfault list locate logical_drives looping loopinsideloop. lowest match matrix meter microsoft motherboard mqqueue number odf opensource owf pattern pdf performance pointer posix probleminc process program programming radix recursion recv repetition research reversing scanf scripting segmentationfault sequential shape socket socketprograming standard string systemcall threads turboc unix user voidmain() wab windows.h windowsapi
