Как посчитать количество сравниваний и перемещений элементов в алгоритме быстрой сортировки?

Question

[parkito]

Реализовал алгоритм быстрой сортировки. Подскажите, куда нужно поставить счетчики, чтобы посчитать, сколько раз элементы матрицы сравнивались между собой и сколько раз перемещались?

void quick(int *temp, int i, int j)
{
int c, x,t=0;
m=i; k=j;
c=temp[(m+k) / 2];
do
{while (temp[m]<c) m++;
while (temp[k]>c) k--;
if (m<=k)
{if(m!=k)NazQuick++;
x=temp[m];
temp[m]=temp[k];
temp[k]=x;
m++;
k--;
}t++;
} while (m<k);
if (i<k) quick(temp, i, k);
if (m<j) quick(temp, m, j);
}

Answer 1

[Никита Колосов]

Не могу придумать ничего умнее, чем сказать "после каждого сравнения и после каждого перемещения"

Answer 2

[Дмитрий Гукетлев]

Попробуйте перестать использовать однобуквенные переменные. Хотел помочь, но лень разбираться в коде.

Comments

[tsarevfs]

+ отступы, например так.

Answer 3

[parkito]

Делаю вот так

void quick(int *temp, int i, int j)
{
int c, x,t=0;
m=i; k=j;
c=temp[(m+k) / 2];
do
{SravQuick++;
while (temp[m]<c) m++;
while (temp[k]>c) k--;
if (m<=k)
{if(m!=k)NazQuick++;
x=temp[m];
temp[m]=temp[k];
temp[k]=x;
m++;
k--;
}t++;
} while (m<k);
if (i<k) quick(temp, i, k);
if (m<j) quick(temp, m, j);
}

Однако считается некорректно.

Answer 4

[xandox]

Это же аналитически считается. Зачем счетчики? Возьми книжку по алгоритмам какую-нибудь. Там в первых главах написано как и что подсчитать.

Answer 5

[xseven]

Аналитически считается сложность/скорость роста. Ясно что в общем случае для алгоритма сравнениями не может быть быстрее, чем nlogn
Чтобы посчитать более корректно нужно перегрузить операторы присваивания сравнения и т.д. и встроить в них счетчик по типу этого

Хотя @xandox был прав - зачем?