Part 1 – Completing the IntList Class (2 marks) For binary search to work, the e
ID: 3637892 • Letter: P
Question
Part 1 – Completing the IntList Class (2 marks)For binary search to work, the elements in the internal array storage must always be
sorted into ascending order. The implementation of the insertElement method provided in the IntList class may not preserve that ascending order property. It simply puts the new element at the end of all the other elements. (And that keeps the elements in sorted order only if the new element is greater than or equal to all the elements already there.)
Your task is to modify the insertElement method so that the ascending order requirement is always satisfied, no matter what value is inserted.
Hint: you can implement this task by first putting the new element at the end (as already programmed), and then swapping pairs of elements from the back of the list towards the front until they are all in order again. For example, if the list is initially [3,7,13,14,17] and we want to insert 9, then the list becomes [3,7,13,14,17,9]. Now we compare the last 2 elements (at index positions 4 and 5), find they are out of order and therefore swap them. This gives the ordering [3,7,13,14,9,17]. Next we compare the 2 elements at positions 3 and 4, find they are out of order and swap them, giving [3,7,13,9,14,17]. Next, comparing the elements at positions 2 and 3 finds them out of order, so they are swapped to give [3,7,9,13,14,17]. Finally,
comparing elements at positions 1 and 2 finds them to be in order and thus we are finished re-sorting the list.
------------------------------------------------------------------------------------------------------
CODE:
IMPORTANT: ONLY MODIFY THE METHODS LISTED AS "FIX ME"
------------------------------------------------------------------------------------------------------
// IntList.java
public class IntList
{
private int[] storage;
private int count; // number of values stored into the array
//
public IntList(){
storage = new int[100];
count = 0;
}
public IntList(int size) {
if (size <= 0)
throw new IndexOutOfBoundsException("invalid capacity for an IntList");
storage = new int[size];
count = 0;
}
// Returns number of values in the IntList
public int count() {
return count;
}
// Returns the element at position pos in the IntList
public int getElement( int pos ) {
if (pos < 0 || pos >= count)
throw new IndexOutOfBoundsException("non-existent element");
return storage[pos];
}
// Inserts a new value into the IntList
// The list of values is supposed to be in ascending order ...
// however the code to put the values into order is not yet implemented
public void insertElement( int val ) {
if (count >= storage.length)
throw new IndexOutOfBoundsException("IntList has no space for a new element");
storage[count++] = val;
// We may need to swap elements until they are in sorted order again.
// FIX ME!
}
/**
* Searches the list using binary search.
*
* Returns the position in the list where the value occurs.
* The list must be in sorted order.
* If the value is not found, the result is -1
*/
public int binarySearch( int value ) {
int low = 0;
int high = count-1;
while (low <= high) {
int mid = (low+high) / 2;
if (storage[mid] == value)
return mid;
else if (value < storage[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
/**
* Searches the list using linear search.
*
* Returns the position in the list where value occurs.
* Does NOT require the list to be in sorted order.
* If the value is not found, the result is -1
*/
public int linearSearch (int value)
{
for( int i=0; i<count; i++ )
{
if (storage[i] == value)
return i;
}
return -1;
}
// Invokes binary search if binary is true, otherwise it
// invokes linear search
public int find(int value, boolean binary)
{
if (binary)
return binarySearch(value);
else
return linearSearch(value);
}
//Returns size of the storage array
public int getCapacity(){
return storage.length;
}
//Expands or contracts the storage array by allocating a new array of the
//desired size and copying the elements over. Do not allow it
// to contract the array to less than the count value.
public void setCapacity(int newCapacity){
// FIX ME
}
// Returns the numbers in the IntList as a String.
public String toString()
{
// FIX ME
return "<fix me>";
}
// a unit tester that tests the methods in this class.
public static void main(String[] args)
{
// FIX ME
// Create an IntList object and test all of its methods,
// make sure they work before moving on to Part 2.
}
}