Homework SourseIn lecture we discussed the binary search algorithm which se
In lecture we discussed the binary search algorithm which searches a sorted array for a key and returns either the index of where it was found, or if not found, returns the index of where it belongs. In such a case this belongs index is encoded as a negative number to distinguish it from being confused with a found index. The encoding is as follows: add 1 to index then negate. In lecture we also discussed the insertInOrder algorithm which reads a sequence of values from a source ( text file) and inserts them into an array keeping them sorted as each value is added to the array. For this project you will combine both algorithms to write an insertInOrder implementation that uses the binary search algorithm to find the correct index where the new incoming value belongs. A binary search will figure out where the new key belongs in O(Log2N) where as a linear scan will take O(N). Using a binary search instead of a simple linear scan to figure out where the new key goes is an optimization of the insertInOrder algorithm. When the insertInOrder gets the index back from the binary search, it must examine that value to see if it is negative. If so, it must be decoded back to a real index. The decoding is actually the same operation: add one then negate it (back to positive).
Your program once submitted will be initially script graded for correct output ASAP and then gradually back read by the me and the UTAa who lead your recitation/lab. We will be looking to verify that you wrote a genuine insert in order algorithm as prescribed. You are not allowed to call any built in sort such as an Arrays.sort(). You are writing your own sort and it must keep the array sorted with each insertion. The array is never allowed to be out of order at any time. As for the binary search you must write your own. You are not allowed to call Arrays.binarySearch(). If you have any doubts about what you are writing being in compliance, you should ask your instructor ASAP as you are writing it.
/* Project4.java InsertInOrder with bSearch optimization to compute insertion index */
import java.util.*;
import java.io.*;
public class Project4
{
static final int INITIAL_CAPACITY = 5;
public static void main( String args[] ) throws Exception
{
// ALWAYS TEST FIRST TO VERIFY USER PUT REQUIRED INPUT FILE NAME ON THE COMMAND LINE
if (args.length < 1 )
{
System.out.println(\"\ usage: C:\\\\> java Project4 <input filename>\ \ \"); // i.e. C:\\> java Project4 P4input.txt
System.exit(0);
}
// LOAD FILE INTO ARR USING INSERINORDER
Scanner infile = new Scanner( new File( args[0] ) );
int[] arr = new int[INITIAL_CAPACITY];
int count= 0;
while (infile.hasNextInt())
{
if ( count==arr.length )
arr = upSizeArr(arr);
insertInOrder( arr, count++, infile.nextInt() );
}
infile.close();
arr=trimArr(arr,count); // Now count == .length
System.out.println( \"Sorted array of \" + arr.length + \" ints from \" + args[0] + \" after insertInOrder:\" );
printArray( arr ); // we trimmed it thus count == length so we don\'t bother to pass in count
} // END MAIN
// ############################################################################################################
// USE AS IS - DO NOT MODIFY
static void printArray( int[] arr )
{
for( int i=0 ; i<arr.length ;++i )
System.out.print(arr[i] + \" \" );
System.out.println();
}
// USE AS IS - DO NOT MODIFY
static int[] upSizeArr( int[] fullArr )
{
int[] upSizedArr = new int[ fullArr.length * 2 ];
for ( int i=0; i<fullArr.length ; ++i )
upSizedArr[i] = fullArr[i];
return upSizedArr;
}
// USE AS IS - DO NOT MODIFY
static int[] trimArr( int[] oldArr, int count )
{
int[] trimmedArr = new int[ count ];
for ( int i=0; i<count ; ++i )
trimmedArr[i] = oldArr[i];
return trimmedArr;
}
// ############################################################################################################
static void insertInOrder( int[] arr, int count, int key )
{
int index=bSearch( arr, count, key ); // LEAVE THIS HERE
// Y O U R C O D E I N H E R E
// TEST index TO SEE IF NEEDS \"DECODED\" BACK TO A REAL INDEX
// OPEN UP A HOLE IN THE ARRAY AT [INDEX]
// BY SLIDING ALL ELEMS AT [INDEX] AND ABOVE, UP ONE SLOT
// COPY THE NEW VALUE (KEY) INTO THE [INDEX] SLOT YOU JUST OPENED UP
arr[index]=key; // LEAVE THIS HERE
}
// IF KEY EXISTS IN THE ARRAY RETURN indexWhereFound
// ELSE FIGURE OUT THE indexWhereItBelongs
// AND return -(indexWhereItBelongs+1);
//
static int bSearch(int[] a, int count, int key)
{
/* Y O U R C O D E H E R E */
return count; // JUST TO MAKE IT COMPILE
}
} // END PROJECT4
Solution
Program:
package org.chegg;
/* Project4.java InsertInOrder with bSearch optimization to compute insertion index */
import java.util.*;
import java.io.*;
public class Project4
{
static final int INITIAL_CAPACITY = 5;
public static void main( String args[] ) throws Exception
{
// ALWAYS TEST FIRST TO VERIFY USER PUT REQUIRED INPUT FILE NAME ON THE COMMAND LINE
if (args.length < 1 )
{
System.out.println(\"\ usage: C:\\\\> java Project4 <input filename>\ \ \"); // i.e. C:\\> java Project4 P4input.txt
System.exit(0);
}
// LOAD FILE INTO ARR USING INSERINORDER
Scanner infile = new Scanner( new File( args[0] ) );
int[] arr = new int[INITIAL_CAPACITY];
int count= 0;
while (infile.hasNextInt())
{
if ( count==arr.length )
arr = upSizeArr(arr);
insertInOrder( arr, count++, infile.nextInt() );
}
infile.close();
arr=trimArr(arr,count); // Now count == .length
System.out.println( \"Sorted array of \" + arr.length + \" ints from \" + args[0] + \" after insertInOrder:\" );
printArray( arr ); // we trimmed it thus count == length so we don\'t bother to pass in count
} // END MAIN
// ############################################################################################################
// USE AS IS - DO NOT MODIFY
static void printArray( int[] arr )
{
for( int i=0 ; i<arr.length ;++i )
System.out.print(arr[i] + \" \" );
System.out.println();
}
// USE AS IS - DO NOT MODIFY
static int[] upSizeArr( int[] fullArr )
{
int[] upSizedArr = new int[ fullArr.length * 2 ];
for ( int i=0; i<fullArr.length ; ++i )
upSizedArr[i] = fullArr[i];
return upSizedArr;
}
// USE AS IS - DO NOT MODIFY
static int[] trimArr( int[] oldArr, int count )
{
int[] trimmedArr = new int[ count ];
for ( int i=0; i<count ; ++i )
trimmedArr[i] = oldArr[i];
return trimmedArr;
}
// ############################################################################################################
static void insertInOrder( int[] arr, int count, int key )
{
int index=bSearch( arr, count, key );
// LEAVE THIS HERE
// Y O U R C O D E I N H E R E
if(index < 0){
index = index + 1;
}
for(int i = arr.length;i>0;i--){
arr[i] = arr[i-1];
}
arr[index]=key; // LEAVE THIS HERE
}
static int bSearch(int[] a, int count, int key)
{
// Y O U R C O D E I N H E R E
int low =0,high = a.length-1,mid = 0;
while(low <= high){
mid = (low + high)/2;
if(a[mid] == key){
count = mid;
return count;
}
else if(a[mid] < key){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return -(mid+1);
}
} // END PROJECT4
