Hey,
Since I never learned programming in school I figured I'd visit some of the common problem sets that most programs put you through. One of these problems sets was learning all the different sorting methods.
On the wikipedia quick sort page it says that insertion sort is faster on smaller arrays and alot of quick sorts use insertion sorts when they get down into the small arrays in the recursion. I was thinking about adding insertion sort into my quick sort algorithm to see if I can increase its speed.
So far I have clocked it at sorting 10 million randomly generated integers in 10-11 seconds. I wanted to see if I could increase that time, but every simulated test I have done shows that the quicksort is outperforming the insertion sort or at least equivalent even on small arrays of 10 or less. Since both finish the sorts in under a second its hard to notice a difference, and when I put a integar to show how many loops are done the quicksort is still a smaller number.
Any suggestions?
Code:
void ReadAndSort::QuickSort(int left, int right)
{
int pivot = Numbers[(left+right)/2];
int x = left;
int y = right;
while(x <= y)
{
while(Numbers[x] < pivot)
x++;
while(Numbers[y] > pivot)
y--;
if(x <= y)
{
Swap(Numbers[x], Numbers[y]);
x++;
y--;
}
timesran++;
}
if(left < y)
QuickSort(left, y);
if(x < right)
QuickSort(x, right);
}
void ReadAndSort::InsertionSort()
{
double Timeslooped = 0;
int j = 0;
for(int x = 1; x < Numbers.size()-1; x++)
{
j = x;
while( j > 0 && Numbers[j-1] > Numbers[j] )
{
int Temp = Numbers[j];
Numbers[j] = Numbers[j-1];
Numbers[j-1] = Temp;
j--;
Timeslooped++;
}
}
cout<<"Insertion sort took "<<Timeslooped<<" iterations."<<endl;
}
Just to be clear the ReadAndSort class reads all the numbers in a file then sorts them then saves back to the file the newly sorted result. Numbers is a vector that it uses to hold all the numbers while sorting.
Also if you notice any glaring weaknesses in the code please let me know. Thanks!