I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot of the relevant paragraph is here: screenshot
Edit: sentinel item
a = x, the current item that I want to insert at the appropriate place.
Sorry, another screenshot of relevant paragraph is here: screenshot2
type index = 0..n var a: array[0..n] of item procedure straightinsertion var i,j: index; x: item; begin for i := 2 to n do begin x := a[i]; a := x; j := i-1; while x.key < a[j].key do begin a[j+1] := a[j]; j := j-1; end; a[j+1] := x end end
I think, that the analysis of the number of comparisons might be wrong. He claims, that the number
C_i of key comparisons in the
i-th sift is at most
i-1. But shouldn't it be
i? Because at the worst case, since we are using sentinel, we have to make an extra comparison with the sentinel too. I claim, that:
C_min = n-1
C_ave = 1/4 * (n^2 + 3n - 4)
C_max = 1/2 * (n^2 + n) -1
The number of moves
M_i should then be
M_min, M_ave, M_max are, I believe, correct in the text (screenshot).
Could you please confirm if I'm right or is there something I'm missing?Thank you all very much!