Using Merge Sort: (In Java) (Please screenshot or copy your output file in the a
ID: 3814690 • Letter: U
Question
Using Merge Sort: (In Java) (Please screenshot or copy your output file in the answer)
Please note that the focus is on Merging and don't forget the following constraint:
Programming Steps:
1) Create a class called Art that implements Comparable interface.
2) Read first 30 records of Arts, use Merge Sort to sort the array of Art and then write them to a file.
3) Read next 30 records from the file, sort them, and merge them with the sorted file on the disk.
4) Repeat the above step until it is all done.
5) Sort Artist ID first and then Art ID.
6) Sort 30 Art IDs at a time. FIrst 30, then other 30, then other 30 and so on.
7) Create temporory files to store the sorted records in.
8) After sorting all Art IDs, merge them and write to output file "p6Out.txt"
Additional Specs and Requirements:
1. Your RAM can only holds 30 records at most at any time;
2. Read the files into arrays, 30 records at a time.
3. Sort them and then write to a temporary output file.
4. So, with 116 input Art records you should have 4 temporary sorted files.
5. You then merge two files into one, so you will then create more temp files.
6. Eventually you will have two temp files left and you merge these two into the file output file.
7. Keep all the temperorary files and their output.
Read the programming steps for guidance.
File specifications:
a) The input file that you are going to use is the tab-delimited text file "p1arts.txt".
b) the output file that you are going to produce using File I/O is also the tabdelimited text file called "p6Out.txt" which is sorted ascendingly on artistID and then artID both.
Example output follows:
(sample output)
ArtistID ArtID Title Appraised Value
1 1038 Spring Flowers 800
1 1050 Cattle Ranch 10000
1 1103 Trail End 8000
2 1042 Coffee on the Trail 7544
3 1013 Superstitions 78000
3 1021 Bead Wall 14000
3 1034 Beaver Pole Jumble 28000
3 1063 Asleep in the Garden 110000
4 1070 Beginnings 27500
5 1036 Blackhawk 25500
6 1017 Brittlecone 1300
6 1053 Blue Eyed Indian 40000
6 1056 Cavalry Is Coming 1900
6 1075 Western Boots and Spurs 6000
6 1077 Bull Riding 5200
7 1049 Buttercup with Red Lip 400
8 1018 Mountain Scene 2500
9 1055 Starlit Evening 9500
10 1096 Ceremonial Sticks 15000
11 1090 Off the Grid 8000
12 1003 Spring Flowers 2400
13 1081 Coming Under Fire 650
14 1039 Treachery 20000
14 1102 Crying Hats 10000
15 1073 Dancing in the Light 4000
16 1052 American Rodeo 3500
17 1059 Dwelling 16000
18 1005 The Hang 8000
19 1011 Eve 975
20 1099 Watch That Rattler 900
21 1037 Floating World 2350
22 1109 Friends 16000
23 1084 Crossing the Platt River 2200
24 1072 Funnel 4500
25 1115 Starry Night 8500
26 1008 End of the Path 1900
27 1112 Dark Canyon 8000
28 1009 Amen 3000
28 1030 Ash Bench 13000
28 1043 Creosote Bushes 18000
28 1078 Chuckwagon 32000
29 1041 Night Version 3800
29 1082 Spring Flowers 20000
30 1116 Apache Warrior 23000
31 1029 Horseshoe Falls 15000
32 1006 House Remembered 700
33 1046 Immediate Gratification 1500
34 1031 Inside/Out 3500
35 1107 Striking It Rich 1750
36 1051 Night Version 7000
37 1088 Lessons 3700
38 1045 Leaf Patterns 2100
38 1100 Hungry Cowboys 750
39 1094 Life Is Sweet 25000
40 1106 Horse Corral 12500
41 1062 Cowboy and Saddle 18000
42 1032 Rising Sun 2000
42 1060 Story Sticks 650
43 1044 Mexican Fiesta 14000
44 1047 Medicine Man 2500
45 1014 Plenty 500
46 1015 Punch 10000
47 1023 Shooting the Rapids 1300
47 1027 Mountain Climber 4700
47 1035 Nature/Nurture 1300
47 1040 Night on the Praire 1300
47 1065 Moonlite 1300
47 1092 Dressing Up 1300
48 1024 Spirit and Nature 592
49 1067 Owl in Flight 7000
50 1001 Red Rock Mountain 18000
50 1028 Tired Cowboy 4700
50 1054 Snake Charmer 4500
50 1068 Moonlight 9750
50 1069 Renaissance 5500
50 1113 Shadow House 5500
50 1114 Storytelling at the Campfire 18000
51 1064 Spirit Columns 7000
52 1002 Offerings 10000
53 1089 Life Lessons 4125
54 1091 Stone Palette 11500
55 1074 Storm on the Rise 8000
56 1098 Sweet Project 592
57 1048 Comfy Chair 800
58 1101 The Red Door 10000
59 1080 The Dust Behind 18000
60 1058 The Gathering 250
61 1019 The White Heart 9300
61 1095 The Spirit 20000
62 1079 Carrying the Mail 8000
62 1093 Antelopes 12500
62 1110 Three Sisters 6500
63 1085 Traces 20000
64 1004 Seeking Shelter 52000
64 1083 Untitled 2500
65 1016 Untitled 6000
66 1026 Untitled (couple) 4000
66 1057 Untitled 4500
67 1086 Untitled (desert landscape) 18000
68 1025 Profile of a Woman 625
69 1022 The Cowboy 4200
70 1104 Untitled 1800
71 1010 Untitled (land with adobe) 800
72 1111 Untitled (man and crucifix) 3200
73 1020 Untitled (Man holding coat) 3000
74 1012 Man on Horseback 8000
75 1097 Untitled (Sea) 2800
76 1066 Untitled (still life) 19500
77 1033 Untitled (Woman abstract) 2500
77 1108 Untitled Mural 400
78 1061 Untitled Mural 3520
79 1071 Ride the Rapids 300
79 1076 Ride the Bronco 1500
80 1105 Meteor Show 10000
81 1087 Three Woman 20000
82 1007 Homage to the Ancestors 1200
p1arts.txt:
I am providing the sample programs that you might need:
Name.java:
Artist.java:
MergeSort.java:
ArraySorter.java:
Name.java:
Artist.java:
Driver.java:
Explanation / Answer
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Objects;
/**
*
* @author Sam
*/
public class ArtSort {
static final int MAXSIZE = 30;
private static int readData(BufferedReader input, Art[] list) throws IOException{ //to read data in chunks of MAXSIZE
int count = 0;
String line;
while (count < MAXSIZE && (line = input.readLine())!= null) {
String[] tokens = line.split(" ");
list[count++] = new Art(Integer.parseInt(tokens[0]), Integer.parseInt(tokens[1]), tokens[2], Integer.parseInt(tokens[3]));
}
return count;
}
private static void write(PrintWriter output, Art[] list, int size){ //Write the array to file
for (int i=0; i<size; i++)
output.println(list[i].artistID+" "+list[i].artID+" "+list[i].title+" "+list[i].appraisedValue);
output.flush();
}
private static void copyFile(PrintWriter output, BufferedReader input) throws IOException{//Copy input file content to outputFile
String line;
while ((line=input.readLine())!=null)
output.println(line);
output.flush();
}
private static void sort(Art[] list, int low, int high) { //merge sort driver
if ((high - low) >= 1) // if not base case
{
int middle1 = (low + high) / 2; // calculate middle of array
int middle2 = middle1 + 1; // calculate next element over
// split array in half; sort each half (recursive calls)
sort(list, low, middle1); // first half of array
sort(list, middle2, high); // second half of array
merge(list, low, middle1, middle2, high);
} // end if
} // end method sortArray
private static void merge(Art[] data, int left, int middle1, int middle2, int right) {
int leftIndex = left; // index into left subarray
int rightIndex = middle2; // index into right subarray
int combinedIndex = left; // index into temporary working array
Art[] combined = new Art[data.length]; // working array
// merge arrays until reaching end of either
while (leftIndex <= middle1 && rightIndex <= right) {
// place smaller of two current elements into result
// and move to next space in arrays
if (data[leftIndex].compareTo(data[rightIndex]) < 0) {
combined[combinedIndex++] = data[leftIndex++];
}
else {
combined[combinedIndex++] = data[rightIndex++];
}
} // end while
// if left array is empty
if (leftIndex == middle2) {// copy in rest of right array
while (rightIndex <= right) {
combined[combinedIndex++] = data[rightIndex++];
}
}
else // right array is empty
// copy in rest of left array
{
while (leftIndex <= middle1) {
combined[combinedIndex++] = data[leftIndex++];
}
}
// copy values back into original array
for (int i = left; i <= right; i++) {
data[i] = combined[i];
}
} // end method merge
public static void main(String[] args) throws IOException {
int tempCount = 1;
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please Enter input file name: ");
BufferedReader inputFile = new BufferedReader(new FileReader(input.readLine()));
PrintWriter pw;
Art[] list = new Art[MAXSIZE];
int sz = readData(inputFile, list);
while (sz > 0){ //read file till inputFile bufferReader contains data
sort(list, 0, sz-1); //sort the list
pw = new PrintWriter(new File("temp"+tempCount++));//and write it to temp file
write(pw, list, sz);
pw.close();
sz = readData(inputFile, list);//read next chunk of data
}
pw = new PrintWriter(new File("p6Out.txt"));
for (int i=1; i<tempCount; i++) {
inputFile = new BufferedReader(new FileReader("temp"+i));//copy all temp file to final file
copyFile(pw, inputFile);
}
pw.close();
}
}
class Art implements Comparable<Art> {
int artistID, artID, appraisedValue;
String title;
public Art(int artistID, int artID, String title, int appraisedValue) {
this.artistID = artistID;
this.artID = artID;
this.appraisedValue = appraisedValue;
this.title = title;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Art other = (Art) obj;
if (this.artistID != other.artistID) {
return false;
}
if (this.artID != other.artID) {
return false;
}
if (this.appraisedValue != other.appraisedValue) {
return false;
}
if (!Objects.equals(this.title, other.title)) {
return false;
}
return true;
}
@Override
public int compareTo(Art o) {
if (artistID == o.artistID) {
return artID - o.artID;
}
return artistID - o.artistID;
}
}
The code is really long (160 lines). I commented the code as far as possible. Copied the merge sort method from your given code with minor change to meet the need and redice memory useage. Go through the code, It is well commented, and i hope you will like the code. And incase you find any difficulty in understanding the code, please let me know. I shall be glad to help you solve your problem.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.