Last time we learned about how to use/implement the merge sort, and we also talked about how Java uses the merge sort by default.

In this assignment, you are going to be given a file that reads a data file for a number of values, and then sorts them by name. This has been done for you and uses the default Collections.sort. However we also want to be able to sort the users by the ID number.

Your assignment is to implement the merge sort on the array of people, but you will need to use the ID as the key to determine what order they go in. You will not be able to use the default sort since it uses the compareTo method, but you need to compare based on something else.

Download the main program, the two data files, and then find the method that you need to implement and implement it. You may also need to implement additional methods to make it work.

The program does time your algorithm, so I would encourage you to try to make it as fast as you can, and you can compare your version to the default sort to see how you are doing.

The Files:

• MergeSortTesting.java
• DataFileInClass5.txt
• DataFileInClass5ver2.txt

Helpful Notes:

• To make a copy of a part of a list, use the following approach
  • List> smallerVersion = new ArrayList>()
  • smallerVersion.addAll( originalList.subList(startPoint,endPoint) )
• Take a look at the Person class, to see what you have access to.
• Don't be afraid to look at the prior notes for help with the merge sort.

MergeSortTesting.java

import java.util.Scanner;

import java.io.File;

import java.io.FileNotFoundException;

import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

public class MergeSortTesting

{

private List myList= new ArrayList();

public static void main(String[] args)

{

MergeSortTesting obj = new MergeSortTesting();

obj.run();

}

public void run()

{

//MAKE SURE TO UNCOMMENT ONE OF THE LINES BELOW

//File f = new File("DataFileInClass5.txt");

//File f = new File("DataFileInClass5ver2.txt");

Scanner scan = null;

try

{

scan = new Scanner(f);

}

catch (FileNotFoundException e)

{

System.out.println("File Not found");

System.exit(0);

}

while(scan.hasNext())

{

int i = scan.nextInt();

String a = scan.next();

String b = scan.next();

Person temp = new Person(i,a,b);

myList.add(temp);

//System.out.println(temp);

}

//System.out.println(myList);

long startTime = System.currentTimeMillis();

Collections.sort(myList);

long endTime = System.currentTimeMillis();

sortListByID(myList);

long endTime2 = System.currentTimeMillis();

//Print out the first 5 elements for checking.

//Do not print out the whole list, it takes too long.

System.out.println("Checking the order");

System.out.println("The first five elements are:");

for (int i=0;i

System.out.println();

System.out.printf("The computer sort took %d (ms) to run.%n" , endTime-

startTime);

System.out.printf(" My sort took %d (ms) to run.%n" , endTime2-

endTime);

}

private class Person implements Comparable

{

private String fName;

private String lName;

private int ID;

public int getID()

{return ID;}

public String getName()

{return fName + " " + lName;}

Person(int a, String b, String c)

{

fName = b;

lName = c;

ID = a;

}

public String toString()

{return "["+lName +", " + fName + " #" + ID+"]";}

public int compareTo(Person o)

{

if (lName.compareTo(o.lName)==0) return fName.compareTo(o.fName);

else return lName.compareTo(o.lName);

}

}

private static void sortListByID (List theList)

{

//TODO

// WRITE YOUR MERGE SORT HERE

// MAKE SURE TO SORT BY ID

//

}

}

DataFileInClass5.txt

91058312 Malika Schulman

69807422 Krysta Lorraine

8927564 Suk Cesar

196816038 Magda Kastner

194671164 Antone Brunell

105752387 Jeannette Luse

87833366 Dorotha Costigan

178889081 Elina Crandall

185162708 Jerrold Schrimsher

33395580 Magan Frier

Transcribed image text