Нахождение числа С ключевых сравнений и числа М ходов

Question

Я сейчас читаю N.Wirth - алгоритмы и структуры данных. (Версия Oberon: август 2004 г.)

Вопрос: как он считал эти С и М? Там нет объяснения этого процесса... (любая помощь будет полезна)

Позвольте мне сказать вам, в чем дело... Я наткнулся на следующее:

2.2.1 Сортировка по прямой вставке

... Хороший показатель эффективности получается путем подсчета чисел C необходимых ключевых сравнений и M ходов (транспозиций) предметов.

Он описывает, как работает этот алгоритм:

PROCEDURE StraightInsertion; 
 VAR i, j: INTEGER; x: Item; 
BEGIN 
 FOR i := 1 TO n-1 DO 
 x := a[i]; j := i; 
 WHILE (j > 0) & (x < a[j-1] DO a[j] := a[j-1]; DEC(j) END ; 
 a[j] := x 
 END 
END StraightInsertion

... а потом он рассказывает о С и М. Но он не объясняет процесс их нахождения -> он просто показал подсчитанное Cmin, Mmax...:

Анализ прямой вставки. Число Ci ключевых сравнений в i-м сите составляет самое большее i-1, по крайней мере 1, и - при условии, что все перестановки n ключей одинаково вероятны - в среднем i/2. Число Mi ходов (назначений предметов) составляет Ci + 2 (включая дозорного). Следовательно, общее количество сравнений и ходов:

Cmin = n-1                   Mmin = 3*(n-1) 
Cave = (n^2 + n - 2)/4       Mave = (n^2 + 9n - 10)/4 
Cmax = (n^2 + n - 4)/4       Mmax = (n^2 + 3n - 4)/2 

Итак, вопрос: как он считал эти С и М? Он не объясняет процесс поиска всех этих чисел. Можете ли вы помочь мне понять, как их найти? Любая помощь будет хорошей.

PS Я искал информацию на эту тему, но безрезультатно.

---

Дополнительно:

Вот процесс вставки, показанный в примере из восьми чисел, выбранных случайным образом (при необходимости):

Initial Keys: 44 55 12 42 94 18 06 67
                 v
          i=1 44 55 12 42 94 18 06 67
                    v
              v-----<   
          i=2 12 44 55 42 94 18 06 67 
                       v
                 v-----<   
          i=3 12 42 44 55 94 18 06 67
                          v
          i=4 12 42 44 55 94 18 06 67
                             v
                 v-----------<    
          i=5 12 18 42 44 55 94 06 67
                                v
              v-----------------<    
          i=6 06 12 18 42 44 55 94 67
                                   v
                                v--<    
          i=7 06 12 18 42 44 55 67 94

Answer 1

C - количество сравнений, а M - количество перемещенных элементов данных. Если мы пойдем по вашему примеру, на итерации 1, будет 1 сравнение и нет хода. На итерации 2 есть 2 сравнения и 2 хода. И так далее. Теперь рассмотрим k-ю итерацию. Будет проведено k сравнений, и если предположить, что ваше точное место находится на полпути от 1 до k, будет k/2 хода. Число C и M являются суммой всех сравнений и движений, когда k изменяется от 1 до n. Все, что вам нужно сделать, это сложить суммы, меняющиеся k от 1 до n, и у вас есть числа.