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;