Java Programming Project Help! (Insertion Sorting)

Assignment Details;

Add searching.java, sorting.java and Numbers.java to your project.

Work on the Numbers.java and fill the blanks with proper code. You need to add the code to invoke the searching method to search a target number. Make sure use the binary search. Print out the searching result properly.

Run the project. Provide the initial integer list as 1, 4, 3, 2, 5. Try searching number 2 first and other different numbers, in the list and not in the list. Is the result correct?

The reason is that the list must be sorted before running binary search. (Need to be sorted before running linear search?) Add code to invoke the insertion sort method before searching.

Now the searching result should be correct.

Lets search a list of a different type. Use the Contact class provided. Since it has already implemented the Comparable interface, you do not need to change it.

Create a driver class. In the main method, declare one array of Contact type with size 5. Instantiate the array with your own data.

Call the insertion sorting method in the provided Sorting class to sort the array. Use a for loop to print out the sorting result.

Then call the binary searching algorithm to search a particular Contact object. Again, try searching elements that is in the list and not in the list.

Here are all of the provided codes;

public class searching {

public static Comparable linearSearch (Comparable[] list,

Comparable target)

{

int index = 0;

boolean found = false;

while (!found && index < list.length)

{

if (list[index].equals(target))

found = true;

else

index++;

}

if (found)

return list[index];

else

return null;

}

public static Comparable binarySearch (Comparable[] list,

Comparable target)

{

int min=0, max=list.length, mid=0;

boolean found = false;

while (!found && min <= max)

{

mid = (min+max) / 2;

if (list[mid].equals(target))

found = true;

else

if (target.compareTo(list[mid]) < 0)

max = mid-1;

else

min = mid+1;

}

if (found)

return list[mid];

else

return null;

}

}

-------------------------------------------------------------------------------------------------------------

//********************************************************************

// Sorting.java Author: Lewis/Loftus

//

// Solution to Programming Project 10.5

//********************************************************************

public class sorting

{

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

// Sorts the specified array of objects using the selection

// sort algorithm.

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

public static void selectionSort (Comparable[] list)

{

int min;

Comparable temp;

for (int index = 0; index < list.length-1; index++)

{

min = index;

for (int scan = index+1; scan < list.length; scan++)

if (list[scan].compareTo(list[min]) < 0)

min = scan;

// Swap the values

temp = list[min];

list[min] = list[index];

list[index] = temp;

}

}

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

// Sorts the specified array of objects using the insertion

// sort algorithm.

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

public static void insertionSort (Comparable[] list)

{

for (int index = 1; index < list.length; index++)

{

Comparable key = list[index];

int position = index;

// Shift larger values to the right

while (position > 0 && key.compareTo(list[position-1]) < 0)

{

list[position] = list[position-1];

position--;

}

list[position] = key;

}

}

}

-------------------------------------------------------------------------------------------------------------

//**********************************************************

// Numbers.java

//

// Demonstrates selectionSort on an array of integers.

//**********************************************************

import java.util.Scanner;

public class Numbers

{

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

// Reads in an array of integers, sorts them,

// then prints them in sorted order.

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

public static void main (String[] args)

{

Integer[] intList;

int size;

int target;

Scanner scan = new Scanner(System.in);

System.out.print (" How many integers do you want to sort? ");

size = scan.nextInt();

intList = new int[size];

System.out.println (" Enter the numbers...");

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

intList[i] = scan.nextInt();

System.out.print (" Input the integer you want to search: ");

target = scan.nextInt();

//Your code here

//Invoke the binary searching algorithm to search for target

//Your code here

//Output the searching result, if found, print the integer; if not found, print out a message

}

}

-------------------------------------------------------------------------------------------------------------

//******************************************************************** // Contact.java Author: Lewis/Loftus // // Represents a phone contact. //******************************************************************** public class Contact implements Comparable { private String firstName, lastName, phone; //----------------------------------------------------------------- // Constructor: Sets up this contact with the specified data. //----------------------------------------------------------------- public Contact (String first, String last, String telephone) { firstName = first; lastName = last; phone = telephone; } //----------------------------------------------------------------- // Returns a description of this contact as a string. //----------------------------------------------------------------- public String toString () { return lastName + ", " + firstName + "\t" + phone; } //----------------------------------------------------------------- // Returns a description of this contact as a string. //----------------------------------------------------------------- public boolean equals (Object other) { return (lastName.equals(((Contact)other).getLastName()) &&firstName.equals(((Contact)other).getFirstName())); } public int compareTo (Object other) { int result; String otherFirst = ((Contact)other).getFirstName(); String otherLast = ((Contact)other).getLastName(); if (lastName.equals(otherLast)) result = firstName.compareTo(otherFirst); else result = lastName.compareTo(otherLast); return result; } //----------------------------------------------------------------- // First name accessor. //----------------------------------------------------------------- public String getFirstName () { return firstName; } //----------------------------------------------------------------- // Last name accessor. //----------------------------------------------------------------- public String getLastName () { return lastName; } }