Why do most people use insertion sort for sub-arrays that have less elements than n to optimise quick sort? I wrote an insertion sort function and shell sort function and called them with few random arrays that have 10, 50, 100 elements. It seemed that shell sort is faster (I only measured the time with clock(); I don't know if it's a good way). If it's faster than insertion sort, why don't more people use shell sort? Do I have a mistake in insertion sort function?
My Code :
double insertionSort(int *a, int size)
{
clock_t start, end;
int i, temp, pos;
start = clock();
for (i = 1; i < size; i++) {
temp = a[i];
pos = i - 1;
while (pos >= 0 && a[pos] > temp) {
a[pos + 1] = a[pos];
pos--;
}
a[pos + 1] = temp;
}
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC * 1000;
}
double shellSort(int *a, int size)
{
int gaps[8] = {701, 301, 132, 57, 23, 10, 4, 1};
int i, k , temp, pos;
clock_t start, end;
start = clock();
for (i = 0; i < 8; i++)
for (k = gaps[i]; k < size; k++) {
temp = a[k];
pos = k - gaps[i];
while (pos >= 0 && a[pos] > temp) {
a[pos + gaps[i]] = a[pos];
pos -= gaps[i];
}
a[pos + gaps[i]] = temp;
}
end = clock();
return (double)(end - start) / CLOCKS_PER_SEC * 1000;
}
Output for 5 :
Insertion Sort : Sorted in 0.002000 milliseconds
Shell Sort : Sorted in 0.001000 milliseconds
Output for 10 :
Insertion Sort : Sorted in 0.004000 milliseconds
Shell Sort : Sorted in 0.001000 milliseconds
Output for 50 :
Insertion Sort : Sorted in 0.007000 milliseconds
Shell Sort : Sorted in 0.007000 milliseconds
Output for 100 :
Insertion Sort : Sorted in 0.015000 milliseconds
Shell Sort : Sorted in 0.014000 milliseconds
Output for 200 :
Insertion Sort : Sorted in 0.040000 milliseconds
Shell Sort : Sorted in 0.028000 milliseconds
