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

System.out.print(a[j] + " "); // display it

System.out.println("");

}

//--------------------------------------------------------------

// HERE IS THE INSERTION SORT ALGORITHM

public void insertionSort()

{

int in, out;

for(out=1; out

{

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()

public long valueAt(int index)

{

return a[index];

}

public long median()

{

//Copy temp array and copy items

ArrayIns b = new ArrayIns(nElems);

for(int i = 0; i < nElems; i++)

b.insert(a[i]);

b.insertionSort();

if(b.nElems % 2 == 0) //If there are 2 middle numbers, return the average of them

{

int temp = b.nElems / 2;

long median = (b.valueAt(temp) + b.valueAt(temp-1) ) / 2;

return median;

}

else return b.valueAt(b.nElems/2);

}

//--------------------------------------------------------------

} // 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);

long medianValue = arr.median();

System.out.println(medianValue);

arr.display(); // display items

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

arr.display(); // display them again

} // end main()

} // end class InsertSortApp