Question

Consider the following two variants of the pseudo code for the Insertion Sort algorithm. Using each variant, sort the array: 51 52 53 54 55. Note that 51, 52, ..., 55 are five different instants of integer 5 and need to be treated as separate elements (that are of the same numerical value). Determine the number of comparisons encountered with each of the two variants of the algorithm to sort the above array and what is the final sorted array (include the suffixes of the elements throughout your work).


Pseudo Code - I Pseudo Code - II

Answer 1

Answer on Question #73553 – Programming & Computer Science | Algorithms

Comparing this 2 algorithms it is easy to notice, that they differ only in the body of ‘while’ loop.

Input: Array A[0...n-1]
Begin
for (index i = 1 to n-1) do
v = A[i]
index j = i-1
while (index j ≥ 0) do
if (v ≥ A[j]) then
break 'j' loop
else
A[j+1] = A[j]
end if
j = j-1
end while
A[j+1] = v
End
Pseudo Code - I
Input: Array A[0...n-1]
Begin
for (index i = 1 to n-1) do
v = A[i]
index j = i-1
while (index j ≥ 0) do
if (v > A[j]) then
break 'j' loop
else
A[j+1] = A[j]
end if
j = j-1
end while
A[j+1] = v
End
Pseudo Code - II

After several test I find out that in the Pseudo Code – I we have (n-1) comparisons.

In the Pseudo Code – II we encounter (n-2) comparisons.

Furthermore array :51,52,53,54,55, after sorting by both algorithms will look the same as on input:51,52,53,54,55.

Answer provided by www.AssignmentExpert.com