Question

USE JAVA PROGRAMMING

Create a program that would collect list of persons using double link list and use a Merge Sort to sort the object by age.



Create a class called Person : name and age

Create methods that add, and delete Person from the link list

Create a method that sorts the persons' objects by age.

package mergesort;


public class MergeSortExample {

private static Comparable[] aux; // auxiliary array for merges

public static void sort(Comparable[] a)
{
aux = new Comparable[a.length]; // Allocate space just once.
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{ // Sort a[lo..hi].
if (hi <= lo)
return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid); // Sort left half.
sort(a, mid+1, hi); // Sort right half.
merge(a, lo, mid, hi); // Merge results (code on page 271).
}

public static void merge(Comparable[] a, int lo, int mid, int hi)
{ // Merge a[lo..mid] with a[mid+1..hi].
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) // Copy a[lo..hi] to aux[lo..hi].
aux[k] = a[k];
for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi].
if (i > mid)
a[k] = aux[j++];
else if (j > hi )
a[k] = aux[i++];
else if (less(aux[j], aux[i]))
a[k] = aux[j++];
else
a[k] = aux[i++];
}

private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

/***************************************************************************
* Check if array is sorted - useful for debugging.
***********************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}

private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}

public static void main(String[] args) {
String [] fields = {"D","A","C","B","A"};
sort(fields);
show(fields);
}





}

Answer 1

CODE:

import java.util.*;
import java.lang.*;
import java.io.*;

class Person
{
static Node head;
  
  
static class Node {
String name;
int age;
Node prev;
Node next;
  
Node(String n, int a) { name=n; age = a; }
}
  
public void add(String n, int a)
{
   Node new_node = new Node(n,a);
  
   Node last = head;
  
   new_node.next = null;
  
   if (head == null) {
       new_node.prev = null;
       head = new_node;
       return;
   }
  
   while (last.next != null)
       last = last.next;
  
   last.next = new_node;
   new_node.prev = last;
}

Node split(Node head) {
Node fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
Node temp = slow.next;
slow.next = null;
return temp;
}
  
Node mergeSort(Node node) {
if (node == null || node.next == null) {
return node;
}
Node second = split(node);
  
node = mergeSort(node);
second = mergeSort(second);
  
return merge(node, second);
}
  
Node merge(Node first, Node second) {
if (first == null) {
return second;
}
if (second == null) {
return first;
}
  
if (first.age < second.age) {
first.next = merge(first.next, second);
first.next.prev = first;
first.prev = null;
return first;
} else {
second.next = merge(first, second.next);
second.next.prev = second;
second.prev = null;
return second;
}
}
void print(Node node) {
Node temp = node;
System.out.println("Forward Traversal using next pointer");
while (node != null) {
System.out.println(node.age + " " + node.name);
temp = node;
node = node.next;
}
}
  
   public static void main (String[] args) throws java.lang.Exception
   {
       // write main code here
       Person list= new Person();
       list.head = new Node("xyz",10);
list.head.next = new Node("pqr",30);
list.head.next.next = new Node("amaaa",3);
list.head.next.next.next = new Node("abc",4);
list.head.next.next.next.next = new Node("answer",20);
list.head.next.next.next.next.next = new Node("sjj",5);
Node node = null;
node = list.mergeSort(head);
System.out.println("Linked list after sorting :");
list.print(node);
   }
}

SAMPLE OUTPUT:

Linked list after sorting :
Forward Traversal using next pointer
3 amaaa
4 abc
5 sjj
10 xyz
20 answer
30 pqr