Question

// ArrayIns.java // demonstrates insertion sort 11--- class ArrayIns private long[] a; private int nElems; // ref to array a // number of data items public ArrayIns(int max) // constructor a = new long[max]; nElems - © // create the array // no items yet --- public void insert(long value) // put element into array a[nElems] = value; nElems++; // insert it // increment size public void display() // displays array contents for(int j=0; j<ntlems; 1++) 1/ for each element, System.out.print(a[] + " "); // display it System.out.println(""); public void insertionSort() int in, out; for (out=1; out<nElems; out++) // out is dividing line long temp = a[out); // remove marked item in = out; // start shifts at out while(in> 88 afin-1) >= temp) // until one is smaller, aſin) - afin-1]; // shift item to right // go left one position --in; } // end for // end insertionSort() } // -- > // end class ArrayIns

Answer 1

In the provided code there is ambiguity in the insertionSort() method. After the while iteration the value of a[in] is not updated with the temp stored in each for iteration. A detailed explanation is provided below.

After each iteration of for loop the array elements to the left of the element in consideration is sorted. In doing so the element in consideration is inserted in the right location with respect to the elements to its left, like inserting card in ordered manner. In the above code the insertion part of the element to its correct place is missing.

In the pseudocode mentioned above there is a logical error in the program. The contents inside the while loop of the code will never be executed as for each for iteration the value of A [j] is stored to key, value of j is stored to i   ( i = j ) and then A[j] is compared to key (A [i] > key). As key, A[i] & A[j] stores the same value therefor the comparison is always false. So the algorithm will not operate. In the condition statement of the while iteration A [i] should be replaced with A[ i-1 ]. so the comparison starts from the previous element.

CORRECTED insertionSort() METHOD

public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++)
{
long temp = a[out];
in = out;
while(in>0 && a[in-1] >= temp)
{
a[in] = a[in-1];
--in;
}
a[in] = temp;
}
}

COMPLETE CODE:

//ArrayIns.java

class ArrayIns{
private long[] a;
private int nElems;
public ArrayIns(int max)
{
a=new long[max];
nElems = 0;
}
public void insert(long value)
{
a[nElems] = value;
nElems++;
  
}
public void display()
{
for(int j=0; j<nElems; j++)
System.out.print(a[j]+" ");
System.out.print("\n");
}

/*********************************WRONG CODE*********************************/
// public void insertionSort()
// {
// int in, out;
// for(out=1; out<nElems; out++)
// {
// long temp = a[out];
// in = out;
// while(in>0 && a[in-1] >= temp)
// {
// a[in] = a[in-1];
// --in;
// }
// }
// }

/*********************************CORRECT CODE*********************************/
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++)
{
long temp = a[out];
in = out;
while(in>0 && a[in-1] >= temp)
{
a[in] = a[in-1];
--in;
}
a[in] = temp;
}
}
}

//InsertionSortTest.java

class InsertionSortTest
{
public static void main (String[] args) {
int maxSize = 100;
ArrayIns arr;
arr = new ArrayIns(maxSize);
  
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
  
arr.display();
arr.insertionSort();
arr.display();
}
}

Above sample run:

1 class InsertionSortTest public static void main(String[] args) { int maxSize = 100; ArrayIns arr; arr = new ArrayIns(maxSize); NNNNSBERGUEDO OWN arr.insert(132); arr.insert(-32); arr.insert(453); arr.insert(1694); arr.insert(342); arr.insert(675); arr.insert(-582); arr.insert(-892); arr.insert (643); arr.insert(37); System.out.print("Before Sort: "); arr.display(); arr.insertionSort(); System.out.print("After Sort: "); arr.display(); input re Sort: 132 -32 453 1694 342 675 -582 -892 643 37 After Sort: -892 -582 -32 37 132 342 453 643 675 1694