Question

Modify the insertionSort() method in insertSort.java so it counts the number of copies and the number of comparisons it makes during a sort and displays the totals. To count comparisons, you will need to break up the double condition in the inner while loop. Use this program to measure the number of copies and comparisons for different amounts of inversely sorted data. Do the results verify O(N² ) efficiency? Do the same for almost-sorted data (only a few items out of place). What can you deduce about the efficiency of this algorithm for almost-sorted data?

// insertSort.java

class ArrayIns
{
private long[] a; // ref to array a
private int nElems; // number of data items

public ArrayIns(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}

public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}

public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // 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>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item to right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()

} // end class ArrayIns

class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array

arr.insert(77); // insert 10 items
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(); // display items

arr.insertionSort(); // insertion-sort them

arr.display(); // display them again
} // end main()
} // end class InsertSortApp

Answer 1

class ArrayIns
{
private long[] a; // ref to array a
private int nElems; // number of data items

public ArrayIns(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}

public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}

public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}

public void insertionSort()
{
int in, out;
int no_of_comparisons=0, no_of_copies=0;

for(out=1; out<nElems; out++) // out is dividing line
{
long temp = a[out]; // remove marked item
in = out; // start shifts at out

boolean already_counted_no_of_comparisons = true; // it will keep track if no of comparisons is incremented by 1
//before the while so that it can't be counted one more time for a single comparisons

no_of_comparisons++; // incrementing number of comparisons

while(in>0 && a[in-1] >= temp ) // until one is smaller,
{
if(already_counted_no_of_comparisons == false){ //checking if already incremented by 1 outside the loop
no_of_comparisons++;
}
a[in] = a[in-1]; // shift item to right
no_of_copies++; // incrementing number of copies
--in; // go left one position
already_counted_no_of_comparisons = false;
}
a[in] = temp; // insert marked item
} // end for

System.out.println("Number of Comparisons : "+ no_of_comparisons);
System.out.println("Number of Copies : "+ no_of_copies);

} // end insertionSort()

} // end class ArrayIns

class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array

arr.insert(77); // insert 10 items
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);

//2nd Run
// arr.insert(7); // insert 10 items
// arr.insert(2);
// arr.insert(3);
// arr.insert(4);
// arr.insert(5);
// arr.insert(6);
// arr.insert(1);
// arr.insert(8);
// arr.insert(9);
// arr.insert(10);

System.out.println("Before Sorting :");
arr.display(); // display items

arr.insertionSort(); // insertion-sort them

System.out.println("After Sorting :");
arr.display(); // display them again
} // end main()
} // end class InsertSortApp

OUTPUT:

1st Run:

Here, for 10 elements 32 comparisons were done and 31 copies were performed. Complexity is O(n*n).

2nd Run:

  

Since array is almost sorted only 9 comparisons and only one copies were performed.So, complexity in best case is linear i.e. O(n).