Finding number C of key comparisons and number M of moves

Question

I'm reading N.Wirth - Algorithms and Data Structures now. (Oberon version: August 2004)

The Question: how did he count these C and M? There is no explanation of this process... (any help will be useful)

Let me tell you what is the matter... I came across the following:

2.2.1 Sorting by Straight Insertion

... A good measure of efficiency is obtained by counting the numbers C of needed key comparisons and M of moves (transpositions) of items.

He describes how does this algorithm work:

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

...and then he tells about C and M. But he doesn't explain the process of finding them --> he just shown the counted Cmin, Mmax... :

Analysis of straight insertion. The number Ci of key comparisons in the i-th sift is at most i-1, at least 1, and --- assuming that all permutations of the n keys are equally probable --- i/2 in the average. The number Mi of moves (assignments of items) is Ci + 2 (including the sentinel). Therefore, the total numbers of comparisons and moves are:

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 

So the question is: how did he count these C and M? He doesn't explain the process of finding all of these numbers. Can you help me to understand how to find them? Any help will be good.

PS I have been looking for the information on this subject, but with no result.

---

Additionally:

Here is the process of insertion shown in an example of eight numbers chosen at random (if needed):

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 is the number of comparisons and M is the number of data items moved. If we go by your example, on iteration 1, there is 1 comparison and no move. On iteration 2, there are 2 comparisons and 2 moves. And so on. Now, let us consider kth iteration. There will be k comparisons and assuming that your exact spot is halfway from 1 to k, there will be k/2 moves. The number C and M are the sum of all comparisons and movements when k changes from 1 to n. All you have to do is to add up the summations, varying k from 1 to n and you have the numbers.