-
Notifications
You must be signed in to change notification settings - Fork 0
/
ExternalSort.java
176 lines (150 loc) · 4.92 KB
/
ExternalSort.java
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
import java.util.Arrays;
import java.util.Scanner;
import java.io.PrintWriter;
import java.nio.file.Path;
import java.nio.file.Paths;
public class ExternalSort {
// track number of values read
public static int numValues = 0;
public static void main(String[] args) {
Scanner input = new Scanner(System.in); // Scanner object to get input from kb
int runsize = input.nextInt(); // get runsize from user
Path t1 = Paths.get("src/T1.txt"); // Path to T1 for input
Path p = extsort(t1, runsize);
}
public static Path extsort(Path t1, int runsize) {
// Get paths for each text file
Path t2 = Paths.get("src/T2.txt");
Path t3 = Paths.get("src/T3.txt");
Path t4 = Paths.get("src/T4.txt");
try {
// Read from t1
Scanner input = new Scanner(t1);
// Write to t3 and t4
PrintWriter t3Write = new PrintWriter(t3.toString());
PrintWriter t4Write = new PrintWriter(t4.toString());
// Str and int arr to store ints
String str = null;
int[] arr;
// read all numbers of T1
while (input.hasNextInt()) {
str = read(input, str, runsize); // read 4 values and store in arr
arr = convertToArr(str); // Convert str to arr
Arrays.sort(arr); // Sort arr
str = convertToStr(arr); // Convert sorted arr to str
t3Write.print(str); // Write sorted arr to file t3
str = read(input, str, runsize); // read 4 values and store in arr
arr = convertToArr(str); // Convert str to arr
Arrays.sort(arr); // Sort arr
str = convertToStr(arr); // Convert sorted arr to str
t4Write.print(str); // Write sorted arr to file t4
}
// close t3 and t4 after writing
t3Write.close();
t4Write.close();
// Get number of runs depending if even
int numRuns = getNumRuns(runsize);
for (int i = 0; i < numRuns; i++) {
if (i % 2 == 0) {
Scanner t3Read = new Scanner(t3);
Scanner t4Read = new Scanner(t4);
boolean print = false;
PrintWriter t1Write = new PrintWriter(t1.toString());
PrintWriter t2Write = new PrintWriter(t2.toString());
while (t3Read.hasNextInt()) {
//str = read(t3Read, str, (int)(runsize * Math.pow(2, i)));
int count = 0;
str = "";
str = read(t3Read, str, (int)(runsize * Math.pow(2, i)));
int counts = 0;
while (t4Read.hasNextInt() && counts < runsize * Math.pow(2, i)) {
str += t4Read.nextInt() + " ";
counts++;
}
arr = convertToArr(str); // Convert str to arr
Arrays.sort(arr); // Sort arr
str = convertToStr(arr); // Convert sorted arr to str
// print data on tap1 or tap2 based on the condition
if (!print) t1Write.print(str);
else t2Write.print(str);
// set other tap
print = !print;
}
t1Write.close();
t2Write.close();
} else {
str = "";
// open input tap files T1 and T2
Scanner t1Read = new Scanner(t1);
Scanner t2Read = new Scanner(t2);
boolean print = false;
// open outputfiles tap T3 and T4
PrintWriter tap3 = new PrintWriter(t3.toString());
PrintWriter tap4 = new PrintWriter(t4.toString());
// loop until tap1 has next input
while (t1Read.hasNextInt()) {
int count = 0;
while (t1Read.hasNextInt() && count < runsize * Math.pow(2, i)) {
str += t1Read.nextInt() + " ";
count++;
}
int counts = 0;
while (t2Read.hasNextInt() && counts < runsize * Math.pow(2, i)) {
str += t2Read.nextInt() + " ";
counts++;
}
arr = convertToArr(str); // Convert str to arr
Arrays.sort(arr); // Sort arr
str = convertToStr(arr); // Convert sorted arr to str
// print data on tap1 or tap2 based on the condition
if (!print)
tap3.print(str);
else
tap4.print(str);
// set other tap
print = !print;
}
tap3.close();
tap4.close();
}
}
}
catch (Exception e) {
System.out.println("Read: " + t1);
System.out.println("Write: " + t3 + " " + t4);
System.out.println(e);
}
return t1;
}
private static int getNumRuns(int runsize) {
if (numValues % (2 * runsize) == 0)
return numValues / (2 * runsize);
return numValues / (2 * runsize) + 1;
}
private static String convertToStr(int[] a) {
StringBuilder sb = new StringBuilder();
for (Integer i : a) {
sb.append(i);
sb.append(" ");
}
return sb.toString();
}
private static int[] convertToArr(String s) {
String[] strArr = s.split(" "); // " " token
int[] arr = new int[strArr.length]; // create array
// str to int arr
for (int i = 0; i < arr.length; i++)
arr[i] = Integer.parseInt(strArr[i]);
return arr;
}
public static String read(Scanner input, String str, int runsize) {
str = ""; // Initialize string when making arr
int numElem = 0; // count elements
while (input.hasNextInt() && numElem < runsize) {
str += input.nextInt() + " ";
numElem++;
numValues++;
}
return str;
}
}