Question

Add a method called median() to the ArrayIns class in the insertSort.java
program (Listing 3.3). This method should return the median value in the
array. (Recall that in a group of numbers half are larger than the median and
half are smaller.) Do it the easy way.

LISTING 3.3 The insertSort.java Program
// insertSort.java
// demonstrates insertion sort
// to run this program: C>java InsertSortApp
//--------------------------------------------------------------
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
}
Insertion Sort 101
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
////////////////////////////////////////////////////////////////
Here’s the output from the insertSort.java program; it’s the same as that from the
other programs in this chapter:
77 99 44 55 22 88 11 0 66 33
0 11 22 33 44 55 66 77 88 99

Answer 1

// insertSort.java
// demonstrates insertion sort
// to run this program: C>java InsertSortApp
//--------------------------------------------------------------
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 long median() {
       int n=nElems;
       // checkin for odd case
       if (n % 2 != 0)
       return a[n / 2];
       //even case
       return (a[(n - 1) / 2] + a[n / 2]) / 2;
   }

   // --------------------------------------------------------------
   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
   ////////////////////////////////////////////////////////////////

public 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();
       System.out.println("Median : " + arr.median());
       // display them again
   } // end main()
} // end class InsertSortApp