please i need help, this is Java: You have to implement your own LinkedList clas
ID: 3726716 • Letter: P
Question
please i need help, this is Java:
You have to implement your own LinkedList class in this homework (either Doubly or Singly is fine). And you have to implement your own Queue data structure (either an Array-based or a LinkedList-based queue is fine).
Please implement the MergeSort algorithm on a LinkedList object, as we learned in the class. The logic idea is shown below. If you failed to follow this logic idea, you could get a zero in this homework.
1, Enqueue all data elements of the linked list, with each element wrapped up and enqueued as a separate one-node list object.
2, while there is more than 1 items in Queue
a. dequeue and assign to a linked list reference sublist1
b. dequeue again and assign to another linked list reference sublist2
c. walk through sublist1 and sublist2 and merge them into a larger sorted listed tempList, with tempList = ( sublist1 merged with sublist2 )
d. equeue tempList
3, dequeue your sorted linked list.
Please implement the InsertionSort algorithm on a LinkedList object, as we learned in the class.
Please write a method boolean isSorted(LinkedList B) to verify whether the LinkedList B is correctly sorted in an ascending order.
boolean isSorted(LinkedList B)
Note: isSorted(LinkedList B) returns true, if B has been sorted in ascending order. Otherwise it returns false.
Note: your isSorted(LinkedList B) has to run in the time complexity of O(n), where n is the size of the input LinkedList. In other words, you scan the input list B once, you should know whether it is sorted or not.
In your main() method in a source file named Tester.java, please create an empty LinkedList A, then please use the Java Random class to generate a sequence S of 20,000 integers, which range between 0 and 3,000,000. You have to insert each element of S into the LinkedList A, with each list node in A holding one integer.
NOTE PLEASE READ: For those who have an old and slow machine, sorting two 20,000 integers maybe too time-consuming. You can generate 2000 integers and sort them, instead of 20,000.
In your main() method of the Tester.java file, please create another separate LinkedList object A2, which contains the same set of integers as A does.
Please invoke the method of your MergeSort() algorithm implementation on the input list A in the separate java file Tester.java. Then call isSorted(A) to verify whether A is correctly sorted.
Please invoke the method of your InsertionSort() algorithm implementation on the input list A2 in the separate java file Tester.java. Then call isSorted(A2) to verify whether A2 is correctly sorted.
Your main() method of your Tester class should perform the operations described in the below,
// First Create A and A2,
// Randomly generate two million integers and insert them into both A and A2.
//……
//measure the time cost of merge sort
double then = System.currentTimeMillis();
A.MergeSort();
double now = System.currentTimeMillis();
System.out.println(“Time cost in milliseconds for mergesort two million elements are: ” + (now – then));
System.out.println( isSorted(A) ); //verify that your merge sort implementation works.
//measure the time cost of insertion sort
then = System.currentTimeMillis();
A2.InsertionSort();
now = System.currentTimeMillis();
System.out.println(“Time cost in milliseconds for insertionsort two million elements are: ” + (now – then));
System.out.println( isSorted(A2) ); //verify that your insertion sort implementation works.
Please organize your source code so that I can compile all your source files in one folder using command, javac *.java, and run your program using command on command line, java Tester.
// First Create A and A2,
// Randomly generate two million integers and insert them into both A and A2.
//……
//measure the time cost of merge sort
double then = System.currentTimeMillis();
A.MergeSort();
double now = System.currentTimeMillis();
System.out.println(“Time cost in milliseconds for mergesort two million elements are: ” + (now – then));
System.out.println( isSorted(A) ); //verify that your merge sort implementation works.
//measure the time cost of insertion sort
then = System.currentTimeMillis();
A2.InsertionSort();
now = System.currentTimeMillis();
System.out.println(“Time cost in milliseconds for insertionsort two million elements are: ” + (now – then));
System.out.println( isSorted(A2) ); //verify that your insertion sort implementation works.
Explanation / Answer
***************Tester.java****************
import java.util.*;
class Tester {
/**
* Checks if Linked List is Sort
* @param l: Linked List
* @return: True if Sorted
*/
public static Boolean isSorted(LinkedList l) {
Node node = l.head;
while (node.next != null){
if (node.data > node.next.data){ // Node not is Ascending Order
return false;
}
node = node.next;
}
return true;
}
public static void main(String args[]) {
int size = 20000; // Size of Linked List
Random rand = new Random(); // For random Number generator
int val = rand.nextInt(3000001); // Generates random number between [0, 3000000]
// Creates two linked list with same values
Node nodeA = new Node(val);
Node nodeB = new Node(val);
LinkedList A = new LinkedList(nodeA); // linked list A
LinkedList A2 = new LinkedList(nodeB); // Linked List A2
for (int i = 0; i < size-1; i++) {
val = rand.nextInt(3000001) ; // random number
Node nextNodeA = new Node(val);
Node nextNodeB = new Node(val);
nodeA.next = nextNodeA;
nodeA = nextNodeA;
nodeB.next = nextNodeB;
nodeB = nextNodeB;
}
A.size = size;
A2.size = size;
//measure the time cost of merge sort
double then = System.currentTimeMillis();
A.MergeSort();
double now = System.currentTimeMillis();
System.out.println("Time cost in milliseconds for mergesort two million elements are: " + (now - then));
System.out.println(isSorted(A)); //verify that your merge sort implementation works.
//measure the time cost of insertion sort
then = System.currentTimeMillis();
A2.InsertionSort();
now = System.currentTimeMillis();
System.out.println("Time cost in milliseconds for insertionsort two million elements are: " + (now - then));
System.out.println(isSorted(A2));//verify that your insertion sort implementation works.
}
}
*******************Node.java***************************
public class Node {
int data;
Node next;
/**
* Constructor of Node
* Creates Node with data and next node as null
* @param data: data for Node
*/
Node(int data){
this.data = data;
this.next = null;
}
}
*******************LinkedList.java*************************
public class LinkedList {
Node head;
int size;
/**
* Linked List Constructor with only 1 node
* @param head: head of list
*/
public LinkedList(Node head) {
this.head = head;
this.size = 1;
}
/**
* Implements Merge Sort
*/
void MergeSort(){
LinkedList queue[] = new LinkedList[100000]; // Create a Queue with each element as linked list of size 100000
int index = 0; // for each index of queue
// Add elements to the queue
Node node = head;
while (node != null){
LinkedList ll = new LinkedList(new Node(node.data)); // Create linked list and add to queue
queue[index] = ll;
node = node.next;
index++;
}
int top = 0; // front most element of queue index
int queueEnd = size-1; // last element of queue index
while (queueEnd - top > 0 ){ // 1 element left in queue
// get top 2 linked list
LinkedList linkedList1 = queue[top];
LinkedList linkedList2 = queue[top+1];
top +=2; // remove it from queue
Node node1 = linkedList1.head;
Node node2 = linkedList2.head;
// get head of new linked list from linked list heads
Node sortedNode = null;
if (node1.data < node2.data){
sortedNode = new Node(node1.data);
node1 = node1.next;
} else {
sortedNode = new Node(node2.data);
node2 = node2.next;
}
LinkedList sortLinkedList = new LinkedList(sortedNode);// create new linked list
// Merge sort implementation
while (node1 != null && node2 != null){
if (node1.data < node2.data){ //get lower value node and insert to linked list
sortedNode.next = new Node(node1.data);
node1 = node1.next;
} else{
sortedNode.next = new Node(node2.data);
node2 = node2.next;
}
sortedNode = sortedNode.next;
}
// Add nodes to new list if nodes are left in linked list1
while (node1 != null){
sortedNode.next = new Node(node1.data);
node1 = node1.next;
sortedNode = sortedNode.next;
}
// Add nodes to new list if nodes are left in linked list 2
while (node2 != null){
sortedNode.next = new Node(node2.data);
node2 = node2.next;
sortedNode = sortedNode.next;
}
// new list is total of list1 and list 2
sortLinkedList.size = linkedList1.size + linkedList2.size;
// add new list created to end of queue
queueEnd++;
queue[queueEnd] = sortLinkedList;
}
head = queue[top].head;
}
/**
* Implements Insertion Sort
*/
void InsertionSort(){
Node sortedHead = new Node(head.data); // head of new Linked list
Node currentNode = head.next;
while (currentNode != null){ // loop till end of list
sortedHead = insertElement(sortedHead, new Node(currentNode.data)); // insert element to new linked list
currentNode = currentNode.next;
}
head = sortedHead; //new head of list
}
/**
* Inserts element to new Linked List (Used in Insertion Sort)
* @param sortedHead: Head of new Linked list
* @param insertNode: New Node to be inserted
* @return: returns head of new LInked list
*/
private Node insertElement(Node sortedHead, Node insertNode){
if (insertNode.data < sortedHead.data){ // to be inserted before head
insertNode.next = sortedHead;
return insertNode;
}
Node node = sortedHead;
while (node.next!= null){
if (node.next.data > insertNode.data){ // get position where to insert node
insertNode.next = node.next;
node.next = insertNode;
return sortedHead;
}
node = node.next;
}
node.next = insertNode; // insert at end of list
return sortedHead;
}
}
**************************
Sample Output:
Time cost in milliseconds for mergesort two million elements are: 19.0
true
Time cost in milliseconds for insertionsort two million elements are: 1099.0
true
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.