Здравствуйте!

Не мог бы кто-нибудь объяснить каким образом в книге "Алгоритмы и структуры данных" подсчитывается количество сравнений для алгоритмов сортировки. Никак в толк не возьму.

Скажем, сортировка с помощью прямого включения. Опираюсь на книгу 1989 года.

## Код:
```
PROCEDURE StraightInsertion; 
   VAR i, j: index; x: item; 
BEGIN 
   FOR i := 2 TO n DO 
      x := a[i]; a[0] := x; j := i; 
      WHILE x < a[j-1] DO a[j] := a[j-1]; j := j-1 END; 
      a[j] := x 
   END 
END StraightInsertion
```


Cmin = n-1
Это я понимаю почему.Цикл FOR выполнится n-1 раз и если элементы уже были упорядочены, то на каждом шаге будет выполнено только одно сравнение x < a[j-1] в цикле WHILE. Это условие будет равно FALSE сразу же. В итоге (n-1) * 1 = n - 1.

Но, скажем, каким образом Cmax = (n2 + n - 4)/4 остаётся для меня загадкой.
Понимаю, как считает тот же Левитин (Алгоритмы. Введение в разработку и анализ)

Двойная сумма сводится к одинарной. Ну а там арифметическая прогрессия...

Но как считает Вирт?