Question

This program should show understanding generic merge sort methods and generic binary search methods in java. The execution should include at least 5 found items including one from the first three items in the sorted array and one from the last three items in the sorted array as well as at least two items not found Create a generic merge sort method that will sort any comparable array of elements. Create a generic binary search method that will search any comparable array of elements for a given element. The method should return the location of the target element in the array if found and -1 otherwise. Write a class to represent an item for sale in a for: Brand Name, Description, Size, price and UPC. Include all the usual methods AND the class should implement the Comparable interface where the UPC is used for the grocery store. Each item has information Write a program that reads the contents of the file, creates instances of those items of the class you created, and stores them in an array. There are 5150 items in the file. The program then sorts the array using your merge sort method. After sorting, display the first 3 items in the sorted array and the last 3 items in the sorted array The program then prompt the user for UPCs and searches for them in the array using your binary search method. When the item is found, display all the information about the item. When the item is not found, display an appropriate message Cream of Wheat;Whole Grain Cream of Wheat;18 oz;5.27;7240000025 General Mills:Corn Chex;14 oz;10.94;1600027558 PictSweet All Natural;COB CORN 16 ears:9.69:070560926157 Cass Clay:Calci-Skim Fat Free,Gallon; 1.88:7042217350

Program with generic merge sort and binary search method help. The programming language I'm using is Java.

Answer 1

// GroceryItem.java

public class GroceryItem implements Comparable<GroceryItem> {

      

       private String brand;

       private String description;

       private String size;

       private double price;

       private long upc;

      

       public GroceryItem()

       {}

      

       public GroceryItem(String brand, String description, String size, double price, long upc)

       {

             this.brand = brand;

             this.description = description;

             this.size = size;

             this.price = price;

             this.upc = upc;

       }

      

       public void setBrand(String brand)

       {

             this.brand = brand;

       }

      

       public void setDescription(String description)

       {

             this.description = description;

       }

      

       public void setSize(String size)

       {

             this.size = size;

       }

      

       public void setPrice(double price)

       {

             this.price = price;

       }

      

       public void setUPC(long upc)

       {

             this.upc= upc;

       }

      

       public String getBrand()

       {

             return brand;

       }

      

       public String getDescription()

       {

             return description;

       }

      

       public String getSize()

       {

             return size;

       }

      

       public double getPrice()

       {

             return price;

       }

      

       public long getUPC()

       {

             return upc;

       }

      

       public String toString()

       {

             return("\n UPC : "+upc+"\n Brand : "+brand+"\n Description : "+description+"\n Size : "+size+"\n Price : "+price);

       }

       @Override

       public int compareTo(GroceryItem arg0) {

             if(upc < arg0.upc)

                    return -1;

             else if(upc > arg0.upc)

                    return 1;

             return 0;

       }

      

}

//end of GroceryItem.java

// Sort.java : Contains generic merge sort and binary search method

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Arrays;

import java.util.Scanner;

public class Sort {

       /**

           * Method to sort an array of comparable objects.

           * Merge sort is used to sort the array

           */

       @SuppressWarnings("unchecked")

       public static <T extends Comparable<T>> T[] sort(T[] inputArray) {

              

             int size =1;

            

             int ia,ua,ib,ub,i,j,it;

             Comparable<T> tempArray[] = new Comparable[inputArray.length];

             // loop that continues till the entire array is sorted

             while(size<tempArray.length)

             {

                    ia =0;

                    it=0;

                   

                    while((ia+size) < inputArray.length)

                    {

                           ib = ia+size;

                           ua = ib -1;

                           if((ib + size -1)< inputArray.length)

                                 ub = ib+size-1;

                           else

                                 ub = inputArray.length-1;

                           for(i=ia,j=ib;i<=ua && j<=ub;it++)

                           {

                                 if(inputArray[i].compareTo(inputArray[j])<0) {

                                        tempArray[it] = inputArray[i];

                                        i++;

                                 }else {

                                        tempArray[it] = inputArray[j];

                                        j++;

                                 }

                           }

                           for(;i<=ua;i++)

                           {

                                 tempArray[it] = inputArray[i];

                                 it++;

                           }

                           for(;j<=ub;j++)

                           {

                                 tempArray[it] = inputArray[j];

                                 it++;

                           }

                          

                           ia = ub+1;

                    }

                    for(;it<inputArray.length;it++)

                    {

                           tempArray[it]=inputArray[ia];

                           ia++;

                    }

                   

                    for(i=0;i<inputArray.length;i++)

                    {

                           inputArray[i] = (T)tempArray[i];

                    }

                   

                    size = size*2;

             }

            

             return inputArray;

       }

      

       // method to search for a key in the array and return the index, if found, -1, if not found

       public static <T extends Comparable<T>> int binarySearch(T[] inputArray, T key)

       {

             int low=0,high = inputArray.length-1;

             int mid;

             while(low <=high)

             {

                    mid = (low+high)/2;

                    if(inputArray[mid].compareTo(key) == 0)

                           return mid;

                    else if(key.compareTo(inputArray[mid]) < 0)

                           high = mid-1;

                    else

                           low = mid+1;

             }

            

             return -1;

       }

          

       public static void main(String[] args) throws FileNotFoundException {

            

             /* Data in one line in the input file is separated by ;

*/

            

             Scanner scan = new Scanner(new File("items.txt"));

             GroceryItem items[] = new GroceryItem[0];

             long upc;

            

             String line;

             // loop to read till the end of file and insert the records in the items array

             while(scan.hasNext())

             {

                    line=scan.nextLine();

                    String line_items[] = line.split(";");

                   

                    items = Arrays.copyOf(items, items.length+1);

                    items[items.length-1] = new GroceryItem(line_items[0],line_items[1],line_items[2],Double.valueOf(line_items[3]),Long.parseLong(line_items[4]));

             }

             scan.close();

            

             sort(items); // sort the items array

             scan = new Scanner(System.in);

             // loop that inputs upc number from user and searches in the items array using binary search

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

             {

                    System.out.print(" Enter the UPC for the item to search: ");

                    upc = Long.parseLong(scan.nextLine());

                    GroceryItem search_item = new GroceryItem();

                    search_item.setUPC(upc);

                    int index = binarySearch(items,search_item);

                    if(index != -1)

                           System.out.println(" Item found at index "+index);

                    else

                           System.out.println(" Item not found in array ");

             }

            

             scan.close();

            

            

       }

}

//end of Sort.java