1. Given an integer array A = f3; 6; 10; 18; 8; 7; 25; 40g,
(a) Write your own Java source code named MergeSort.java to implement Merge Sort algorithm on the array A. Please finish your code in the following template, where “XXXSort” is replaced with “MergeSort”.
(b) Write your own Java source code named HeapSort.java to implement Heap Sort algorithm on the array A. Please also finish your code in the following template, where “XXXSort” is replaced with “HeapSort”.
(c) Write your own Java source code named QuickSort.java to implement Quick Sort algorith-m on the array A. Please also finish your code in the following template, where “XXXSort” is replaced with “QuickSort”.
public class XXXSort
{
public static void main()
{
int[] A = {3, 6, 10, 18, 8, 7, 25, 40};
sort(A);
show(A); // display the sorted result A
}
public static void sort(int[] A)
{
...
}
public static void show(int[] A)
{
...
}
... // add all other functions you need
}
2. Write a Java source code named TreeOrder.java to first store the following tree (left), where each node is represented by the private class Node (right), and then implement the functions of PreOrder, InOrder, and PostOrder and output the result of each type of order on the tree.
root 1
12
2
3
10
19
4
5
13
15
6
7
14
18
[20] 3. Write a linear-time algorithm in java named CheckBST.java to determine whether a binary tree is a binary search tree. Take the following two binary trees as input (For the conveniences, you can first store the two binary trees in your java codes.) to test your algorithm.
root 1
root 1
13
12
2
3
2
3
10
19
10
19
4
5
4
5
12
15
13
15
6
7
6
7
14
18
14
18
