This assignment is to exercise and validate the theoretical cost of the sorting
ID: 3676743 • Letter: T
Question
This assignment is to exercise and validate the theoretical cost of the sorting algorithms we covered in class, through practical implementation of them. Sorting Algorithms and Performance. 1. Input/Output: Read in an input data file in a plain text format as an argument. Example: $pgm1 1000.txt or $java pgm1 1000.txt The program should be named pgm1.c, pgm1.cpp or pgm1.java etc. Submit only program source file(s) and your own input data files (at least two such that one with size 100, another in 1000 records). The format of your input and output data file is specified as follows: 10 Stocker Norris | 3631 W. 8th Ln. #264 | TRUCKEE | CA | 96161 Saylor Alisya | 1854 W. Green Ln. #89 | LITTLE SUAMICO | WI | 54141 Moore Lucy | 1471 E. Forest Rd. #139 | TALMAGE | KS | 67482 Ryals Larson | 8385 E. Hillcrest St. | LEWISTON | MN | 55952 Sherill Hardy | 7313 N. Franklin Blvd. | TAHLEQUAH | OK | 74464 Justin Ray | 9251 N. Cherry Way #221 | MAMARONECK | NY | 10543 Justin Ray | 4357 N. Broadway Way | LAKELAND | LA | 70752 Earhart Alanis | 7515 N. Washington Way #72 | LOUISE | TX | 77455 Draudy Joleen | 201 NE 23rd St. | HOUSTON | TX | 77061 Bishop Holden | PO Box 409 | CARONA | KS | 66773 where 10 is the number of input records. Each line is a record. The name should be sorted in ascending order of last name and then first name. The address should be sorted in ascending order of state, city, zip code, and street address. The format of the output file is the same as the input file format but in different order. 2. Program: Your program is to perform sorting of the records in your input data file, using insertion sort, mergesort and quicksort, by the following order 1)sort by last name --> 2)sort by first name --> 3)sort by state --> 4)sort by city --> 5)sort by zip code --> 6)sort by street address. All task should be done by one run. Ask the user to restart the program for each sorting algorithm is not acceptable. 3. Performance: Record the running time by using a virtual stopwatch. Then plot a performance graph for algorithms. In the performance graph, x-axis will be # of data (records of line), and y-axis will be the execution time. Note that you may use any plotting programs such as MS-Excel, gnuplot, Maple, Matlab or etc. The unit of the time should be as accurate as micro second.
Explanation / Answer
RecordGenerator.java
import java.util.ArrayList;
import java.util.List;
import java.io.BufferedWriter;
import java.io.FileWriter;
import com.kkirch.Record;
public class RecordGenerator {
public static void main(String ... args) throws Exception {
if (args.length != 1) {
System.out.println("Invalid Usage -- please supply the number of records to generate");
System.out.println("`java -cp pgm1-...jar com.kkirch.generator.RecordGenerator 500`");
} else {
int numberOfRecords = Integer.parseInt(args[0]);
List<Record> records = new ArrayList<Record>();
NameGenerator nameGenerator = new NameGenerator();
AddressGenerator addressGenerator = new AddressGenerator();
for (int i = 0; i < numberOfRecords; ++i) {
Record r = new Record(nameGenerator.generateName(),
nameGenerator.generateName(),
addressGenerator.generateAddress(),
addressGenerator.generateCity(),
addressGenerator.generateState(),
addressGenerator.generateZipCode());
records.add(r);
}
String outFile = numberOfRecords + ".txt";
BufferedWriter bw = new BufferedWriter(new FileWriter(outFile));
bw.write(String.format("%d%n",numberOfRecords));
for (Record r : records) {
bw.write(String.format("%s%n", r.toDelimitedString()));
}
try {
bw.close();
} catch (Exception e) {
System.out.println("Failed to close buffered writer");
}
}
}
}
NameGenerator.java
import java.util.Random;
public class NameGenerator {
Random r = new Random();
String[] names = new String[]{
"Arlette",
"Justa",
"Christena",
"Annis",
"Simon",
"Annamaria",
"Roxanna",
"Mabelle",
"Keven",
"Kati",
"Isabell",
"Estela",
"Zofia",
"Latosha",
"Maire",
"Shawnda",
"Sid",
"Mitzie",
"Hong",
"Danica",
"Kasandra",
"Maryann",
"Elda",
"Cristi",
"Bruna",
"Rigoberto",
"Robbie",
"Omega",
"Andrew",
"Delilah",
"Shanel",
"Debroah",
"Elizabeth",
"Margert",
"Ramona",
"Susan",
"Darla",
"Kari",
"Francesco",
"Jesenia",
"Wiley",
"Siu",
"Myriam",
"Kizzie",
"Lily",
"Emiko",
"Regena",
"Scarlet",
"Mariana",
"Marva"
};
public String generateName() {
return names[r.nextInt(names.length)];
}
}
AddressGenerator.java
import java.util.Random;
public class AddressGenerator {
Random r = new Random();
String[] streetNames = new String[]{
"Washington",
"Regina",
"Pine",
"Rainy",
"Bluff",
"Wall",
"Lancer",
"Walker",
"Penn",
"Council",
"Rockwell",
"Hefner"
};
String[] streetSuffixes = new String[]{
"Pl.",
"St.",
"Way",
"Ave.",
"Blvd."
};
String[] cities = new String[]{
"Mobile",
"Tucson",
"Knoxville",
"Daytona Beach",
"Grand Rapids",
"Stockton",
"San Antonio",
"Fresno",
"Louisville",
"Norfolk-Virginia Beach",
"Charlotte",
"Charleston",
"New Orleans",
"Columbia",
"Raleigh",
"Harrisburg",
"Scranton",
"Rochester",
"Nashville",
"Toledo",
"Las Vegas",
"Richmond",
"Boise City",
"Cincinnati",
"Providence",
"Tulsa",
"Columbus",
"Oklahoma City",
"Greenville",
"Little Rock",
"Kansas City",
"Omaha",
"Dayton",
"Sarasota-Bradenton",
"Tampa",
"Memphis",
"Baton Rouge",
"Miami",
"Youngstown",
"Austin",
"Syracuse"
};
String[] states = new String[]{
"AL",
"AK",
"AZ",
"AR",
"CA",
"CO",
"CT",
"DE",
"FL",
"GA",
"HI",
"ID",
"IL",
"IN",
"IA",
"KS",
"KY",
"LA",
"ME",
"MD",
"MA",
"MI",
"MN",
"MS",
"MO",
"MT",
"NE",
"NV",
"NH",
"NJ",
"NM",
"NY",
"NC",
"ND",
"OH",
"OK",
"OR",
"PA",
"RI",
"SC",
"SD",
"TN",
"TX",
"UT",
"VT",
"VA",
"WA",
"WV",
"WI",
"WY"
};
public String generateAddress() {
String address = (r.nextInt(15000) + 1) + " ";
switch (r.nextInt(4)) {
case 0:
address += "N. ";
break;
case 1:
address += "S. ";
break;
case 2:
address += "W. ";
break;
case 3:
address += "E. ";
break;
}
address += streetNames[r.nextInt(streetNames.length)] + " ";
address += streetSuffixes[r.nextInt(streetSuffixes.length)];
if (r.nextBoolean()) {
address += " #" + r.nextInt(100);
}
return address;
}
public String generateCity() {
return cities[r.nextInt(cities.length)];
}
public int generateZipCode() {
return 70000
+ 5000
+ r.nextInt(10) * 100
+ r.nextInt(10) * 10
+ r.nextInt(10);
}
public String generateState() {
return states[r.nextInt(states.length)];
}
}
AddressComparator.java
import java.util.Comparator;
public class AddressComparator implements Comparator<Record> {
public int compare(Record a, Record b) {
if (a == null && b == null) {
return 0;
} else if ((a == null && b != null)
|| (a != null && b == null)) {
return a == null ? 1 : -1;
} else {
return a.address.compareToIgnoreCase(b.address);
}
}
}
CityComparator.java
import java.util.Comparator;
public class CityComparator implements Comparator<Record> {
public int compare(Record a, Record b) {
if (a == null && b == null) {
return 0;
} else if ((a == null && b != null)
|| (a != null && b == null)) {
return a == null ? 1 : -1;
} else {
return a.city.compareToIgnoreCase(b.city);
}
}
}
FirstNameComparator.java
import java.util.Comparator;
public class FirstNameComparator implements Comparator<Record> {
public int compare(Record a, Record b) {
if (a == null && b == null) {
return 0;
} else if (
(a == null && b != null)
|| (a != null && b == null)) {
return a == null ? 1 : 0;
} else {
return a.firstName.compareToIgnoreCase(b.firstName);
}
}
}
InsertionsortSorter.java
import java.util.Comparator;
import java.util.List;
public class InsertionsortSorter implements Sorter<Record> {
public void sortList(List<Record> records, Comparator<Record> comparator) {
int j;
Record key;
int i;
for (j = 1; j < records.size(); j++)
{
key = records.get(j);
for (i = j - 1; (i >= 0) && comparator.compare(key, records.get(i)) < 0; i--)
{
records.set(i + 1, records.get(i));
}
records.set(i + 1, key);
}
}
}
LastNameComparator.java
import java.util.Comparator;
public class LastNameComparator implements Comparator<Record> {
public int compare(Record a, Record b) {
if (a == null && b == null) {
return 0;
} else if (
(a == null && b != null)
|| (a != null && b == null)) {
return a == null ? 1 : 0;
} else {
return a.lastName.compareToIgnoreCase(b.lastName);
}
}
}
NameAddressComparator.java
import java.util.Comparator;
public class NameAddressComparator implements Comparator<Record> {
public int compare(Record a, Record b) {
if (a == null && b == null) {
return 0;
} else if ((a == null && b != null)
|| (a != null && b == null)) {
return a == null ? 1 : -1;
} else {
int recordCompare = a.lastName.compareToIgnoreCase(b.lastName);
if (recordCompare == 0) {
recordCompare = a.firstName.compareToIgnoreCase(b.firstName);
}
if (recordCompare == 0) {
recordCompare = a.state.compareToIgnoreCase(b.state);
}
if (recordCompare == 0) {
recordCompare = a.city.compareToIgnoreCase(b.city);
}
if (recordCompare == 0) {
if (a.zipcode > b.zipcode) {
recordCompare = 1;
} else if (a.zipcode < b.zipcode) {
recordCompare = -1;
} else {
recordCompare = 0;
}
}
if (recordCompare == 0) {
recordCompare = a.address.compareToIgnoreCase(b.address);
}
return recordCompare;
}
}
}
QuicksortSorter.java
import java.util.Comparator;
import java.util.List;
public class QuicksortSorter implements Sorter<Record> {
public void sortList(List<Record> records, Comparator<Record> comparator) {
sortList(records, comparator, 0, records.size() - 1);
}
private void sortList(List<Record> records, Comparator<Record> comparator, int left, int right) {
if (left < right) {
int pivotIndex = randPartition(records, comparator, left, right);
sortList(records, comparator, left, pivotIndex - 1);
sortList(records, comparator, pivotIndex + 1, right);
}
}
private int randPartition(List<Record> records, Comparator<Record> comparator, int left, int right) {
int randPivot = left + (int) (Math.random() * ((right - left) + 1));
swap(records, right, randPivot);
return partition(records, comparator, left, right);
}
private int partition(List<Record> records, Comparator<Record> comparator, int left, int right) {
// Select pivot element
Record pivot = records.get(right);
int i = left - 1;
for (int j = left; j < right; ++j) {
int comparison = comparator.compare(records.get(j), pivot);
if (comparison < 0) {
i++;
swap(records, i, j);
}
}
// Move the pivot element in the middle of the array
swap(records, i + 1, right);
// Return the pivot element index
return i + 1;
}
private void swap(List<Record> records, int a, int b) {
Record temp = records.get(a);
records.set(a, records.get(b));
records.set(b, temp);
}
}
Pgm1.java
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.util.Map;
import static java.util.Map.Entry;
public class Pgm1 {
public static void main(String... args) throws Exception {
Sorter<Record> sorter = new InsertionsortSorter();
if (args.length != 1) {
System.out.println("Invalid Usage -- please supply a filename as an argument");
System.out.println("`java -jar pgm1-...jar 10.txt`");
} else {
String filename = args[0];
//we have a filename, make sure file exists
File file = new File(filename);
if (!file.exists()) {
System.out.println("The file you supplied doesn't seem to exist!");
} else {
//start processing
System.out.println("Found file " + filename);
String filename_number = filename.split("\.")[0];
RecordSorter recordSorter = new RecordSorter();
String nameFileName = "name_" + filename;
String lNameFileName = "lName_" + filename;
Map<String, String> lNameSortPerformance = recordSorter.sortRecordsFromFileByKeyWithOutputFile(
filename,
new LastNameComparator(),
sorter,
lNameFileName);
String fNameFileName = "fName_" + filename;
Map<String, String> fNameSortPerformance = recordSorter.sortRecordsFromFileByKeyWithOutputFile(
lNameFileName,
new FirstNameComparator(),
sorter,
nameFileName);
new File(lNameFileName).delete();
File namePerformanceFile = new File("name_" + filename_number + "_time.txt");
if (!namePerformanceFile.exists()) {
namePerformanceFile.createNewFile();
}
BufferedWriter bw = new BufferedWriter(new FileWriter(namePerformanceFile));
for (Entry<String, String> entry : fNameSortPerformance.entrySet()) {
bw.write(String.format("%6s %s ", entry.getKey(), entry.getValue()));
}
try {
bw.close();
} catch (Exception e) {
System.out.println("Failed to close buffered writer");
}
String addressFileName = "address_" + filename;
String stateFileName = "state_address_" + filename;
String cityFileName = "city_address_" + filename;
String zipFileName = "zip_address_" + filename;
Map<String, String> stateSortPerformance = recordSorter.sortRecordsFromFileByKeyWithOutputFile(
nameFileName,
new StateComparator(),
sorter,
stateFileName);
Map<String, String> citySortPerformance = recordSorter.sortRecordsFromFileByKeyWithOutputFile(
stateFileName,
new CityComparator(),
sorter,
cityFileName);
Map<String, String> zipSortPerformance = recordSorter.sortRecordsFromFileByKeyWithOutputFile(
cityFileName,
new ZipcodeComparator(),
sorter,
zipFileName);
Map<String, String> addressSortPerformance = recordSorter.sortRecordsFromFileByKeyWithOutputFile(
zipFileName,
new AddressComparator(),
sorter,
addressFileName);
new File(stateFileName).delete();
new File(cityFileName).delete();
new File(zipFileName).delete();
File addressPerformanceFile = new File("address_" + filename_number + "_time.txt");
if (!addressPerformanceFile.exists()) {
addressPerformanceFile.createNewFile();
}
bw = new BufferedWriter(new FileWriter(addressPerformanceFile));
for (Entry<String, String> entry : addressSortPerformance.entrySet()) {
bw.write(String.format("%6s %s ", entry.getKey(), entry.getValue()));
}
try {
bw.close();
} catch (Exception e) {
System.out.println("Failed to close buffered writer");
}
}
}
}
}
Record.java
public class Record {
public final String lastName;
public final String firstName;
public final String address;
public final String city;
public final String state;
public final int zipcode;
public Record(String delimitedString) {
String[] parts = delimitedString.split(" \| ");
String name = parts[0];
String[] nameParts = name.split(" ");
firstName = nameParts[0];
lastName = nameParts[1];
address = parts[1];
city = parts[2];
state = parts[3];
zipcode = Integer.parseInt(parts[4]);
}
public Record(final String lastName,
final String firstName,
final String address,
final String city,
final String state,
final int zipcode){
this.lastName = lastName;
this.firstName = firstName;
this.address = address;
this.city = city;
this.state = state;
this.zipcode = zipcode;
}
public String toDelimitedString() {
return new StringBuilder()
.append(firstName).append(" ").append(lastName)
.append(" | ")
.append(address)
.append(" | ")
.append(city)
.append(" | ")
.append(state)
.append(" | ")
.append(zipcode).toString();
}
@Override
public String toString() {
return new StringBuilder()
.append("Record = {")
.append("First Name : ").append(firstName)
.append(", Last Name : ").append(lastName)
.append(", Address : ").append(address)
.append(", City : ").append(city)
.append(", State : ").append(state)
.append(", Zipcode : ").append(zipcode)
.append(" }").toString();
}
}
Sorter.java
import java.util.Comparator;
import java.util.List;
public interface Sorter<T> {
void sortList(List<T> records, Comparator<T> comparator);
}
ZipcodeComparator.java
import java.util.Comparator;
public class ZipcodeComparator implements Comparator<Record> {
public int compare(Record a, Record b) {
if (a == null && b == null) {
return 0;
} else if ((a == null && b != null)
|| (a != null && b == null)) {
return a == null ? 1 : -1;
} else {
int recordCompare = 0;
if (a.zipcode > b.zipcode) {
recordCompare = 1;
} else if (a.zipcode < b.zipcode) {
recordCompare = -1;
}
return recordCompare;
}
}
}
StateComparator.java
import java.util.Comparator;
public class StateComparator implements Comparator<Record> {
public int compare(Record a, Record b) {
if (a == null && b == null) {
return 0;
} else if ((a == null && b != null)
|| (a != null && b == null)) {
return a == null ? 1 : -1;
} else {
return a.state.compareToIgnoreCase(b.state);
}
}
}
RecordSorter.java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class RecordSorter {
public Map<String,String> sortRecordsFromFileByKeyWithOutputFile(
String inFileName,
Comparator<Record> comparator,
Sorter sorter,
String outFileName) throws FileNotFoundException, IOException {
Map<String,String> performanceData = new LinkedHashMap<String,String>();
File inFile = new File(inFileName);
File outFile = new File(outFileName);
BufferedReader br = new BufferedReader(new FileReader(inFile));
List<Record> unsortedRecords = new ArrayList<Record>();
List<Record> sortedRecords = null;
int numberOfRecords = Integer.parseInt(br.readLine());
String line;
while((line = br.readLine()) != null) {
Record r = new Record(line);
unsortedRecords.add(r);
}
try {
br.close();
} catch (Exception e) {
System.out.println("Failed to close buffered reader");
}
List<Record> unsortedSublist = new ArrayList<Record>();
for (int i = 0; i < numberOfRecords; ++i) {
unsortedSublist.add(unsortedRecords.get(i));
long startTime = System.nanoTime();
sorter.sortList(unsortedSublist, comparator);
//unsortedSublist now sorted...
long endTime = System.nanoTime();
long totalTime = (endTime - startTime) / 1000; //convert to microseconds
performanceData.put((i + 1) + "", totalTime + "");
if ((i + 1) == numberOfRecords) {
sortedRecords = new ArrayList<Record>(unsortedSublist);
}
}
//write to disk
if (!outFile.exists()) {
outFile.createNewFile();
}
BufferedWriter bw = new BufferedWriter(new FileWriter(outFile));
bw.write(String.format("%d%n",numberOfRecords));
for (Record r : sortedRecords) {
bw.write(String.format("%s%n", r.toDelimitedString()));
}
try {
bw.close();
} catch (Exception e) {
System.out.println("Failed to close buffered writer");
}
return performanceData;
}
}
100.txt
100
Maryann Justa | 3483 N. Hefner St. #61 | Toledo | FL | 75474
Maire Francesco | 2806 W. Pine Blvd. | Harrisburg | AL | 75890
Marva Kizzie | 1850 E. Rockwell Way #96 | Tulsa | FL | 75139
Lily Susan | 13222 W. Regina Way #33 | Providence | SC | 75748
Shawnda Annis | 5931 N. Pine Blvd. #72 | Las Vegas | AL | 75001
Robbie Rigoberto | 13405 N. Regina Pl. | Oklahoma City | CT | 75491
Elda Roxanna | 7013 W. Rockwell Blvd. #38 | Little Rock | MD | 75313
Kasandra Kasandra | 194 N. Penn Pl. | Rochester | KS | 75954
Arlette Mitzie | 14545 N. Hefner Way #51 | Greenville | VA | 75920
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.