Rewrite the Insertion Sort algorithm Algorithm 71 as follows

Rewrite the Insertion Sort algorithm (Algorithm 7.1) as follows. Include an extra array slot S[0] that has a value smaller than any key. This eliminates the need to compare j with 0 at the top of the while loop. Determine the exact time complexity of this version of the algorithm. Is better or worse than the time complexity of Algorithm 7.1? Which version should be more efficient? Justify your answer.

•Algorithm 7.1 Insertion Sort

•Problem: Sort n keys in nondecreasing order.

•Inputs: positive integer n; array of keys S indexed from l to n.

•Outputs: the array S containing the keys in nondecreasing order.

•       void insertionsort( int n, keytype S[ ])

•       {

•           int i, j;

•           keytype x;

•            for( i= 2; i<=n; i++) {

•                 x = S[i];

•                 j= i – l;

•                while( j>0 && S[j] > x) {

•                        S[j + l] = S[j];

•                        j--;

•                  }

•                   S[j + l]= x;

•              }

•       }

Solution

Note to student: It is well known that indexing in computers starts at 0 (not 1, like in the above question). Please confirm with your teacher or the original homework to see if the value of i=1 (as it should be)

First, let us look at why the above algorithm (7.1) can be time inefficient. Take an array S which is already sorted by in descending order, like say, S=[1000,900,800,700,-100]

Applying the above insertion sort algorithm on S, (we go over an example array S by hand, I recommend the student to do the same to get a better understanding of how 7.1 works, especially in the worst case, when S is already sorted descendingly)

i=2, s[2]=x=900

j=1, S[j]=1000,1000>900,

So S[j+1]=S[2]=1000

Decrease j: j=0 (invalid!)

Set S[j]=S[1]=x=900

S=[900,1000,800,700,-100]

Now i=3,x=800

j=2,S[j]=S[2]=1000

1000>800, So S[3]=1000

j=1 (still j>0); S[j]=S[1]=900

S=[900,1000,1000,700,-100]

See that 900>x, ie.., 900>800

S[2]=S[1]

S[2]=900

S=[900,900,1000,700,-100]

Decrease j: j=0 (invalid!)

S[1]=x=800

So S:[800,900,1000,700,-100]

Now i=4, S[i]=700=x

j=3, S[3]=1000, 1000>700

S=[800,900,1000,1000,-100]

j=2, S[2]=900, 900>700

S=[800,900,900,1000,-100]

j=1,S[1]=800, 800>700

S=[800,800,900,1000,-100]

j=0 (invalid!)

S[1]=x=700

S=[700,800,900,1000,-100]

Now i=5, S[i]=-100

j=4, S[j]=1000, 1000>-100

S=[700,800,900,1000,1000]

j=3, S[3]=900, 900>-100

S=[700,800,900,900,1000]

j=2, S[2]=800, 800>-100

S=[700,800,800,900,1000]

j=1,S[1]=700,700>-100

S=[700,700,800,900,1000]

j=0(invalid!)

S[1]=x=-100

S=[-100,700,800,900,1000]

As you can see, in the worst case, for every \'i\', \'j\' keeps going back until it hits 1. This means that the system repeats comparison operation over the same regions of the array A (from j to 1) for every element. For every element, it does j comparisons. Now j can be between 1 and n-1. We do (n-1) operations for every element. We have n elements and so, we do n(n-1) total operations= n² operations.

Now, as per the question, let us put a sentinel value in S[0]. A sentinel here is the smallest negative number.

Having a sentinel value for the smallest negative number (-2³² or -2^64, depending on whether the system is 32-bit or 64-bit).

Like:

S=-2⁶⁴, 1000,900,800,700,-100

Since we have already taken the smallest numbers of all numbers available to us in S[0], any other element in S is going to be larger than S[0]. This eliminates the need for j to go until the very last index (here 0).

So, in our algorithm:

•       void insertionsort( int n, keytype S[ ])

•       {

•           int i, j;

•           keytype x;

•            for( i= 2; i<=n; i++) {

•                 x = S[i];

•                 j= i;

•                while( S[j-1] > x) {

•                        S[j] = S[j-1];

•                        j--;

•                  }

•                   S[j]= x;

•              }

•       }

There is not much difference in time complexity with this improvement. In fact, now we have more elements (n+1) and fewer comparisons (we are not comparing S[0] with any element), that is, (n-1). Still, however, in the worst case, the complexity is still quaratic Big-BO(n²)

In the best case (where S is already sorted ascendingly), the complexity is only Big-O(n). Try to verify this.