2
$\begingroup$

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[0] = 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[0] := 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 (i-1)+2. 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!

$\endgroup$
  • $\begingroup$ What exactly is the sentinel defined as here? Also, does the author index arrays starting from 0 or starting from 1? $\endgroup$ – kotu Jun 27 at 16:40
  • $\begingroup$ Sentinel is the current element that I want to sift/insert to the sorted part of an array. In this case, the arrays index start from zero. $\endgroup$ – Bomba Jun 27 at 16:42
  • $\begingroup$ Perhaps I'm missing something, but why would you compare the item that you wish to insert to itself? $\endgroup$ – kotu Jun 27 at 16:52
  • $\begingroup$ I've edited my question - instead of me trying to rewrite it, I'll post another screenshot. Hope this might be better, sorry for any confusion. $\endgroup$ – Bomba Jun 27 at 16:59
0
$\begingroup$

Edit: My apologies, misunderstood what you meant by sentinel earlier. It seems to me that you are correct, and this is indeed a typo. When you include comparison against the sentinel at $a[0]$, you perform $i - 1 + 1 = i$ comparisons on a worst case sift.

$\endgroup$
  • 1
    $\begingroup$ Well, let's say I have an array [S,5,6,7,2,...] where S is sentinel at position 0 and I currently want to insert the item x=a[4] (in this case the sentinel will be set to S=7 since that was the last value that I inserted in). Now, i = 4, S = 2 and j = 3. I will compare 2 (my item I want to insert) with all the other values -> 7, 6, 5 (that's 3 comparisons) but for the while loop to terminate (since for all the previous values x<a[j], I have to make one more comparison with the sentinel S at position a[0]. So that's 4 comparisons. $\endgroup$ – Bomba Jun 27 at 17:15
  • $\begingroup$ Seems like you've answered your own question! $\endgroup$ – kotu Jun 27 at 17:25
  • $\begingroup$ Thank you very much. It still seems weird to me, that the author would have then the C_max correct but C_min and C_ave wrong in his text: authors' analysis $\endgroup$ – Bomba Jun 27 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.