CS 100: Programming Assignment P5
Solution
Part A.
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:
// Permutes the values in data so that they are arranged from smallest to largest.
// Returns the number of required comparisons.
public static int bubbleSort(int[] data)
{
int pass=1;
int comps=0;
int temp;
int swaps;
boolean Sorted = false;
while (!Sorted)
{
swaps=0;
for (int j = 0; j < data.length - pass; j++) {
if ((data[j+1] < data[j]))
{
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
swaps++;
}
comps++;
}
pass++;
Sorted = (pass == data.length) || swaps==0;
}
return comps;
}
// Place the string version of bubbleSort here:
// Permutes the values in data so that they are arranged from smallest to largest.
// Returns the number of required comparisons.
public static int bubbleSort(String[] data)
{
int pass=1;
int comps=0;
String temp;
int swaps;
boolean Sorted = false;
while (!Sorted)
{
swaps=0;
for (int j = 0; j < data.length - pass; j++) {
if (data[j+1].compareTo(data[j])< 0)
{
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
swaps++;
}
comps++;
}
pass++;
Sorted = (pass == data.length) || swaps==0;
}
return comps;
}
// 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();
}
}
/* Output
Sorting integer array:
668 942 624 799 710 381 486 546 680 422 555 987 754 75 843 163 499 425 719 297
Result:
75 163 297 381 422 425 486 499 546 555 624 668 680 710 719 754 799 843 942 987
Number of comparisons = 189
Sorting string array:
the quick brown fox jumped over the lazy dog
Result:
brown dog fox jumped lazy over quick the the
Number of comparisons = 36
*/
Part B.
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[] array, copyOfArray;
int[] bubbleSortComps = new int[sizes.length]; // Comparisons in BubbleSort
int[] mergeSortComps = new int[sizes.length]; // Comparisons in MergeSort
int[] q1 = new int[sizes.length]; // "Predict" BubbleSort compares with n*n
int[] q2 = new int[sizes.length]; // "Predict" MergeSort compares with n log n.
System.out.println(" n Bubble Sort Merge Sort");
System.out.println(" Comparisons Comparisons");
System.out.println("-------------------------------------------");
for (int i = 0; i < sizes.length; i++)
{
q1[i] = (sizes[i]*sizes[i]);
q2[i] = (sizes[i]*(int)Math.log(sizes[i]));
// Generate a random array and sort it with each method.
array = P5A.randomInt(sizes[i]);
copyOfArray = copy(array);
bubbleSortComps[i] = bubbleSort(array);
mergeSortComps[i] = mergeSort(copyOfArray);
// Display comparison counts in a table.
Format.print(System.out,"%8d",sizes[i]);
Format.print(System.out," %10d",bubbleSortComps[i]);
Format.println(System.out," %10d",mergeSortComps[i]);
}
// Display comparison counts in a plot along with the n*n and n logn predictions
new Plot("BubbleSort Results",sizes,q1,bubbleSortComps);
new Plot("MergeSort Results",sizes,q2,mergeSortComps);
}
// Permutes the values in data so that they are arranged from smallest to largest.
// Returns the number of required comparisons.
public static int bubbleSort(int[] data) {
int pass=1;
int comps=0;
int temp;
int swaps;
boolean Sorted = false;
while (!Sorted)
{
swaps=0;
for (int j = 0; j < data.length - pass; j++) {
if ((data[j+1] < data[j]))
{
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
swaps++;
}
comps++;
}
pass++;
Sorted = (pass == data.length) || swaps==0;
}
return comps;
}
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;
}
}
/* Output
n Bubble Sort Merge Sort
Comparisons Comparisons
-------------------------------------------
200 19899 1281
500 124254 3838
1000 497960 8684
1500 1122765 13957
2000 1998334 19396
2500 3121335 25062
3333 5549292 34874
5000 12485872 55166
6400 20461400 72879
8000 31984065 93686
9999 49981173 120392
*/
Part C
/*
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;
}
// Permutes the values in a so that they are arranged from smallest to largest.
// Returns the number of required comparisons.
public int bubbleSort()
{
int pass=1;
int comps=0;
Comparable temp;
int swaps;
boolean Sorted = false;
while (!Sorted)
{
swaps=0;
for (int j = 0; j < data.length - pass; j++) {
if ((data[j+1].leq(data[j])))
{
temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
swaps++;
}
comps++;
}
pass++;
Sorted = (pass == data.length) || swaps==0;
}
return comps;
}
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();
}
}
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();
}
}
/* Output:
the quick brown fox jumped over the lazy dog
Merge Sort Result:
brown dog fox jumped lazy over quick the the
Number of comparisons = 20
597 313 390 890 226 367 922 55 612 503 938 327 754 668 303 953 307 912 448 212
Merge Sort Result:
55 212 226 303 307 313 327 367 390 448 503 597 612 668 754 890 912 922 938 953
Number of comparisons = 67
the quick brown fox jumped over the lazy dog
Bubble Sort Result:
brown dog fox jumped lazy over quick the the
Number of comparisons = 36
Sorting integer array:
999 295 768 264 494 657 591 467 914 507 432 537 481 150 190 180 754 61 287 564
Bubble Sort Result:
61 150 180 190 264 287 295 432 467 481 494 507 537 564 591 657 754 768 914 999
Number of comparisons = 189
*/
Part D.
/*
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;
}
}
// Modified lex
public class ModLexStr implements Comparable
{
String value; //the String value of this ModLexStr object
// The Constructor.
ModLexStr(String v)
{
value = v;
}
// Yields true if this string is shorter than q or if they are
// equal and length and this string equals or comes before q
// "in the dictionary".
public boolean leq(Comparable q) {
String qvalue = ((ModLexStr)q).value;
//compare the strings value and qvalue lexicographically
//compareTo is defined in the String class
if (value.length() < qvalue.length()) return true;
if (value.length() > qvalue.length()) return false;
return value.compareTo(qvalue) <= 0;
}
// Yields the value of this string.
public String toString()
{
return value;
}
// Convert a String array to a LexStr array
public static ModLexStr[] convert(String[] s)
{
int i;
ModLexStr[] ls = new ModLexStr[s.length];
for (i = 0; i < s.length; i++)
ls[i] = new ModLexStr(s[i]);
return ls;
}
}
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();
}
}
/* Output:
the quick brown fox jumped over the lazy dog
Bubble Sort Result (Lexicographic Order:)
brown dog fox jumped lazy over quick the the
Number of comparisons = 36
the quick brown fox jumped over the lazy dog
Bubble Sort Result(Modified Lexicographic Order):
dog fox the the lazy over brown quick jumped
Number of comparisons = 36
*/