Počet operací srovnání a přesunů - insertion sort – C / C++ – Fórum – Programujte.com

Ahoj,

nevíte někdo, jak se dá vypočítat počet srovnání a přesunů u insertion sort pro např. 10, 20, 50, 100 prvků?

Ono zalezi taky jak ty prvky budou serazene. Pro jiz serazene pole ma mit slozitost O(n). Zaroven to znamena, ze srovnani bude cca n. Presunu bude 0, jelikoz se nic nemusi presouvat. U opacne serazeneho pole to bude neco jineho. Kazdy prvek se musi srovnavat se vsemi jiz zarazenymi a pokazde se posouvaji vsechny prvky. Odhadem bych rekl ze pocet srovnani i pocet presunu bude suma od 1 do n

Já bych to potřebovala spočítat postupně pro různé počty prvků např. tady:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>            
int main()
{
	int pole[10];
	int i, j, n, temp;
	n = 10;
	
	srand((unsigned)(time(NULL)));          
	for (i = 0; i < n; i++)                 
	pole[i] = rand();                

		/*Sort*/
	for (i = 1; i < n; i++) {
		j = i;
		while ((j > 0) && (pole[j - 1] > pole[j])) {
			temp = pole[j - 1];
			pole[j - 1] = pole[j];
			pole[j] = temp;
			j--;
		}
	}
	/* tisk */
	printf("Sorted Array\n");
	for (i = 0; i < n; i++)
		printf("%d \n", pole[i]);
	return 0;
}