This assignment is to exercise and validate the theoretical cost of the sorting
ID: 3692346 • 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. 100.TXT
100 Alan Wright | 816 Rainforest | BIRMINGHAM | AL | 35201 Alan Phillips | 310 McElroy | MOBILE | AL | 36613 Alan Tomas | 498 Oakshire | ROCK HILL | SC | 29730 Betty Smith | 1126 Victor | HUNTSVILLE | AL | 35810 Betty Wright | 378 Turtlehill | GOOSE CREEK | SC | 29445 Betty Phillips | 754 Albright | DETROIT | MI | 48201 Betty Tomas | 569 Lake Fork | BIRMINGHAM | AL | 35201 Cherry Smith | 1083 Bella Monte | BIRMINGHAM | AL | 35201 Cherry Wright | 176 Sierra Grande | NORMAN | OK | 73026 Cherry Phillips | 948 Chamonix | WEST LINN | OR | 97068 Cherry Tomas | 1027 Campus Center | CHARLESTON | SC | 29403 Danial Smith | 370 Cindy | DENVER | CO | 80202 Danial Hil | 648 Maple | OKLAHOMA CITY | OK | 73105 Danial Phillips | 219 Rainforest | GOOSE CREEK | SC | 29445 Danial Moore | 1399 McElroy | DENVER | CO | 80014 Ellen Smith | 1096 Oakshire | MOBILE | AL | 36618 Ellen Hil | 841 Victor | OKLAHOMA CITY | OK | 73130 Ellen Phillips | 1221 Turtlehill | COLORADO SPRINGS | CO | 80902 Ellen Moore | 746 Albright | HUNTSVILLE | AL | 35816 Frank Smith | 1246 Lake Fork | COLORADO SPRINGS | CO | 80902 Frank Hil | 105 Bella Monte | YPSILANTI | MI | 48197 Frank Phillips | 1122 Sierra Grande | OKLAHOMA CITY | OK | 73105 Frank Moore | 1061 Chamonix | LAS CRUCES | NM | 88011 George Smith | 1 Campus Center | DENVER | CO | 80211 George Hil | 959 Cindy | LAS CRUCES | NM | 88011 George Parker | 1407 Maple | COLUMBIA | SC | 29217 George Moore | 1773 Rainforest | ANNISTON | AL | 36201 Helen Johnson | 1568 McElroy | ROCK HILL | SC | 29730 Helen Hil | 578 Oakshire | COLORADO SPRINGS | CO | 80902 Helen Parker | 235 Victor | PORTLAND | OR | 97086 Helen Moore | 1512 Turtlehill | COLORADO SPRINGS | CO | 80902 Irin Johnson | 89 Albright | HUNTSVILLE | AL | 35810 Irin Hil | 1352 Lake Fork | OKLAHOMA CITY | OK | 73105 Irin Parker | 532 Bella Monte | FARMINGTON | NM | 87401 Irin Moore | 525 Sierra Grande | MOBILE | AL | 36618 Jenny Johnson | 1338 Chamonix | SANTA FE | NM | 87506 Jenny Hil | 1462 Campus Center | MOBILE | AL | 36603 Jenny Parker | 1834 Cindy | MONTGOMERY | AL | 36107 Jenny Anderson | 1091 Maple | BIRMINGHAM | AL | 35223 Kan Johnson | 547 Rainforest | BIRMINGHAM | AL | 35223 Kan Green | 901 McElroy | LAS CRUCES | NM | 88011 Kan Parker | 762 Oakshire | ALBUQUERQUE | NM | 87124 Kan Anderson | 1424 Victor | ANNISTON | AL | 36201 Laurence Johnson | 578 Turtlehill | GOOSE CREEK | SC | 29445 Laurence Green | 186 Albright | COLORADO SPRINGS | CO | 80902 Laurence Parker | 547 Lake Fork | SUMTER | SC | 29150 Laurence Anderson | 107 Bella Monte | SANTA FE | NM | 87506 Martin Johnson | 917 Sierra Grande | AUBURN | AL | 36830 Martin Green | 1372 Chamonix | AUBURN | AL | 36830 Martin Parker | 1507 Campus Center | AUBURN | AL | 36830 Martin Anderson | 1178 Cindy | COLUMBIA | SC | 29204 Nancy Davis | 139 Maple | TULSA | OK | 74107 Nancy Green | 1138 Rainforest | NORMAN | OK | 73026 Nancy Edwards | 1290 McElroy | AUBURN | AL | 36830 Nancy Anderson | 1460 Oakshire | TULSA | OK | 74107 Oliver Davis | 322 Victor | TULSA | OK | 74136 Oliver Green | 1137 Turtlehill | NORMAN | OK | 73026 Oliver Edwards | 485 Albright | MOBILE | AL | 36613 Oliver Anderson | 1246 Lake Fork | ALBUQUERQUE | NM | 87101 Peter Davis | 56 Bella Monte | ANNISTON | AL | 36201 Peter Green | 49 Sierra Grande | PORTLAND | OR | 97209 Peter Edwards | 259 Chamonix | COLORADO SPRINGS | CO | 80902 Peter Anderson | 1409 Campus Center | COLUMBIA | SC | 29204 Qi Davis | 1501 Cindy | HUNTSVILLE | AL | 35824 Qi Bakeer | 1031 Maple | TULSA | OK | 74107 Qi Edwards | 610 Rainforest | MOBILE | AL | 36618 Qi Miller | 321 McElroy | HUNTSVILLE | AL | 35810 Rober Davis | 1599 Oakshire | SANTA FE | NM | 87501 Rober Bakeer | 139 Victor | ALBUQUERQUE | NM | 87101 Rober Edwards | 1714 Turtlehill | BIRMINGHAM | AL | 35201 Rober Miller | 1974 Albright | DETROIT | MI | 48206 Steve Davis | 44 Lake Fork | DETROIT | MI | 48201 Steve Bakeer | 179 Bella Monte | TULSA | OK | 74136 Steve Edwards | 1376 Sierra Grande | COLORADO SPRINGS | CO | 80902 Steve Miller | 150 Chamonix | MOBILE | AL | 36618 Tim Davis | 259 Campus Center | ALBUQUERQUE | NM | 87124 Tim Bakeer | 1957 Cindy | LAS CRUCES | NM | 88011 Tim Stewart | 171 Maple | HUNTSVILLE | AL | 35824 Tim Miller | 1480 Rainforest | ALBUQUERQUE | NM | 87124 Uter Thompson | 1122 McElroy | DETROIT | MI | 48201 Uter Bakeer | 185 Oakshire | ALBUQUERQUE | NM | 87124 Uter Stewart | 1010 Victor | COLUMBIA | SC | 29220 Uter Miller | 1618 Turtlehill | LAWTON | OK | 73505 Virginia Thompson | 1032 Albright | FARMINGTON | NM | 87401 Virginia Bakeer | 499 Lake Fork | BIRMINGHAM | AL | 35223 Virginia Stewart | 274 Bella Monte | ROCK HILL | SC | 29730 Virginia Miller | 1195 Sierra Grande | SANTA FE | NM | 87501 Welson Thompson | 243 Chamonix | HUNTSVILLE | AL | 35816 Welson Bakeer | 347 Campus Center | MOBILE | AL | 36603 Welson Stewart | 1227 Cindy | MONTGOMERY | AL | 36107 Welson Brown | 521 Maple | BIRMINGHAM | AL | 35223 Xin Thompson | 49 Rainforest | ALBUQUERQUE | NM | 87109 Xin Nelson | 968 McElroy | BIRMINGHAM | AL | 35201 Xin Stewart | 652 Oakshire | DENVER | CO | 80202 Xin Brown | 1186 Victor | CHARLESTON | SC | 29403 Ying Thompson | 1043 Turtlehill | HUNTSVILLE | AL | 35810 Ying Nelson | 1952 Albright | FARMINGTON | NM | 87401 Ying Stewart | 1121 Lake Fork | DENVER | CO | 80014 Ying Brown | 1005 Bella Monte | HUNTSVILLE | AL | 35824 Zue Thompson | 388 Sierra Grande | YPSILANTI | MI | 48197
Explanation / Answer
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");
}
}
}
}
}
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);
}
}
}
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;
}
}
}
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();
}
}
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;
}
}
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);
}
}
}
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);
}
}
}
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);
}
}
}
Sorter.java
import java.util.Comparator;
import java.util.List;
public interface Sorter<T> {
void sortList(List<T> records, Comparator<T> comparator);
}
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);
}
}
}
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);
}
}
}
10.txt
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.