P5 Files

P5A.java

import java.io.*;
import java.util.*;

public class P5A 
{
	public static void main(String args[]) 
	{
		TokenReader in = new TokenReader(System.in);
		
		int comps; // For counting comparisons.
		
		// For checking the integer version of bubbleSort.
		int n = 20;               
		int[] a = randomInt(20);
		System.out.println("Sorting integer array:");
		print(a);
		comps = bubbleSort(a);
		System.out.println("Result:");
		print(a);                          // Comment this line out for large n trials
		System.out.println("Number of comparisons = " + comps);
		System.out.println();
		
		
		// For checking the string version of bubbleSort.
		// Comment this fragment out until you have written that version.
			
		String[] s = {"the","quick","brown","fox","jumped","over","the","lazy","dog"};
		System.out.println("Sorting string array:");
		print(s);
		comps = bubbleSort(s);
		System.out.println("Result:");
		print(s);
		System.out.println("Number of comparisons = " + comps);
		
		in.waitUntilEnter();
	}
	
	/*
	        
	Place your integer vesion of bubbleSort here:
	
		
	
	Place the string version of bubbleSort here:
	
	
		
    */
    
	// Yields a reference to a random array of integers selected
	// from 0..999
	public static int[] randomInt(int length) 
	{
		int[] s = new int[length];
		for (int i = 0; i < length; i++) 
		{
			s[i] = (int) Math.floor(1000*Math.random());
		}
		return s;
	}
	
	// Print an integer array.
	public static void print(int[] a) 
	{
		int i;
		if (a.length == 0) return;
		System.out.print(a[0]);
		for (i = 1; i < a.length; i++) 
		{
			System.out.print(" " + a[i]);
		}
		System.out.println();
	}
	
	// Print a string array.
	public static void print(String[] a) 
	{
		int i;
		if (a.length == 0) return;
		System.out.print(a[0]);
		for (i = 1; i < a.length; i++) 
		{
			System.out.print(" " + a[i]);
		}
		System.out.println();
	}
}

P5B.java

import java.io.*;
import java.awt.*;

public class P5B {

	public static void main(String args[]) {
	  
		int[] sizes = { 200, 500,1000,1500,2000,2500,3333,5000,6400,8000, 9999};
		int[] y     = {1200,1500,2000,2500,3000,3500,4333,6000,7400,9000,10999};
		int[] z     = {5000,   0,6000,1000,7000,2000,8000,3000,9000,4000, 9999};
	    new Plot("Test",sizes,y,z);
	}
	
	// Copy from P5A.java your integer bubbleSort method. Put it here:
	
	
	
	
	public static int[] temp; //temporary storage for mergesort
		
    // Permutes the values in the array so that they are arranged from smallest to largest.
    // Returns the number of required comparisons.
	public static int mergeSort(int[] data) 
	{
		//allocate temporary storage array
		temp = new int[data.length];
		//call recursive mergeSort procedure on whole array
		return mergeSort(data,0,data.length);
	}
	
	// Permutes the values in elements p through q-1 of the array so that they are arranged 
	// from smallest to largest. Returns the number of required comparisons.
	public static int mergeSort(int[] data, int p, int q) 
	{
		int comps = 0;	
		
		//if length is 0 or 1, nothing to do
		if (q - p < 2) return 0;
		
		//otherwise split into two subarrays of roughly equal length
		//and sort them recursively
		int mid = (p + q)/2;
		comps = comps + mergeSort(data,p,mid);
		comps = comps + mergeSort(data,mid,q);
		
		//merge the two sorted subarrays
		int i = p;		//index into first subarray
		int j = mid;	//index into last subarray
		int k = p;		//index into temp array
		while ((i < mid) && (j < q)) {
			if (data[i] <= data[j])	temp[k++] = data[i++];
			else				    temp[k++] = data[j++];
			comps++; //tally this comparison
		}
		while (i < mid)	temp[k++] = data[i++];
		while (j < q)	temp[k++] = data[j++];
		
		//copy sorted subarray back to original array
		for (i = p; i < q; i++) 
		{
		   data[i] = temp[i];
		}
		return comps;
	}
	
	// Yields a reference to a second copy of the array.
	public static int[] copy(int[] a) 
	{
		int[] c = new int[a.length];
		int i;
		for (i = 0; i < a.length; i++) 
		{
		   c[i] = a[i];
		}
		return c;
	}
	
}

P5C.java

import java.io.*;
import java.awt.*;

public class P5C {

	public static void main(String args[]) {
	
		int comps; //for counting comparisons

		//initialize a token reader to read from standard input
		TokenReader in = new TokenReader(System.in);
		
		// Create an array of strings to sort.
		String[] s1 = {"the","quick","brown","fox","jumped","over","the","lazy","dog"};
		// Convert it a sortable object referenced by ls1.
		Sortable ls1 = new Sortable(LexStr.convert(s1));
		ls1.print();
		// Sort the object referenced by ls1 and count comparisons.
		comps = ls1.mergeSort();
		// Print results.
		System.out.println("Merge Sort Result:");
		ls1.print();
		System.out.println("Number of comparisons = " + comps);
		
		System.out.println(" ");
		
		// Create an array of integers to sort.
		int[] a = P5A.randomInt(20);
		// Convert it a sortable object referenced by ls2.
		Sortable ls2 = new Sortable(Int.convert(a));
		ls2.print();
		// Sort the object referenced by ls2 and count comparisons.
		comps = ls2.mergeSort();
		// Print results.
		System.out.println("Merge Sort Result:");
		ls2.print();
		System.out.println("Number of comparisons = " + comps);
		
		System.out.println(" ");
		
		// Create an array of strings to sort.
		String[] s3 = {"the","quick","brown","fox","jumped","over","the","lazy","dog"};
		// Convert it a sortable object referenced by ls1.
		Sortable ls3 = new Sortable(LexStr.convert(s1));
		ls3.print();
		// Sort the object referenced by ls3 and count comparisons.
		comps = ls3.bubbleSort();
		// Print results.
		System.out.println("Bubble Sort Result:");
		ls3.print();
		System.out.println("Number of comparisons = " + comps);
		
		System.out.println(" ");
		
		// Create an array of integers to sort.
		a = P5A.randomInt(20);
		// Convert it a sortable object referenced by ls4.
		Sortable ls4 = new Sortable(Int.convert(a));
		System.out.println("Sorting integer array:");
		ls4.print();
		// Sort the object referenced by ls4 and count comparisons.
		comps = ls4.bubbleSort();
		// Print results.
		System.out.println("Bubble Sort Result:");
		ls4.print();
		System.out.println("Number of comparisons = " + comps);
		
		
		in.waitUntilEnter();
	}	
}

P5D.java

import java.io.*;
import java.awt.*;

public class P5D {

	public static void main(String args[]) {
	
		int comps; //for counting comparisons

		//initialize a token reader to read from standard input
		TokenReader in = new TokenReader(System.in);
		
		// Create an array of strings to sort.
		String[] s1 = {"the","quick","brown","fox","jumped","over","the","lazy","dog"};
		// Convert it a sortable object referenced by ls1.
		Sortable ls1 = new Sortable(LexStr.convert(s1));
		ls1.print();
		// Sort the object referenced by ls1 and count comparisons.
		comps = ls1.bubbleSort();
		// Print results.
		System.out.println("\nBubble Sort Result (Lexicographic Order:)\n");
		ls1.print();
		System.out.println("\nNumber of comparisons = " + comps);
		
		System.out.println("\n\n\n ");
		
		// Create an array of strings to sort.
		String[] s2 = {"the","quick","brown","fox","jumped","over","the","lazy","dog"};
		// Convert it a sortable object referenced by ls2.
		Sortable ls2 = new Sortable(ModLexStr.convert(s2));
		ls2.print();
		// Sort the object referenced by ls2 and count comparisons.
		comps = ls2.bubbleSort();
		// Print results.
		System.out.println("\nBubble Sort Result(Modified Lexicographic Order):\n");
		ls2.print();
		System.out.println("\nNumber of comparisons = " + comps);
		
	
		in.waitUntilEnter();
	}	
}

Sortable.java

/*
class Sortable

This class encapsulates an array of objects that can be sorted.
The objects to be sorted must implement the Comparable interface
so they can be compared in a uniform way.
*/
			

public class Sortable {
	Comparable[] data;		//the array of objects to be sorted
	int comps = 0;			//number of comparisons needed to sort this array
	
	//create a new instance of Sortable with the given data array
	Sortable(Comparable[] array) {
		data = array;
	}
	
	// Place your Part C BubbleSort implementation here:
	
	          
	
	
	Comparable temp[];	// Temporary storage for mergeSort
	
	// Permutes the values in the array so that they are arranged from smallest to largest.
    // Returns the number of required comparisons.
	public int mergeSort() 
	{
		//allocate temporary storage array
		temp = new Comparable[data.length];
		//call recursive mergeSort procedure on whole array
		return mergeSort(0,data.length);
	}
	
	
	// Permutes the values in elements p through q-1 of the array so that they are arranged 
	// from smallest to largest. Returns the number of required comparisons.
	public int mergeSort(int p, int q) 
	{	
		int comps = 0;	
		
		// If length is 0 or 1, nothing to do
		if (q - p < 2) return 0;
		
		//otherwise split into two subarrays of roughly equal length
		//and sort them recursively
		int mid = (p + q)/2;
		comps = comps + mergeSort(p,mid);
		comps = comps + mergeSort(mid,q);
		
		// Merge the two sorted subarrays
		int i = p;		//index into first subarray
		int j = mid;	//index into last subarray
		int k = p;		//index into temp array
		while (i < mid && j < q) {
			if (data[i].leq(data[j]))	temp[k++] = data[i++];
			else						temp[k++] = data[j++];
			comps++; //tally this comparison
		}
		while (i < mid)	temp[k++] = data[i++];
		while (j <  q)	temp[k++] = data[j++];
		
		// Copy sorted subarray back to original array
		for (i = p; i < q; i++) data[i] = temp[i];
		return comps;
	}

	// Yields a reference to a second copy of the array.
	Sortable copy() 
	{
		int i;
		Comparable[] newData = new Comparable[data.length];
		for (i = 0; i < data.length; i++) {
			newData[i] = data[i];
		}
		return new Sortable(newData);
	}
	
	// Print the array.
	void print() 
	{
		int i;
		if (data.length > 0) System.out.print(data[0].toString());
		for (i = 1; i < data.length; i++) {
			System.out.print(" " + data[i].toString());
		}
		System.out.println();
	}	
}

Comparable.java

/*
Comparable

This interface specifies a collection of procedures that
must be implemented by a class in order for the sorting routines
to be able to sort objects in the class.

To implement this interface, a class must provide two procedures:

(1) leq, which defines what it means for one object in the class
    to be "less than or equal to" another object in the class.

(2) toString, which tells how objects should be printed.

The purpose of this is to provide a uniform interface so that
the sorting routines can sort different types of objects
in the same way.

To use the sorting routines on any type of object that can be
compared, wrap it in a class that implements the Comparable
interface.  We show how to do this below for integers and strings.
*/

import java.util.*;

interface Comparable {
	boolean leq(Comparable q);
	String toString();
}


// For comparing strings lexicographically
public class LexStr implements Comparable {
	String value; // The String value of this LexStr object
	
	// The constructor.
	LexStr(String v) 
	{
		value = v;
	}
	
	//  Yields true if this string "equals or comes before" q.
	public boolean leq(Comparable q) 
	{
		String qvalue = ((LexStr)q).value;
		//compare the strings value and qvalue lexicographically
		//compareTo is defined in the String class
		return value.compareTo(qvalue) <= 0;
	}	

    // Yields the value of this object as a string.
	public String toString() {
		return value;
	}
	
	// Convert a String array to a LexStr array.	
	public static LexStr[] convert(String[] s) 
	{
		int i;
		LexStr[] ls = new LexStr[s.length];
		for (i = 0; i < s.length; i++) 
		   ls[i] = new LexStr(s[i]);
		return ls;
	}
}

// For comparing integers
public class Int implements Comparable {
	int value; //the integer value of this Int object
	
	// The Constructor.
	Int(int v) {
		value = v;
	}
	
	//  Yields true if this integer is less than or equal to q.
	public boolean leq(Comparable q) 
	{
	   return value <= ((Int)q).value;	
	}	

    // Yields the value of this object as a string.
	public String toString() 
	{
		return String.valueOf(value);
	}
	
	
	// Convert an integer array to an Int array	
	public static Int[] convert(int[] s) 
	{
		int i;
		Int[] ls = new Int[s.length];
		for (i = 0; i < s.length; i++) 
		   ls[i] = new Int(s[i]);
		return ls;
	}
}

// Place your ModLexStr class here:

Plot.java

/*
Plot

Draw up to three line graphs specified by integer arrays.
Call the constructor with a string message and two, three or four integer arrays,
all of the same length.  The first contains the x values.
The second, third and fourth specify the y values of one,
two, or three line graphs.  The graphs are plotted in different
colors. The window is titled with the message.
*/

import java.io.*;
import java.awt.*;
import java.awt.event.*;

public class Plot extends Frame {
	int[] sizes;
	int[][] values;
	int maxValue = 0;
	int maxSize = 0;
	final int windowWidth = 800;
	final int windowHeight = 600;
	final int margin = 100;
	final int plotWidth = windowWidth - 2*margin;
	final int plotHeight = windowHeight - 2*margin;

	
	Plot(String message, int[] s, int[] v0, int[] v1, int[] v2) {
		sizes = s;
		values = new int[3][s.length];
		values[0] = v0;
		values[1] = v1;
		values[2] = v2;
		init(message);
	}
	
	Plot(String message,int[] s, int[] v0, int[] v1) {
		sizes = s;
		values = new int[2][s.length];
		values[0] = v0;
		values[1] = v1;
		init(message);
	}
	
	Plot(String message,int[] s, int[] v0) {
		sizes = s;
		values = new int[1][s.length];
		values[0] = v0;
		init(message);
	}
	
	void init(String message) {
		int i,j;
		//do some error checking, calculate max value and size
		if (sizes.length == 0) {
			throw new Error("No points to plot");
		}
		for (i = 0; i < sizes.length; i++) {
			if (sizes[i] < 0) {
				throw new Error("Can't plot negative size " + sizes[i]);
			}
			if (sizes[i] > maxSize) maxSize = sizes[i];
		}
		for (i = 0; i < values.length; i++) {
			if (values[i].length != sizes.length) {
				throw new Error("Can't plot arrays of different lengths");
			}
			for (j = 0; j < values[i].length; j++) {
				if (values[i][j] > maxValue) {
					maxValue = values[i][j];
				}
				if (values[i][j] < 0) {
					throw new Error("Can't plot negative value " + values[i][j]);
				}
			}
		}
		addWindowListener(new MyWindowListener());
		setTitle(message);
		resize(windowWidth,windowHeight);
		move(0,75);
		show();
		toFront();
	}
	
	//convert point to pixel value and plot it
	Point plotPoint(Graphics g, int s, int t) {
		int x = (int)(((double)s)*plotWidth/maxSize);
		int y = (int)(((double)plotHeight) - ((double)t)*plotHeight/maxValue);
		g.fillOval(x-3,y-3,6,6);
		return new Point(x,y);
	}

	public void paint(Graphics g) {
		int i,j;
		Point p,q;
		Color[] colors = {Color.red, Color.blue, Color.green};
		//set origin at top left corner of plot area
		g.translate(margin,margin);
		//plot coordinate axes
		g.setColor(Color.black);
		g.drawRect(0,0,plotWidth,plotHeight);
		for (i = 0; i < values.length; i++) {
			g.setColor(colors[i]);
			p = plotPoint(g,sizes[0],values[i][0]);
			for (j = 1; j < sizes.length; j++) {
				q = p;
				p = plotPoint(g,sizes[j],values[i][j]);
				g.drawLine(q.x,q.y,p.x,p.y);
			}
			g.drawString("array " + i,20,20*i+20);
		}
		g.setFont(new Font("Helvetica",Font.PLAIN,14));
		g.drawString("0",plotWidth+5,plotHeight+5);
		g.drawString(" "+ maxValue,plotWidth+5,5);
		g.drawString("0",-5,plotHeight+20);
		g.drawString(" " + sizes[sizes.length-1],plotWidth-40,plotHeight+20);
	    
	}	
}

class MyWindowListener implements WindowListener {
	public void windowClosing(WindowEvent e) {
		System.exit(0);
	}
	public void windowOpened(WindowEvent e) {
	}
	public void windowIconified(WindowEvent e) {
	}
	public void windowDeiconified(WindowEvent e) {
	}
	public void windowClosed(WindowEvent e) {
	}
	public void windowActivated(WindowEvent e) {
	}
	public void windowDeactivated(WindowEvent e) {
	}	
}