I was benchmarking two simple sorting algoritm: selection and insertion sort. I use clock() function to measure how much time each function use. However, there is an interesting phenomenon: when the size of random array is 1000 the exuction time sometimes will be 0.0000 sec. When the size increased to 10000, everything go back to normal.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <sys/types.h>
static inline void swap(int *restrict const a, int *restrict const b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
static void selection(int *restrict const array, size_t size) {
for (size_t i = 0; i < size; i++) {
int min_index = i;
for (size_t j = i+1; j < size; j++) {
if (array[j] < array[min_index]) {
min_index = j;
}
}
swap(&array[min_index], &array[i]);
}
}
static void insertion(int *restrict const array, size_t size) {
for (size_t i = 1; i < size; i++) {
for (size_t j = i; j > 0; j--) {
if (array[j] < array[j-1]) {
swap(&array[j], &array[j-1]);
} else {
break;
}
}
}
}
int main(int argc, char const *argv[])
{
int rand_array1[10000];
int rand_array2[10000];
srand(time(NULL));
for (size_t i = 0; i < 10000; i++) {
rand_array1[i] = rand();
}
memcpy(rand_array2, rand_array1, sizeof(rand_array1));
clock_t start = clock();
insertion(rand_array1, 10000);
clock_t stop = clock();
printf("Insertion use %lf sec.\n", (double)(stop - start) / CLOCKS_PER_SEC);
start = clock();
selection(rand_array2, 10000);
stop = clock();
printf("Selection use %lf sec.\n", (double)(stop - start) / CLOCKS_PER_SEC);
return 0;
}
Output(array size 1000):
[william@Notebook Sort]$ ./a.out
Insertion use 0.002276 sec.
Selection use 0.006772 sec.
[william@Notebook Sort]$ ./a.out
Insertion use 0.001282 sec.
Selection use 0.000000 sec.
Output(array size 10000):
[william@Notebook Sort]$ ./a.out
Insertion use 0.153155 sec.
Selection use 0.102534 sec.
[william@Notebook Sort]$ ./a.out
Insertion use 0.161796 sec.
Selection use 0.141816 sec.
