Need Java help with PersonSort class: import java.util.*; import java.io.*; publ
ID: 3715192 • 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
I've implemented the "to provide" functions here. Please have a check and let me know if there is anything not clear.
public static void selectionSort(ArrayList<Person> list)
{
int start = 0, end = list.size();
numCompares = 0;
for(int i=start; i<end-1; i++){
int minIndex = i;
for(int j=i+1; j<n; j++) {
numCompares++;
if (list.get(minIndex).compareTo(list.get(j)) > 0) {
minIndex = j;
}
// swap the min element with the first element
Person temp = list.get(i);
list.set(i, list.get(minIndex));
list.set(minIndex, temp);
}
}
public static void insertionSort(ArrayList<Person> list)
{
numCompares = 0;
for (int i=1; i<n; i++){
Person personToInsert = list.get(i);
for(int j=i-1; j>=0; j--){
numCompares++;
if (list.get(j).compareTo(personToInsert) > 0){
// swap the min element with the first element
Person temp = list.get(j);
list.set(j, personToInsert);
list.set(i, temp);
} else break;
}
}
}
public static void quickSort(ArrayList<Person> list, int start, int end)
{
numCompares=0;
if (start < end)
{
// partioning
pivot = partition(list, start, end);
quickSort(list, start, pivot-1);
quickSort(list, pivot+1, end);
}
}
public static int partition(ArrayList<Person> list, int start, int end)
{
// pivot
int pivotIndex = start+(end-start)/2;
pivot = list.get(pivotIndex);
while(start<=end){
while(pivot.compareTo(list.get(start)) > 0){
numCompares++;
start++;
}
numCompares++;
while(pivot.compareTo(list.get(end)) < 0){
numCompares++;
end--;
}
numCompares++;
if(start<=end) {
// swap
Person temp = list.get(start);
list.set(start, list.get(end));
list.set(end, temp);
}
}
return pivotIndex;
}
public static void mergeSort(ArrayList<Person> list)
{
numCompares = 0;
int left = 0, right = list.size()-1;
if (left < right)
{
int medium = left + (right-left)/2;
ArrayList<Person> list1 = new ArrayList<Person>();
// populate the left half of the list into the list1
for (int i=0; i<medium; i++) {
list1.add(list.get(i));
}
ArrayList<Person> list2 = new ArrayList<Person>();
// populate the right half of the list into the list2
for (int i=medium; i<list.size(); i--) {
list2.add(list.get(i));
}
// sort both the lists separately
mergeSort(list1);
mergeSort(list2);
// merge the two sorted lists into list
merge(list1, list2, list);
}
}
public static void merge(ArrayList<Person> list1, ArrayList<Person> list2, ArrayList<Person> temp)
{
int list1Index = 0, list2Index =0, tempIndex=0;
while (list1Index<list1.size() && list2Index<list2.size()){
numCompares++;
if(list1.get(list1Index).compareTo(list2.get(list2Index))) < 0) {
temp.set(tempIndex, list1.get(list1Index));
list1Index++;
}
else {
temp.set(tempIndex, list2.get(list2Index));
list2Index++;
}
tempIndex++;
}
ArrayList<Person> remaining;
int remainIndex;
if (list1Index >= list1.size()) {
// copy the list2
for (int i=list2Index;i<list2.size();i++) {
temp.set(tempIndex, list2.get(list2Index));
tempIndex++;
}
} else {
// copy the list1
for (int i=list1Index;i<list1.size();i++) {
temp.set(tempIndex, list1.get(list1Index));
tempIndex++;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.