Algoritmi za urejanje tabel

V C sem si napisal bubble sort, selection sort in insertion sort. Za foro sem še izmeril koliko časa porabi kateri algoritem za urejanje in koliko primerjav in prirejanj pri tem opravi. Naredil sem 3 identične tabele in vsako spustil skozi en algoritem. Vedno se je izkazalo, da je najpočasnejši bubble sort, najhitrejši pa insertion sort. Kar me je pa najbolj presenetilo, je izjemno majhno število primerjav in prirejanj za selection sort. Tu so npr. podatki za tabelo 100 elementov:

bubblesort
primerjave: 2362
prirejanja: 7086
bubblesort: 0.000037

selectsort
primerjave: 316
prirejanja: 712
selectsort: 0.000024

insertsort
primerjave: 4724
prirejanja: 5021
insertsort: 0.000014

Kako to, da ima insertion sort desetkrat več primerjav in prirejanj, pa uredi tabelo prej kot selection sort? Podobne rezultate sem dobil tudi pri velikosti 10000 elementov in več.

Elementi so random:

for(i = 0; i < n; i++) {
	int x = rand() % 20000000;
	arr0[i] = x;
	arr1[i] = x;
	arr2[i] = x;
}

Bubblesort:

void bubblesort(int *a, int n) {
	int primerjave = 0;
	int prirejanja = 0;
	int i,j;

	for(i = n-1; i > 0; i--) {			// skozi tabelo of zadaj naprej
		for(j = 0; j <= i; j++) {		// od začetka do meje z neurejenim delom
			if(a[j] > a[j+1]) {		// če je x večji od naslednjega ju obrnemo
				primerjave++;

				int tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
				prirejanja += 3;
			}
		}
	}
	printf("bubblesort\nprimerjave: %d\nprirejanja: %d\n", primerjave,prirejanja);
}

Selection sort:

void selectsort(int *a, int n) {
	int primerjave = 0;
	int prirejanja = 0;
	int i,j;

	for(i = 0; i < n-1; i++) {
		int min = i;
		prirejanja++;
		for(j = i+1; j < n; j++) {
			if(a[j] < a[min]) {
				primerjave++;

				min = j;
				prirejanja++;
			}
		}
		int tmp = a[min];
		a[min] = a[i];	
		a[i] = tmp;
		prirejanja += 3;
	}
	printf("selectsort\nprimerjave: %d\nprirejanja: %d\n", primerjave,prirejanja);
}

Insertion sort:

void insertsort(int *a, int n) {
	int primerjave = 0;
	int prirejanja = 0;
	int i;

	for(i = 1; i < n; i++) {	
		int v = a[i];	
		int j = i-1;	
		prirejanja += 2;

		while((j >= 0) && (a[j] > v)) {		
			primerjave += 2;

			a[j+1] = a[j];		
			j--;
			prirejanja += 2;
		}
		a[j+1] = v;
		prirejanja++;
	}
	printf("insertsort\nprimerjave: %d\nprirejanja: %d\n", primerjave,prirejanja);
}

Za merjenje časa imam takole:

clock_t start = clock();
bubblesort(arr0,n);
clock_t end = clock();
double seconds = (double)(end - start) / CLOCKS_PER_SEC;
printf("bubblesort: %f\n",seconds);

Pa res, sedaj dobim bolj smiselne (pričakovane) rezultate. Hvala.