Implement the given algorithm in Java: import java.io.BufferedReader; import jav
ID: 3835961 • Letter: I
Question
Implement the given algorithm in Java:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class FinalList {
private final List<Integer> unsortedList;
public FinalList(String filename) throws IOException {
BufferedReader in = new BufferedReader(new FileReader(filename));
unsortedList = new LinkedList<Integer>();
while (in.ready()) {
String line = in.readLine();
int num = Integer.parseInt(line);
unsortedList.add(num);
}
in.close();
}
public String toString() {
return unsortedList.toString();
}
private List<Integer> copyList() {
int n = unsortedList.size();
List<Integer> list = new ArrayList<Integer>(n);
for (int i = 0; i < n; ++i) { // copy the list
list.add(unsortedList.get(i));
}
return list;
}
public List<Integer> bubbleSort() {
List<Integer> sortedList = copyList();
int n = sortedList.size();
boolean swapped;
do {
swapped = false;
for (int i = 1; i < n; ++i) {
if (sortedList.get(i - 1) > sortedList.get(i)) {
// swap
int temp = sortedList.get(i - 1);
sortedList.set(i - 1, sortedList.get(i));
sortedList.set(i, temp);
swapped = true;
}
}
--n;
} while (swapped);
return sortedList;
}
public List<Integer> selectionSort() {
List<Integer> sortedList = copyList();
int n = sortedList.size();
for (int j = 0; j < n - 1; ++j) {
int i_Min = j;
for (int i = j + 1; i < n; ++i) {
if (sortedList.get(i) < sortedList.get(i_Min)) {
i_Min = i;
}
}
if (i_Min != j) {
// swap
int temp = sortedList.get(j);
sortedList.set(j, sortedList.get(i_Min));
sortedList.set(i_Min, temp);
}
}
return sortedList;
}
public List<Integer> heapSort() {
List<Integer> sortedList = copyList();
Heap heap = new Heap(sortedList);
heap.heapify();
int end = heap.count() - 1;
while (end > 0) {
// swap
int temp = heap.get(end);
heap.set(end, heap.get(0));
heap.set(0, temp);
--end;
heap.siftDown(0, end);
}
return sortedList;
}
private class Heap {
private List<Integer> a;
public Heap(List<Integer> list) {
a = list;
}
public int count() {
return a.size();
}
public int get(int index) {
return a.get(index);
}
public void set(int index, int element) {
a.set(index, element);
}
public void heapify() {
int count = count();
int start = Math.floorDiv(count - 1, 2);
while (start >= 0) {
siftDown(start, count - 1);
--start;
}
}
public void siftDown(int start, int end) {
/* ADD CODE BELOW */
/* ADD CODE ABOVE */
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter("output.txt");
for (int i = 1; i <= 3; ++i) {
FinalList l = new FinalList("list" + i + ".txt");
out.println(l);
System.out.println("List " + i + ":");
// Bubble Sort
long start = System.nanoTime();
List<Integer> sortedList = l.bubbleSort();
long end = System.nanoTime();
out.println(sortedList);
System.out.println("Bubble Sort execution time in seconds: " + (double)(end - start) / 1000000000L + " [first element = " + sortedList.get(0) + ", last element = " + sortedList.get(sortedList.size() - 1) + "]");
// Selection Sort
start = System.nanoTime();
sortedList = l.selectionSort();
end = System.nanoTime();
out.println(sortedList);
System.out.println("Selection Sort execution time in seconds: " + (double)(end - start) / 1000000000L + " [first element = " + sortedList.get(0) + ", last element = " + sortedList.get(sortedList.size() - 1) + "]");
// Heap Sort
start = System.nanoTime();
sortedList = l.heapSort();
end = System.nanoTime();
out.println(sortedList);
System.out.println("Heap Sort execution time in seconds: " + (double)(end - start) / 1000000000L + " [first element = " + sortedList.get(0) + ", last element = " + sortedList.get(sortedList.size() - 1) + "]");
out.println();
System.out.println();
}
out.close();
}
}
Explanation / Answer
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class FinalList {
private final List<Integer> unsortedList;
public FinalList(String filename) throws IOException {
BufferedReader in = new BufferedReader(new FileReader(filename));
unsortedList = new LinkedList<Integer>();
while (in.ready()) {
String line = in.readLine();
int num = Integer.parseInt(line);
unsortedList.add(num);
}
in.close();
}
public String toString() {
return unsortedList.toString();
}
private List<Integer> copyList() {
int n = unsortedList.size();
List<Integer> list = new ArrayList<Integer>(n);
for (int i = 0; i < n; ++i) { // copy the list
list.add(unsortedList.get(i));
}
return list;
}
public List<Integer> bubbleSort() {
List<Integer> sortedList = copyList();
int n = sortedList.size();
boolean swapped;
do {
swapped = false;
for (int i = 1; i < n; ++i) {
if (sortedList.get(i - 1) > sortedList.get(i)) {
// swap
int temp = sortedList.get(i - 1);
sortedList.set(i - 1, sortedList.get(i));
sortedList.set(i, temp);
swapped = true;
}
}
--n;
} while (swapped);
return sortedList;
}
public List<Integer> selectionSort() {
List<Integer> sortedList = copyList();
int n = sortedList.size();
for (int j = 0; j < n - 1; ++j) {
int i_Min = j;
for (int i = j + 1; i < n; ++i) {
if (sortedList.get(i) < sortedList.get(i_Min)) {
i_Min = i;
}
}
if (i_Min != j) {
// swap
int temp = sortedList.get(j);
sortedList.set(j, sortedList.get(i_Min));
sortedList.set(i_Min, temp);
}
}
return sortedList;
}
public List<Integer> heapSort() {
List<Integer> sortedList = copyList();
Heap heap = new Heap(sortedList);
heap.heapify();
int end = heap.count() - 1;
while (end > 0) {
// swap
int temp = heap.get(end);
heap.set(end, heap.get(0));
heap.set(0, temp);
--end;
heap.siftDown(0, end);
}
return sortedList;
}
private class Heap {
private List<Integer> a;
public Heap(List<Integer> list) {
a = list;
}
public int count() {
return a.size();
}
public int get(int index) {
return a.get(index);
}
public void set(int index, int element) {
a.set(index, element);
}
public void heapify() {
int count = count();
int start = Math.floorDiv(count - 1, 2);
while (start >= 0) {
siftDown(start, count - 1);
--start;
}
}
public void siftDown(int start, int end) {
}
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter("output.txt");
for (int i = 1; i <= 3; ++i) {
FinalList l = new FinalList("list" + i + ".txt");
out.println(l);
System.out.println("List " + i + ":");
// Bubble Sort
long start = System.nanoTime();
List<Integer> sortedList = l.bubbleSort();
long end = System.nanoTime();
out.println(sortedList);
System.out.println("Bubble Sort execution time in seconds: " + (double)(end - start) / 1000000000L + " [first element = " + sortedList.get(0) + ", last element = " + sortedList.get(sortedList.size() - 1) + "]");
// Selection Sort
start = System.nanoTime();
sortedList = l.selectionSort();
end = System.nanoTime();
out.println(sortedList);
System.out.println("Selection Sort execution time in seconds: " + (double)(end - start) / 1000000000L + " [first element = " + sortedList.get(0) + ", last element = " + sortedList.get(sortedList.size() - 1) + "]");
// Heap Sort
start = System.nanoTime();
sortedList = l.heapSort();
end = System.nanoTime();
out.println(sortedList);
System.out.println("Heap Sort execution time in seconds: " + (double)(end - start) / 1000000000L + " [first element = " + sortedList.get(0) + ", last element = " + sortedList.get(sortedList.size() - 1) + "]");
out.println();
System.out.println();
}
out.close();
}
}
int root = start;