Рассматриваю простые сортировки массивов.Делаю сортировку вставками(без барьера). Но в книге Вирта "Алгоритмы и структура данных" она написана с барьером , соответственно и количество сравнений(они же ключи) ( C ) и количество перестановок (пересылок) (М) посчитаны для кода с барьером. По сему вопрос : как самому посчитать эти С и М , есть ли какой-либо алгоритм , как у подсчета сложности (эти О(n^2) )?
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
const int N =7;
void vstavki(int *P)
{
int i = 0, j = 0,x=0;
for (i = 1; i <= N - 1; i++)
{
j = i;
x = *(P + i);
while (j > 0 && x < P[j - 1])
{
P[j] = P[j - 1];
j--;
}
P[j] = x;
}
}
int main()
{
srand(time(NULL));
int A[N], i = 0, j = 0, k = 0;
while (i < N)
{
*(A+i) = rand() % 100;
printf("%4d", *(A+i));
i++;
}
vstavki(A);
printf("\n");
for (i = 0; i < N; i++)
{
printf("%4d", A[i]);
}
_getch();
return 0;
}
i-1
раз, что дает2 * (i - 1)
M иi - 1
C. K выполнений внутреннего цикла добавитK-1
C и K M (K-1, поскольку первое сравнение мы учли в составе выполнений внешнего цикла. Остается определить, чему в среднем равно K -)