Sort Lab 2

This program requires knowledge of various sort algorithms

The focus of this assignment is the search Algorithms. After seeing and hearing about the two basic search algorithms (linear and binary), this lab will help put these ideas to use. Here we have a starter code for each of these.


Part One: Compare Linear and 2 Kinds of Binary Search

You need this code, and the textfile names-data.txt. Make sure this data file is either part of your Eclips project (File>New>File, name it 'names-data.txt' and paste it in) or in the same folder as where your BlueJ IDE stores your LinearVsBinarySearch.class file.

LinearVsBinarySearch.java

Find your Name and see how popular it has been over the past century. Note how many steps it takes to find your name in over 4408 names who made it to the top 1000 names submitted to the Social Security Office. Find names that take more or less steps to find then yours.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;


public class LinearVsBinarySearch {

	public static long linSteps,binSteps,bin2Steps;
	public static ArrayList<String> readDataFile(String fileName){
		ArrayList<String> result=new ArrayList<String>(); 
		File dataFile = new File(fileName);
        if (dataFile.exists())
       {
           try{
           FileReader inFile = new FileReader(dataFile);
           BufferedReader inStream = new BufferedReader(inFile);
           String newLine;
          
           newLine = inStream.readLine();
           
           while (newLine!=null){
               result.add(newLine);
               newLine = inStream.readLine();
            }
           inStream.close(); 
           
           } catch (IOException e){}
       }
        return result;
	}
	private static void showNameData(String n){
		String[] d=n.split(" ");
		System.out.println("Popularity for "+d[0]+": (rank order)");
		for (int i=1; i<12;i++){
			System.out.print((1890+10*i)+": ");
			int rank=100-Integer.parseInt(d[i]);
			if (d[i].equals("0")) rank=0;
			for(int j=rank; j>0; j-=2)
				System.out.print("X");
			System.out.println(" "+d[i]);
		}
	}
	public static void main(String[] args) {
		Scanner kb=new Scanner(System.in);
		ArrayList<String> names=readDataFile("names-data.txt");
		System.out.println("Read "+names.size()+" names. Ready to Search SSN Name data");
		System.out.print("type \"quit\" to end\nSearch for: ");
		String input=kb.nextLine();
		while (!input.equals("quit")){
			// Do linear search
			long linearTime=System.currentTimeMillis();
			 linSteps=0;
			int i=linearSearch(input, names);
			linearTime=System.currentTimeMillis()-linearTime;
			// Do binary Search
			long binaryTime=System.currentTimeMillis();
			binSteps=0;
			i=binarySearch(input,names);
			binaryTime=System.currentTimeMillis()-binaryTime;
			bin2Steps=0;
			i=binarySearch2(input,names);
			
			//Report our findings
			if(i<0) {
				System.out.println("not found");
			}else {
				showNameData(names.get(i));
				
			}
			System.out.println("Linear search took "+linearTime+" ms, "+linSteps+" steps");
			System.out.println("Binary search took "+binaryTime+" ms, "+binSteps+" steps");
			System.out.println("Binary2 search took "+bin2Steps+" steps");
			System.out.println("type \"quit\" to end\nSearch for: ");
			input=kb.nextLine();
		}
		System.out.println("Ok.  Data gathered from http://www.ssa.gov/OACT/babynames/");
	}
	/**
	 * liner Search of n in the first word of the ArrayList list
	 * @param n name to search
	 * @param list the ArrayList<String> to search
	 * @return
	 */
	private static int linearSearch(String n, ArrayList<String> list){
		int result=-1;
		for(int i=0; i<list.size(); i++) {
			linSteps++;
			String entry=list.get(i);
			entry=entry.substring(0,entry.indexOf(" "));		
			if (n.equals(entry))result=i;
		}
		return result;
	}
	private static int binarySearch(String n, ArrayList<String> list){
		int low=0;
		int high=list.size();
		int mid;
		while (low<high){
			binSteps++;
			mid=(low+high)/2;
			String entry=list.get(mid);
			entry=entry.substring(0,entry.indexOf(" "));
			if (entry.compareTo(n)<0) {
				low=mid+1;
			}else{ 
				high=mid;
			}			
		}
		
		binSteps++;	
		if (low<list.size()){
			String entry=list.get(low);
			entry=entry.substring(0,entry.indexOf(" "));
			if (entry.equals(n))return low;
			
		}		
		 return -1;

	}
	private static int binarySearch2(String n, ArrayList<String> list){
		int low=0;
		int high=list.size()-1;
		int mid;
		while (low<high){
			bin2Steps++;
			mid=(low+high)/2;
			String entry=list.get(mid);
			entry=entry.substring(0,entry.indexOf(" "));
			if (entry.compareTo(n)>0) {
				high=mid-1;
			}else if (entry.compareTo(n)<0){ 
				low=mid+1;
			}else return mid; //found		
		}
		return -1; //not found
		
	}
	

}


Part 2: Car Talk Staff Applet

This applet also reads a text file, but in order for it to use the binary search, it must be sorted. Adapt what you have done in SortLab1 and the Phone Lab1 to sort the ArrayList. The data file is CarTalkStaff.tab which is an ordinary text file with the fields separated with tab characters.

Employee.java


/**
 *  class Employee is a data record for an employee.
 * 
 * @author Chris Thiel 
 * @version 15 Jan 2009
 */
public class Employee
{
	// instance variables - replace the example below with your own
	public String job;
	public String fullName;
	public String lastName;
	public String phone;
	public String SSN;
    
    // just to make up a string of d random digits:
	private String rand(int d){
	    int min=1;
	    for (int i=0; i<d-1; i++) min*=10;
	    int result = min+(int)(9.0*min*Math.random());
	    return Integer.toString(result);
	   }
	/**
	 *  The Constructors for objects of class Employee
	 *  are used to either read all the info, or
	 *  to make up phoney SSN and telephone numbers.
	 */
	public Employee(String j, String n)
	{
		job=j;
		fullName=n;
		lastName=n.substring(n.lastIndexOf(" ")+1);
		phone="("+rand(3)+") "+rand(3)+"-"+rand(4);
		SSN=rand(3)+"-"+rand(2)+"-"+rand(4);
	}
	public Employee(String[] s)
	{
		job=s[0];
		fullName=s[1];
		lastName=s[2];
		phone=s[3];
		SSN=s[4];
	}
    public String getName (){
        return fullName;
    }
    public String getLastName (){
        return lastName;
    }
    public String getPhone (){
        return phone;
    }
    public String getSSN (){
        return SSN;
    }
    public String getJob (){
        return job;
    }
	
}

StaffDirectory.java

import java.io.*;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

/**
 * Class StaffDirectory - write a description of the class here
 * 
 * @author Chris Thiel
 * @version 15 Jan 2009
 */
public class StaffDirectory extends JApplet implements ActionListener
{
    // instance variables - replace the example below with your own
    private int x;
    TextArea textArea;
     ArrayList<Employee> list;
     Button sortName;
     Button sortJob;
     Button searchName;
     Button searchJob;
     TextField searchFor;
     String message;
     /**
     * Called by the browser or applet viewer to inform this JApplet that it
     * has been loaded into the system. It is always called before the first 
     * time that the start method is called.
     */
    public void init()
    {
        // this is a workaround for a security conflict with some browsers
        // including some versions of Netscape & Internet Explorer which do 
        // not allow access to the AWT system event queue which JApplets do 
        // on startup to check access. May not be necessary with your browser. 
        JRootPane rootPane = this.getRootPane();    
        rootPane.putClientProperty("defeatSystemEventQueueCheck", Boolean.TRUE);
    
        list=new ArrayList<Employee>();
        textArea=new TextArea("Added the following:",25,70);
        textArea.setEditable(false);
        setLayout(new FlowLayout());
        sortName = new Button("Sort by Name");
        sortName.addActionListener(this);
        sortJob = new Button("Sort by Job");
         sortJob.addActionListener(this);
        add(sortName);
        add(sortJob);
        setSize(700,500);
         add(textArea);
         searchFor = new TextField(30);
         add(searchFor);
        searchName = new Button("Search Names");
         searchName.addActionListener(this);
        searchJob = new Button("Search Job");
         searchJob.addActionListener(this);
        add(searchName);
        add(searchJob);
        File dataFile = new File("CarTalkStaff.tab");
         if (dataFile.exists())
        {
            message="Car Talk Staff";
            try{
            FileReader inFile = new FileReader(dataFile);
            BufferedReader inStream = new BufferedReader(inFile);
            String newLine;
           
            newLine = inStream.readLine();
            int i=0;
            while (newLine!=null){
                i++;
                String[] s= newLine.split("\t");
                Employee e=new Employee(s);
                list.add(e);
                textArea.append("\n"+i+". "+e.getJob()+" -- "+e.getName());
                newLine = inStream.readLine();
             }
            inStream.close(); 
            textArea.select(0,0);
            } catch (IOException e){
               message="File \"CarTalkStaff.tab\" not Found";
            }
        }
                
    }

   
    /**
     * Paint method for applet.
     * 
     * @param  g   the Graphics object for this applet
     */
    public void paint(Graphics g)
    {
        // simple text displayed on applet
        g.setColor(Color.white);
        g.fillRect(0, 0, getWidth(), getHeight());
        g.setColor(Color.black);
        g.drawString(message, 20, 20);
        g.setColor(Color.blue);
        g.drawString("created by BlueJ", 500, 20);
    }
    /**
     * showRecord will return a String describing the 
     * the desired Employee from the list.
     */
    public String showRecord(int i){
        String result="Record not found";
        if (i>=0 && i<list.size() ){
            Employee e=list.get(i);
            result=e.getJob()+"\n";
            result+=e.getName()+"\n";
            result+="SSN: "+e.getSSN()+"\n";
            result+="Telephone: "+e.getPhone()+"\n";
        }
        return result;
    }
    /**
     * Here is the implementaqtion of the ActionPerformed interface
     * 
     * This interface requred us to define a specific method called
     * actionPerformed, which will handle any ActionEvent which
     * is generated when our user pressed a button.
     */
    public void actionPerformed (ActionEvent ev){
        Object source = ev.getSource();
        if (source == sortName){
            list=mergeSort(list, "lastName");
            message="Sorting by last name";
            textArea.setText("Names and Jobs");
            for (Employee e:list) textArea.append( "\n"+e.getName()+" -- "+e.getJob() );
        }
        if (source == sortJob){
            message="Sorting by job";
            list=mergeSort(list, "job");
            textArea.setText("Jobs and Names");
            for (Employee e:list) textArea.append( "\n"+e.getJob()+" -- "+e.getName());
        }
        if (source == searchName){
            String userInput = searchFor.getText();
            message="Searching Names for "+userInput;
            textArea.setText(message);
            list=mergeSort(list, "lastName");
            int record =findLastName(userInput,list);
            textArea.setText(showRecord(record));
        }
        if (source == searchJob){
            String userInput = searchFor.getText();
             message="Searching Jobs for "+userInput;
             int record =findJob(userInput,list);
            textArea.setText(showRecord(record));
        }
        repaint();
    }
    public static ArrayList<Employee> mergeSort(ArrayList<Employee> a, String field)
	{
		if (a.size()<=1) return a;
		int middle=a.size()/2;
		ArrayList<Employee> left=new ArrayList<Employee>();
		ArrayList<Employee> right=new ArrayList<Employee>();
		for (int i=0;i<middle; i++)
		{		
				left.add(a.get(i));				
		}
		for (int i=middle;i<a.size();i++)
		{
				right.add(a.get(i));			
		}
		
		left =mergeSort(left, field);
		
		right=mergeSort(right, field);
		ArrayList<Employee> result=merge(left,right, field);
		
		return result;
	}
	
	private static ArrayList<Employee> merge(ArrayList<Employee> left, ArrayList<Employee> right, String field)
	{
		ArrayList<Employee> result=new ArrayList<Employee>();
		while (left.size()>0 && right.size()>0)
		{
			String theLeft="",theRight="";
		    if (field.equals("lastName")) {
			     theLeft=(left.get(0)).getLastName();
			     theRight=(right.get(0)).getLastName();
			}
			if (field.equals("job")) {
			     theLeft=(left.get(0)).getJob();
			     theRight=(right.get(0)).getJob();
			}
		    if (theLeft.compareTo(theRight)<0){
				result.add(left.get(0));
			    left.remove(0);
			}else {
				result.add(right.get(0));
				right.remove(0);
			}
		}
		//Since left or right ran out, we attach the remainder to the result
		while (left.size()>0) 
		{
			result.add(left.get(0));
			left.remove(0);
		}
		while (right.size()>0)
		{
			result.add(right.get(0));
			right.remove(0);
		}
		return result;
	}
	public int findLastName(String last, ArrayList<Employee> list)
	{
	    int n=list.size();
	    int result=-1;
	    for(int i=0; i<n; i++){
	        String currentName= (list.get(i)).getName();
	       if (currentName.indexOf(last)>=0 ) result=i;
	    }
	    return result;   
	    
	}
	public int findJob(String job, ArrayList<Employee> list)
	{
	    int n=list.size();
	    int result=-1;
	    
	    // Insert your code here!
	    
	    return result;   
	    
	}
}

8 Points

Complete method findJob using a linear search method.

10 Points

Complete method findJob using a binary search method.

11 Points

Write the method:
private static ArrayList<Employee> quickSort(ArrayList<Employee> which uses the quickSort algorithm.