Question

C++

Suppose that L is a list is of length n and it is sorted using insertion sort. If L is already sorted in the reverse order, show that the number of comparisons is (1/2)(n2 – n) and the number of item assignments is (1/2)(n2 +3n) – 2.

Answer 1

ANSWER:

GIVEN THAT:

NUMBER OF COMPARISONS AND ITEM ASSIGNMENTS:

Given that:

1. The length of the list L is n and is sorted in reverse order using insertion sort. In order to sort the list which are already reverse ordered we have to move the first element to n, 2ed element to n-1 and so on.
2. To move the first element to n using insertion sort n-1 comparisons are performed. Similarly to move the next higher element to position n-1, n-2 comparisons are performed and so on.

Therefore, to sort the n elements then the number of comparisons:

(n-1) + (n-2) + (n-3) +......... + 2 + 1 = n (n-1) /2
=(1/2) (n^2-n)

3. While sorting the reverse ordered elements using insertion sort 2(n-1). (n-1) + (n-2) + (n-3) + + 1 item assignments are performed.

But (n-1) + (n-2) + .......+ 2 + 1 = (1/2) (n2-n)

Therefore the number item assignments = 2(n-1) + (1/2) (n2-n)

= (n2 + 3n — 4)/2

=(1/2) (n^+3n)-2