Using Merge Sort: In this project, we combine the concepts of Recursion and Sort
ID: 3801308 • Letter: U
Question
Using Merge Sort:
In this project, we combine the concepts of Recursion and Sorting. Since the Java Collection API provides various built-in sorting capabilities, so we will focus on Merge Sort and have it applied to a file.
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 "p6sortedArts.txt" which is sorted ascendingly on artistID and then artID both.
Example follows:
(sample output just for artistID) (have to sort both, ArtistID and then ArtID):
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
Programming Steps:
1) Create a class called Art that implements Comparable interface.
2) Read part of the file and use Merge Sort to sort the array of Art and then write them to a file.
3) Read some more 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.
p1arts.txt:
I am providing the sample programs that you might need:
MergeSort.java:
ArraySorter.java:
Name.java:
Artist.java:
Driver.java:
Explanation / Answer
Here is program for your question. comments are inline. Please do rate the answer if it helped. thanks.
---------------
import java.io.EOFException;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Art implements Comparable<Art> {
protected int artistId;
protected int artId;
protected String title;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getArtistId() {
return artistId;
}
public int getArtId() {
return artId;
}
public String getTitle() {
return title;
}
protected int value;
public Art(int artId1,int artistId1,String title1,int value1)
{
//set the data members
artId=artId1;
artistId=artistId1;
title=title1;
value=value1;
}
//compares 2 art objects. First compares artist id, only when they are same, then
//comparison is on artid. Return -1 whenever the current object is less than the art2
// 0, when both the artistid and artid on both objects are same and 1 when the current
//object is greater (i.e bigger artistid or in case of same artistid, the current object
//has bigger artid
@Override
public int compareTo(Art art2) {
if(artistId>art2.artistId)
return 1;
else if(artistId<art2.artistId)
return -1;
else //both artistid same.... now compare
{
if(artId>art2.artId)
return 1;
else if(artId<art2.artId)
return -1;
else
return 0;
}
}
public String toString()
{
return artistId+" "+artId+" "+title+" "+value+" ";
}
//loads sorted data from the specified file and returns the array
private static Art[] loadSortedData(RandomAccessFile file) throws NumberFormatException, IOException
{
int artid,artistid,value;
String title,line;
ArrayList<Art> list=new ArrayList<Art>();
Art art[]=null;
try
{
//if we not reached end of file
while((line=file.readLine())!=null)
{
Art a;
//read a line and tokenize it with tab delimiter
//System.out.println(line);
StringTokenizer tokenizer=new StringTokenizer(line, " ");
//the sequence in sorted file is artistid, artid, title and value
artistid=Integer.parseInt(tokenizer.nextToken());//artist id is the 1st token
artid=Integer.parseInt(tokenizer.nextToken()); //artid is 2 token
title=tokenizer.nextToken(); //title is 3 token
value=Integer.parseInt(tokenizer.nextToken());//value is the 4th token
a=new Art(artid,artistid,title,value);
list.add(a);
}
}
catch(EOFException e)
{
//; do nothing
}
art=new Art[list.size()];
list.toArray(art);
//System.out.println("----------------");
return art;
}
//loads size number of records from file. If there are less records, it loads only available
//records and returns the number of records that are loaded.
private static int loadData(Scanner file,Art[] arts,int size)
{
int count=0;
int artid,artistid,value;
String title,line;
//if we not reached end of file and not yet read size record
while(file.hasNext() && count<size)
{
Art a;
//read a line and tokenize it with tab delimiter
line=file.nextLine();
//System.out.println(line);
StringTokenizer tokenizer=new StringTokenizer(line, " ");
artid=Integer.parseInt(tokenizer.nextToken()); //artid is first token
title=tokenizer.nextToken(); //title is second token
artistid=Integer.parseInt(tokenizer.nextToken());//artist id is the 3rd token
value=Integer.parseInt(tokenizer.nextToken());//value is the 4th token
a=new Art(artid,artistid,title,value);
arts[count]=a;
count++;
}
return count;
}
private static void writeArray(RandomAccessFile file,Art[] art,int startIndex,int endIndex) throws IOException
{
if(art!=null && art.length>0)
{
for(int i=startIndex;i<endIndex;i++)
{
file.writeBytes(art[i].toString());
}
}
}
public static void main(String[] args) {
Scanner infile;
//PrintWriter outfile;
String outfilename="c:\test\p1sortedArts.txt";
RandomAccessFile outfile=null;
try {
infile=new Scanner(new File("c:\test\p1arts.txt"));
File f=new File(outfilename);
if(f.exists()) //delete output file if exiting already
f.delete();
outfile=new RandomAccessFile(f, "rw");
int MAX_RECORDS=25,count;
Art art[]=new Art[MAX_RECORDS],sorted[];
boolean firsttime=true;
while((count=loadData(infile, art, MAX_RECORDS))!=0) //while there are records loaded
{
ArraySorter.mergeSort(art,count); //sorts the art in the same array itself
if(firsttime) //first time just write to file and contiinue since there is no previous data to merge
{
writeArray(outfile, art,0,count);
firsttime=false;
continue;
}
outfile.seek(0); //go to beginnig of file
//if not first time,...we need to load sorted data from outfile and merge with new sorted array
sorted=loadSortedData(outfile); //load merged data from file
//after loading the outfile is pointing to end of file so we need to go back to begining
outfile.seek(0); //go to beginnig of file
int p1=0,p2=0; //p1 index to new sorted array, p2 index to old sorted data from file
//now we have 2 sorted array -art (new data) and sorted (old data)
//To merge these 2 arrays, each time we compare records from both arrays and write out the
//lesser one (compareto function) and increment its index leaving the other
//index as is. Finally if any left out records are there in any array we
//write it out
while(p1<count && p2<sorted.length)
{
if((art[p1].compareTo(sorted[p2]))<=0)
{
outfile.writeBytes(art[p1].toString());
p1++;
}
else
{
outfile.writeBytes(sorted[p2].toString());
p2++;
}
}
if(p1<count)
writeArray(outfile, art, p1, count);
if(p2<sorted.length)
writeArray(outfile, sorted, p2, sorted.length);
}
infile.close();
outfile.close();
} catch (FileNotFoundException e) {
System.out.println("File is not found "+e.getMessage());
} catch (IOException e) {
e.printStackTrace();
}
}
}
-------------
ouput for sample in question
-------------
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
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.