Need Java help with PersonSort class: import java.util.*; import java.io.*; publ
ID: 3714432 • Letter: N
Question
Need Java help with PersonSort class:
import java.util.*;
import java.io.*;
public class PersonSort
{
private static int numCompares = 0;
private static boolean printList = true;
public static void main (String[] args) throws Exception
{
// File name for testing the algorithms
final String PERSON_FILE32 = ".\src\Person32.txt";
// ArrayList size array for printing
String[] size = {"1K", "2K", "4K", "8K", "16K"};
// This set of files are for determining the running time of sorting randomized Persons
String[] random =
{".\src\Person1Ka.txt", ".\src\Person2Ka.txt", ".\src\Person4Ka.txt",
".\src\Person8Ka.txt", ".\src\Person16Ka.txt"};
// This set of files are for determining the running time of sorting sorted Persons
String[] sorted =
{".\src\Person1Kb.txt", ".\src\Person2Kb.txt", ".\src\Person4Kb.txt",
".\src\Person8Kb.txt", ".\src\Person16Kb.txt"};
// This set of files are for determining the running time of sorting sorted Persons
String[] revsorted =
{".\src\Person1Kc.txt", ".\src\Person2Kc.txt", ".\src\Person4Kc.txt",
".\src\Person8Kc.txt", ".\src\Person16Kc.txt"};
// Define an ArrayLst to hold the list of Persons
ArrayList<Person> personList = new ArrayList<Person>();
// Start sorting the small random file with each sort and print the results
String fileName = PERSON_FILE32;
System.out.println("Sorting the 32 item array using each of five algorithms");
System.out.println("======================================================");
System.out.println();
sort (personList, fileName);
printList = false;
// Sort randomly generated array list of Persons
for (int file = 0; file < 5; file++)
{
fileName = random[file];
System.out.println();
System.out.println ("ArrayLists with Persons Randomly Located");
System.out.println ("Sorting the " + size[file] + " item array using each of five algorithms");
System.out.println ("=======================================================");
System.out.println();
// Sort the list using 6 methods
sort (personList, fileName);
}
// Sort sorted array list of Persons
for (int file = 0; file < 5; file++)
{
fileName = sorted[file];
System.out.println();
System.out.println ("ArrayLists with Persons Sorted");
System.out.println ("Sorting the " + size[file] + " item array using each of five algorithms");
System.out.println ("=======================================================");
System.out.println();
// Sort the list using 6 methods
sort (personList, fileName);
}
// Sort reverse sorted array list of Persons
for (int file = 0; file < 5; file++)
{
fileName = revsorted[file];
System.out.println();
System.out.println ("ArrayLists with Persons Reverse Sorted");
System.out.println ("Sorting the " + size[file] + " item array using each of five algorithms");
System.out.println ("=======================================================");
System.out.println();
// Sort the list using 6 methods
sort (personList, fileName);
}
}
/**
* Populates a list of Persons from a file
*
* @param list
*/
public static void populate (ArrayList<Person> list, String fileName) throws Exception
{
list.clear();
numCompares = 0;
File file = new File (fileName);
Scanner fin = new Scanner (file);
String name = "";
int month, day, year;
while (fin.hasNext())
{
name = fin.next();
month = fin.nextInt();
day = fin.nextInt();
year = fin.nextInt();
list.add (new Person (name, year, month, day));
}
fin.close();
}
/**
* Prints the list of Persons
*
* @param list
*/
public static void print (ArrayList<Person> list)
{
if (printList)
{
for (Person p : list)
{
System.out.println (p.toString() + " ");
}
System.out.println ();
}
}
/**
* Calls all five types of sorts
*
* @param list
*/
public static void sort (ArrayList<Person> list, String fileName) throws Exception
{
// Call selection sort
populate (list, fileName);
selectionSort(list);
System.out.println ("Selection Sort");
System.out.println ("The number of compares: " + numCompares + " ");
print (list);
// Call insertion sort
populate (list, fileName);
insertionSort(list);
System.out.println ("Insertion Sort");
System.out.println ("The number of compares: " + numCompares + " ");
print (list);
// Call quick sort
populate (list, fileName);
quickSort(list);
System.out.println("Quick Sort");
System.out.println("The number of compares: " + numCompares + " ");
print(list);
// Call merge sort
populate (list, fileName);
mergeSort(list);
System.out.println ("Merge Sort");
System.out.println ("The number of compares: " + numCompares + " ");
print (list);
// Call heap sort
populate (list, fileName);
heapSort(list);
System.out.println("Heap Sort");
System.out.println ("The number of compares: " + numCompares + " ");
print (list);
}
/**
* Sorts a list of Persons using selection sort
*
* @param list
*/
public static void selectionSort (ArrayList<Person> list)
{
// Provide this code from Lab3: add in numCompares
}
/**
* Sorts a list of Persons using insertion sort
*
* @param list
*/
public static void insertionSort (ArrayList<Person> list)
{
// Provide this code from Lab3: add in numCompares
}
/**
* Sorts a list of Persons using merge sort
*
* @param list
*/
public static void mergeSort (ArrayList<Person> list)
{
// Provide this code
}
/**
* Merge two sorted lists
*
* @param list1
* @param list2
* @param temp
*/
public static void merge (ArrayList<Person> list1, ArrayList<Person> list2, ArrayList<Person> temp)
{
// Provide this code and add in numCompares
}
/**
* QuickSort start method
*
* @param list
*/
public static void quickSort(ArrayList<Person> list)
{
quickSort(list, 0, list.size() - 1);
}
/**
* QuickSort recursive method
*
* @param list
* @param start
* @param end
*/
private static void quickSort (ArrayList<Person> list, int start, int end)
{
// Provide this code
}
/**
* Partition the array list[start..lend]
*
* @param list
* @param start
* @param end
*/
private static int partition (ArrayList<Person> list, int start, int end)
{
// Provide this code and add in numCompares
}
/**
* Heap sort method
*
* @param list
*/
public static void heapSort (ArrayList<Person> list)
{
Heap<Person> heap = new Heap<Person>();
// Add elements to the heap
for (int i = 0; i < list.size(); i++)
{
heap.add (list.get (i));
}
// Remove elements from the heap
for (int i = list.size() - 1; i >= 0; i--)
{
list.set (i, heap.remove());
}
numCompares = heap.getNumCompares();
}
}
............................................................................
public class Person implements Comparable<Person>
{
private String name;
private MyDate birthday;
public Person (String name, int year, int month, int day)
{
this.name = name;
this.birthday = new MyDate (year, month, day);
}
@Override
public int compareTo (Person p)
{
int comp = birthday.compareTo (p.birthday);
if (comp == 0)
{
comp = name.compareTo (p.name);
}
return comp;
}
@Override
public String toString()
{
return (name + ": " + this.birthday.toString() + " ");
}
}
...................................................................................
public class MyDate implements Comparable <MyDate>
{
private int year;
private int month;
private int day;
public MyDate (int year, int month, int day)
{
this.year = year;
this.month = month;
this.day = day;
}
@Override
public int compareTo (MyDate d)
{
int comp = 0;
if (year > d.year)
{
comp = 1;
}
else if (year < d.year)
{
comp = -1;
}
else
{
if (month > d.month)
{
comp = 1;
}
else if (month < d.month)
{
comp = -1;
}
else
{
if (day > d.day)
{
comp = 1;
}
else if (day < d.day)
{
comp = -1;
}
}
}
return comp;
}
@Override
public String toString()
{
return month + "-" + day + "-" + year ;
}
}
....................................................................
import java.util.ArrayList;
public class Heap<E extends Comparable<E>>
{
private ArrayList<E> list = new ArrayList<>();
private int numCompares;
/**
* Create a default heap
*/
public Heap()
{
numCompares = 0;
}
/**
* Create a heap from an array of objects
* @param objects
* */
public Heap (E[] objects)
{
numCompares = 0;
for (int i = 0; i < objects.length; i++)
{
add (objects[i]);
}
}
/**
* Add a new object into the heap
* Return the number of compares
*/
public int add (E newObject)
{
list.add (newObject); // Append to the heap
int currentInd = list.size()-1; // last node
while (currentInd > 0)
{
int parentInd = (currentInd - 1) / 2;
numCompares++;
if (list.get (currentInd).compareTo (list.get (parentInd)) > 0)
{
// Swap when current > parent
E temp = list.get (currentInd);
list.set (currentInd, list.get (parentInd));
list.set (parentInd, temp);
}
else
break; // the tree is a heap now
currentInd = parentInd;
}
return numCompares;
}
/** Remove the root from the heap */
public E remove()
{
if (list.size() == 0) return null;
E removedObject = list.get (0);
list.set (0, list.get (list.size() - 1));
list.remove (list.size() - 1);
int currentInd = 0;
while (currentInd < list.size())
{
int ltChildInd = 2 * currentInd + 1;
int rtChildInd = 2 * currentInd + 2;
if (ltChildInd >= list.size()) break;
int maxInd = ltChildInd;
if (rtChildInd < list.size())
{
numCompares++;
if (list.get (maxInd).compareTo (list.get (rtChildInd)) < 0)
{
maxInd = rtChildInd;
}
}
// Swap if current < max
numCompares++;
if (list.get (currentInd).compareTo (list.get (maxInd)) < 0)
{
E temp = list.get (maxInd);
list.set (maxInd, list.get (currentInd));
list.set (currentInd, temp);
currentInd = maxInd;
}
else
break; // The tree is a heap
}
return removedObject;
}
/**
* Get the number of nodes in the tree
* @return int
*/
public int getSize()
{
return list.size();
}
/**
* Get the number of compares
* @return int
*/
public int getNumCompares()
{
return numCompares;
}
}
Explanation / Answer
import java.util.*;
import java.io.*;
public class PersonSort {
private static int numCompares = 0;
private static boolean printList = true;
public static void main(String[] args) throws Exception {
// File name for testing the algorithms
final String PERSON_FILE32 = ".\src\Person32.txt";
// ArrayList size array for printing
String[] size = { "1K", "2K", "4K", "8K", "16K" };
// This set of files are for determining the running time of sorting randomized Persons
String[] random = { ".\src\Person1Ka.txt", ".\src\Person2Ka.txt", ".\src\Person4Ka.txt",
".\src\Person8Ka.txt", ".\src\Person16Ka.txt" };
// This set of files are for determining the running time of sorting sorted Persons
String[] sorted = { ".\src\Person1Kb.txt", ".\src\Person2Kb.txt", ".\src\Person4Kb.txt",
".\src\Person8Kb.txt", ".\src\Person16Kb.txt" };
// This set of files are for determining the running time of sorting sorted Persons
String[] revsorted = { ".\src\Person1Kc.txt", ".\src\Person2Kc.txt", ".\src\Person4Kc.txt",
".\src\Person8Kc.txt", ".\src\Person16Kc.txt" };
// Define an ArrayLst to hold the list of Persons
ArrayList<Person> personList = new ArrayList<Person>();
// Start sorting the small random file with each sort and print the results
String fileName = PERSON_FILE32;
System.out.println("Sorting the 32 item array using each of five algorithms");
System.out.println("======================================================");
System.out.println();
sort(personList, fileName);
printList = false;
// Sort randomly generated array list of Persons
for (int file = 0; file < 5; file++) {
fileName = random[file];
System.out.println();
System.out.println("ArrayLists with Persons Randomly Located");
System.out.println("Sorting the " + size[file] + " item array using each of five algorithms");
System.out.println("=======================================================");
System.out.println();
// Sort the list using 6 methods
sort(personList, fileName);
}
// Sort sorted array list of Persons
for (int file = 0; file < 5; file++) {
fileName = sorted[file];
System.out.println();
System.out.println("ArrayLists with Persons Sorted");
System.out.println("Sorting the " + size[file] + " item array using each of five algorithms");
System.out.println("=======================================================");
System.out.println();
// Sort the list using 6 methods
sort(personList, fileName);
}
// Sort reverse sorted array list of Persons
for (int file = 0; file < 5; file++) {
fileName = revsorted[file];
System.out.println();
System.out.println("ArrayLists with Persons Reverse Sorted");
System.out.println("Sorting the " + size[file] + " item array using each of five algorithms");
System.out.println("=======================================================");
System.out.println();
// Sort the list using 6 methods
sort(personList, fileName);
}
}
/**
* Populates a list of Persons from a file
*
* @param list
*/
public static void populate(ArrayList<Person> list, String fileName) throws Exception {
list.clear();
numCompares = 0;
File file = new File(fileName);
Scanner fin = new Scanner(file);
String name = "";
int month, day, year;
while (fin.hasNext()) {
name = fin.next();
month = fin.nextInt();
day = fin.nextInt();
year = fin.nextInt();
list.add(new Person(name, year, month, day));
}
fin.close();
}
/**
* Prints the list of Persons
*
* @param list
*/
public static void print(ArrayList<Person> list) {
if (printList) {
for (Person p : list) {
System.out.println(p.toString() + " ");
}
System.out.println();
}
}
/**
* Calls all five types of sorts
*
* @param list
*/
public static void sort(ArrayList<Person> list, String fileName) throws Exception {
// Call selection sort
populate(list, fileName);
selectionSort(list);
System.out.println("Selection Sort");
System.out.println("The number of compares: " + numCompares + " ");
print(list);
// Call insertion sort
populate(list, fileName);
insertionSort(list);
System.out.println("Insertion Sort");
System.out.println("The number of compares: " + numCompares + " ");
print(list);
// Call quick sort
populate(list, fileName);
quickSort(list);
System.out.println("Quick Sort");
System.out.println("The number of compares: " + numCompares + " ");
print(list);
// Call merge sort
populate(list, fileName);
mergeSort(list);
System.out.println("Merge Sort");
System.out.println("The number of compares: " + numCompares + " ");
print(list);
// Call heap sort
populate(list, fileName);
heapSort(list);
System.out.println("Heap Sort");
System.out.println("The number of compares: " + numCompares + " ");
print(list);
}
/**
* Sorts a list of Persons using selection sort
*
* @param list
*/
public static void selectionSort(ArrayList<Person> list) {
// Provide this code from Lab3: add in numCompares
for (int i = 0; i < list.size(); i++) {
for (int j = i; j < list.size(); j++) {
numCompares++;
if (list.get(i).name > list.get(i).name) {
Person p = list.get(i);
list.set(i, list.get(j));
list.set(j, p);
}
}
}
}
/**
* Sorts a list of Persons using insertion sort
*
* @param list
*/
public static void insertionSort(ArrayList<Person> list) {
// Provide this code from Lab3: add in numCompares
int n = list.length;
for (int i = 1; i < n; ++i) {
Person temp = list.get(i);
int j = i - 1;
numCompares++;
while (j >= 0 && list.get(j).name > temp.name) {
list.set(j + 1, list.get(j));
j = j - 1;
}
list.set(j + 1, temp);
}
}
/**
* Sorts a list of Persons using merge sort
*
* @param list
*/
public static void mergeSort(ArrayList<Person> list) {
// Provide this code
if (list == null) {
return;
}
if (list.size() > 1) {
int mid = list.size() / 2;
// Split left part
Person[] left = new Person[mid];
for (int i = 0; i < mid; i++) {
left[i] = list[i];
}
// Split right part
Person[] right = new Person[list.size() - mid];
for (int i = mid; i < list.size(); i++) {
right[i - mid] = list[i];
}
mergeSort(left);
mergeSort(right);
int i = 0;
int j = 0;
int k = 0;
// Merge left and right arrays
while (i < left.size() && j < right.size()) {
numCompares++;
if (left[i].name < right[j].name) {
list[k] = left[i];
i++;
} else {
list[k] = right[j];
j++;
}
k++;
}
// Collect remaining elements
while (i < left.size()) {
list[k] = left[i];
i++;
k++;
}
while (j < right.length) {
list[k] = right[j];
j++;
k++;
}
}
}
/**
* Merge two sorted lists
*
* @param list1
* @param list2
* @param temp
*/
public static void merge(ArrayList<Person> list1, ArrayList<Person> list2, ArrayList<Person> temp) {
// Provide this code and add in numCompares
int i = 0, j = 0, k = 0, n1 = list1.size(), n2 = list2.size();
// Traverse both array
while (i < n1 && j < n2) {
if (list1.get(i) < list2.get(j))
temp.set(k++, list1.get(i++));
else
temp.set(k++, list2.get(j++));
}
// Store remaining elements of first array
while (i < n1)
temp.set(k++, list1.get(i++));
// Store remaining elements of second array
while (j < n2)
temp.get(k++, list2.get(j++));
}
/**
* QuickSort start method
*
* @param list
*/
public static void quickSort(ArrayList<Person> list) {
quickSort(list, 0, list.size() - 1);
}
/**
* QuickSort recursive method
*
* @param list
* @param start
* @param end
*/
private static void quickSort(ArrayList<Person> list, int start, int end) {
numCompares++;
if (start < end) {
int pi = partition(list, start, end);
sort(list, start, pi - 1);
sort(list, pi + 1, end);
}
}
/**
* Partition the array list[start..lend]
*
* @param list
* @param start
* @param end
*/
private static int partition(ArrayList<Person> list, int start, int end) {
Person pivot = list.get(end);
int i = (start - 1); // index of smaller element
for (int j = start; j < end; j++) {
numCompares++;
if (list.get(j).name <= pivot.name) {
i++;
Person temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}
// swap arr[i+1] and arr[high] (or pivot)
Person temp = list.get(i + 1);
list.set(i + 1, list.get(end));
list.set(end, temp);
return i + 1;
}
/**
* Heap sort method
*
* @param list
*/
public static void heapSort(ArrayList<Person> list) {
Heap<Person> heap = new Heap<Person>();
// Add elements to the heap
for (int i = 0; i < list.size(); i++) {
heap.add(list.get(i));
}
// Remove elements from the heap
for (int i = list.size() - 1; i >= 0; i--) {
list.set(i, heap.remove());
}
numCompares = heap.getNumCompares();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.