挿入ソートの比較操作

Question

前提・実現したいこと

c言語でデータを昇順にする挿入ソートを実装し、その挿入ソート内で比較操C作と交換操作が何回行われているのかを計測したい。

###問題
現状のコードでは、交換回数(s[3])は正しく計測できているのですが、比較回数(s[2])が正しく計測できていません。

どうやらwhile文全体ではなく、while文の2つ目の条件(array[j - 1] > array[j])の部分（比較操作）の回数を計測しないといけないようなのですが、どのようにコードを改良してもうまくいきません。
どうすればできるのかご教授願います。

該当のソースコード

void insert_sort(int array[], int array_size){
	int i,j;
	int tmp;

	s[0]++;		for(i = 1; i < array_size; i++){
	s[1]++;			j = i;
	s[2]++;			while((j >= 0) && (array[j - 1] > array[j])){
	s[3]++;				tmp = array[j];　array[j] = array[j - 1]; array[j - 1] = tmp;
	s[4]++;				j--;
	s[5]++;			}
	s[6]++;		}
}

試したこと

試しにwhile文のところを以下のように2つに分割してみたのですが、データそのものが既に昇順になっている場合に、比較操作(s[3])が（データ数が100のとき）5049回行われていることになってしまいました。
昇順挿入ソートにおいて入力データが既に昇順だった場合、比較回数はデータ数Nに対し、N－1回だと認識しているのですが、私の認識と5049回という実行結果のどちらが正しいのでしょうか。

void insert_sort(int array[], int array_size){
	int i,j;
	int tmp;

	s[0]++;		for(i = 1; i < array_size; i++){
	s[1]++;			j = i;
	s[2]++;			while(j >= 0){
	s[3]++;				while(array[j - 1] > array[j]){
	s[4]++;					tmp = array[j]; array[j] = array[j - 1]; array[j - 1] = tmp;
	s[5]++;				}
	s[6]++;				j--;
	s[7]++;			}
	s[8]++;		}
}

Answer 1

int comps; // 比較回数
int swaps; // 交換回数

int compare(int x, int y) {
  ++comps;
  return x > y;
}

void swap(int* px, int* py) {
  ++swaps;
  int tmp = *px;
  *px = *py;
  *py = tmp;
}

void insert_sort(int array[], int array_size) {
  int i,j;
  for(i = 1; i < array_size; i++){
    j = i;
    while((j >= 0) && compare(array[j - 1], array[j] ) {
      swap(&array[j-1], &array[j]);
      j--;
    }
  }
}

#define N 123

int main() {
  int data[N] = { .... };
  comps = 0;
  swaps = 0;
  insert_sort(data, N);
  // compsとswapsをプリント
  return 0;
}

Comments

[MIFA]

回答ありがとうございます！
確かにそのようにしたら出来ますね。
助かりました。ありがとうございます。

Answer 2

純粋にarray[j - 1] > array[j]の回数だけ数えたいなら、コンマ演算子を使ってこのように書けます。

void insert_sort(int array[], int array_size) {
    int i, j;
    int tmp;

    for (i = 1; i < array_size; i++) {
        j = i;
        while ((j >= 0) && (s[2]++, array[j - 1] > array[j])) {
            tmp = array[j]; array[j] = array[j - 1]; array[j - 1] = tmp;
            j--;
        }
    }
}

ただし、こちらのコードにはarray[-1]にアクセスするバグがあるので、想定した回数にはならないでしょう。

Comments

[MIFA]

回答ありがとうございます！
コンマ演算子という記述法があったのをすっかり忘れていました。
ありがとうございます。