forked from AndrewProgramming/JavaTutorialCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSortLargeFile.java
More file actions
197 lines (171 loc) · 5.64 KB
/
SortLargeFile.java
File metadata and controls
197 lines (171 loc) · 5.64 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
package sort;
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
public class SortLargeFile {
public static final int MAX_ARRAY_SIZE = 43;
public static final int BUFFER_SIZE = 100000;
public static void main(String[] args) throws Exception {
// Sort largedata.dat to sortedfile.dat
sort("largedata.dat", "sortedfile.dat");
// Display the first 100 numbers in the sorted file
displayFile("sortedfile.dat");
}
/**
* Sort data in source file and into target file
*/
public static void sort(String sourcefile, String targetfile)
throws Exception {
// Implement Phase 1: Create initial segments
int numberOfSegments =
initializeSegments(MAX_ARRAY_SIZE, sourcefile, "f1.dat");
// Implement Phase 2: Merge segments recursively
merge(numberOfSegments, MAX_ARRAY_SIZE,
"f1.dat", "f2.dat", "f3.dat", targetfile);
}
/**
* Sort original file into sorted segments
*/
private static int initializeSegments
(int segmentSize, String originalFile, String f1)
throws Exception {
int[] list = new int[segmentSize];
DataInputStream input = new DataInputStream(
new BufferedInputStream(new FileInputStream(originalFile)));
DataOutputStream output = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(f1)));
int numberOfSegments = 0;
while (input.available() > 0) {
numberOfSegments++;
int i = 0;
for (; input.available() > 0 && i < segmentSize; i++) {
list[i] = input.readInt();
}
// Sort an array list[0..i-1]
java.util.Arrays.sort(list, 0, i);
// Write the array to f1.dat
for (int j = 0; j < i; j++) {
output.writeInt(list[j]);
}
}
input.close();
output.close();
return numberOfSegments;
}
private static void merge(int numberOfSegments, int segmentSize,
String f1, String f2, String f3, String targetfile)
throws Exception {
if (numberOfSegments > 1) {
mergeOneStep(numberOfSegments, segmentSize, f1, f2, f3);
merge((numberOfSegments + 1) / 2, segmentSize * 2,
f3, f1, f2, targetfile);
} else { // Rename f1 as the final sorted file
File sortedFile = new File(targetfile);
if (sortedFile.exists()) {
sortedFile.delete();
}
new File(f1).renameTo(sortedFile);
}
}
private static void mergeOneStep(int numberOfSegments,
int segmentSize, String f1, String f2, String f3)
throws Exception {
DataInputStream f1Input = new DataInputStream(
new BufferedInputStream(new FileInputStream(f1), BUFFER_SIZE));
DataOutputStream f2Output = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(f2), BUFFER_SIZE));
// Copy half number of segments from f1.dat to f2.dat
copyHalfToF2(numberOfSegments, segmentSize, f1Input, f2Output);
f2Output.close();
// Merge remaining segments in f1 with segments in f2 into f3
DataInputStream f2Input = new DataInputStream(
new BufferedInputStream(new FileInputStream(f2), BUFFER_SIZE));
DataOutputStream f3Output = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(f3), BUFFER_SIZE));
mergeSegments(numberOfSegments / 2,
segmentSize, f1Input, f2Input, f3Output);
f1Input.close();
f2Input.close();
f3Output.close();
}
/**
* Copy first half number of segments from f1.dat to f2.dat
*/
private static void copyHalfToF2(int numberOfSegments,
int segmentSize, DataInputStream f1, DataOutputStream f2)
throws Exception {
for (int i = 0; i < (numberOfSegments / 2) * segmentSize; i++) {
f2.writeInt(f1.readInt());
}
}
/**
* Merge all segments
*/
private static void mergeSegments(int numberOfSegments,
int segmentSize, DataInputStream f1, DataInputStream f2,
DataOutputStream f3) throws Exception {
for (int i = 0; i < numberOfSegments; i++) {
mergeTwoSegments(segmentSize, f1, f2, f3);
}
// If f1 has one extra segment, copy it to f3
while (f1.available() > 0) {
f3.writeInt(f1.readInt());
}
}
/**
* Merges two segments
*/
private static void mergeTwoSegments(int segmentSize,
DataInputStream f1, DataInputStream f2,
DataOutputStream f3) throws Exception {
int intFromF1 = f1.readInt();
int intFromF2 = f2.readInt();
int f1Count = 1;
int f2Count = 1;
while (true) {
if (intFromF1 < intFromF2) {
f3.writeInt(intFromF1);
if (f1.available() == 0 || f1Count++ >= segmentSize) {
f3.writeInt(intFromF2);
break;
} else {
intFromF1 = f1.readInt();
}
} else {
f3.writeInt(intFromF2);
if (f2.available() == 0 || f2Count++ >= segmentSize) {
f3.writeInt(intFromF1);
break;
} else {
intFromF2 = f2.readInt();
}
}
}
while (f1.available() > 0 && f1Count++ < segmentSize) {
f3.writeInt(f1.readInt());
}
while (f2.available() > 0 && f2Count++ < segmentSize) {
f3.writeInt(f2.readInt());
}
}
/**
* Display the first 100 numbers in the specified file
*/
public static void displayFile(String filename) {
try {
DataInputStream input =
new DataInputStream(new FileInputStream(filename));
for (int i = 0; i < 100; i++) {
System.out.print(input.readInt() + " ");
}
input.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
}