英文:

properly count the number of insertion sort comparisons

问题

int comparisons = 0;
for (int i = 1; i < input.length; i++) {
  int j = i;
  while (j > 0 && comp.compare(input[j - 1], input[j]) > 0) {
    if (comp.compare(input[j - 1], input[j]) > 0)
      comparisons++;
    E temp = input[j - 1];
    input[j - 1] = input[j];
    input[j] = temp;
    j--;
  }
  comparisons++;
}

我试图计算插入排序中的比较次数。然而，我的比较结果与预期的 JUnit 值不符。

输入：
{ 9, 5, 6, 7, 2, 8 } 预期结果：11 实际结果：13

输入：
{ "how", "about", "dey", "da", "bears" } 预期结果：7 实际结果：8

测试输入的预期值错误吗？还是我漏掉了一些边界情况？

<details>
<summary>英文:</summary>

```java
int comparisons = 0;
for (int i = 1; i &lt; input.length; i++) {
  int j = i;
  while (j &gt; 0 &amp;&amp; comp.compare(input[j - 1], input[j]) &gt; 0) {
	if (comp.compare(input[j - 1], input[j]) &gt; 0)
	  comparisons++;
	E temp = input[j - 1];
	input[j - 1] = input[j];
	input[j] = temp;
	j--;
  }
  comparisons++;
}

I am trying to count the number of comparisons in an insertion sort. However my comparisons are not correct with the expected JUnit value.

Inputting:
{ 9, 5, 6, 7, 2, 8 } expects: 11 but was 13

inputting:
{ "how", "about", "dey", "da", "bears" }; expects: 7 but was 8

Are the test inputs expected values incorrect or is there some edge case i'm missing?

答案1

得分: 0

比较会在条件为假时执行，命令:comparisons++
只有在条件为真时才会发生

英文:

The comparison is done even if the condition is false and the command :comparisons++

Happens only when it’s true