0

Problem: Find a mathematical derivation for the exact number of assignments and comparisons for the worst case insertion sort scenario.

I know the worst case scenario is the list being in reverse sorted order.

My best guess from looking through these is:

Step one being (2+(n-1)*(n-1))
Step two being (2+(n-2)*(n-2))

and finally...

(2+(n-k)^2) where k increases incrementally by 1 until k equals n-1.


Is this correct? Even if I am on the right track, all I have come up with is a summation...

insertionSort(array A)
 
{ This procedure sorts in ascending order. }
begin
    for i := 1 to length(A)-1 do
    begin
        value := A[i];
        j := i - 1;
        done := false;
        repeat
            { To sort in descending order simply reverse
              the operator i.e. A[j] < value }
            if A[j] > value then
            begin
                A[j + 1] := A[j];
                j := j - 1;
                if j < 0 then
                    done := true;
            end
            else
                done := true;
        until done;
        A[j + 1] := value;
    end;
end;

Edited by coolbeanbob: n/a

1
Contributor
1
Reply
2
Views
5 Years
Discussion Span
Last Post by coolbeanbob
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.