挿入ソートの比較回数のカウント

Question

前提・実現したいこと

挿入ソートの比較回数を求めるプログラムを作る。

発生している問題・エラーメッセージ

どのような比較回数を増やす処理を入れるかがわからない。

該当のソースコード

for(i=1; i<n; i++ ){
                j=i;
                while(j>=1 &&  a[j-1] >a[j]){
                        t = a[j];
                        a[j]=a[j-1];
                        a[j-1]=t;
                        j--;
                }
        }

Comments

[hoshi-takanori]

a[j-1] >a[j] の回数を数えればいいと思いますが、そのままだとちょっと難しいので、while の条件を分解する必要がありそうですね。

[submaru]

for文とif文でなんとかなりそうですかね？

Answer 1

while文を使わずにやったらできました。
回答ありがとうございました。

Answer 2

#include <stdio.h>

int main(void)
{
	int a[5] = { 3, 1, 5, 2, 4 }, n = 5, i, j, t;

	int k = 0;  // ★
	for (i = 1; i < n; i++) {
		j = i;
		while (j >= 1 && (++k, a[j-1] > a[j])) { // ★
			t = a[j];
			a[j] = a[j - 1];
			a[j - 1] = t;
			j--;
		}
	}
	for (i = 0; i < n; i++) printf(" %d", a[i]);
	printf(" : %d comparisons\n", k);
}

Answer 3

int greater(int x, int y, int* count) {
  ++*count;
  return x > y;
}

...
        int count = 0;
        for(i=1; i<n; i++ ){
                j=i;
                while(j>=1 &&  greater(a[j-1], a[j], &count)) {
                        t = a[j];
                        a[j]=a[j-1];
                        a[j-1]=t;
                        j--;
                }
        }

Answer 4

グローバル変数でカウント用の変数を定義しといて、比較時にそいつを＋１すればよろしい。