Help with this Java Program,The error Im having is at the end of PersonSort in t

Question

Help with this Java Program,The error Im having is at the end of PersonSort in the loops/if statment.. code posted below:

Heap CLass:

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;
}
}

My Date:

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 ;
}
}

Person Class:

public class Person implements Comparable<Person>
{
private String name;
private MyDate birthday;
private int id;

public int getId()
{
return id;
}

public void setId(int id)
{
this.id=id;
}

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() + " ");
}
}

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

for (int i = 0; i < list.size() - 1; i++) {

int index = i;

int j = i + 1;

while (j < list.size()) {

if (list.get(j).compareTo(list.get(index)) < 0) {

index = j;

}

j++;

}

// swap index i with j

Person smaller = list.get(index);

list.set(index, list.get(i));

list.set(i, smaller);

}

}

/**

* 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

for (int i = 1; i < list.size(); i++) {

Person valueToSort = list.get(i);

int j = i;

while (j > 0 && list.get(j - 1).compareTo(valueToSort) > 0) {

list.set(j, list.get(j - 1));

j--;

}

list.set(j, valueToSort);

}

}

/**

* Sorts a list of Persons using merge sort

*

* @param list

*/

public static void mergeSort(ArrayList<Person> list) {

// Provide this code

if (list.size() > 1) {

// Merge sort the first half

ArrayList<Person> firstHalf = new ArrayList<>(list.size() / 2);

System.arraycopy(list, 0, firstHalf, 0, list.size() / 2);

mergeSort(firstHalf);

// Merge sort the second half

int secondHalfLength = list.size() - list.size() / 2;

ArrayList<Person> secondHalf = new ArrayList<>(secondHalfLength);

System.arraycopy(list, list.size() / 2, secondHalf, 0, secondHalfLength);

mergeSort(secondHalf);

// Merge firstHalf with secondHalf into list

merge(firstHalf, secondHalf, list);

}

}

/**

* 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 current1 = 0; // Current index in list1

int current2 = 0; // Current index in list2

int current3 = 0; // Current index in temp

while (current1 < list1.size() && current2 < list2.size()) {

if (list1.get(current1).getId() < list2.get(current2).getId())

temp.add(list1.get(current1++));

else

temp.add(list2.get(current2++));

}

while (current1 < list1.size()) {

temp.add(list1.get(current1++));

}

while (current2 < list2.size()) {

temp.add(list2.get(current2++));

}

}

/**

* 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

if (end > start) {

int pivotIndex = partition(list, start, end);

quickSort(list, start, pivotIndex - 1);

quickSort(list, pivotIndex + 1, end);

}

}

/**

* Partition the array list[start..lend]

*

* @param list

* @param start

* @param end

*/

*******************Error located here, the "list" in the comparing if statements causes an error**********************************

private static int partition(ArrayList<Person> list, int start, int end) {

// Provide this code and add in numCompares

Person pivot = list.get(start); // First element is the pivot

int low = start + 1; // Index for forward search

int high = end; // Index for backward search

while (high > low) {

while (low <= high && list(low) <= pivot) {

low++; // Search forward from left

}

while (low <= high && list(high) > pivot) {

high--; // Search backward from right

}

if (high > low) // Swap two elements in the list

{

Person temp = list.get(high);

list.set(high,list.get(low));

list.set(low,temp);

}

}

while (high > start && list(high) >= pivot) {

high--;

}

// Swap pivot with list[high]

if (pivot > list(high)) {

list.set(start,list.get(high));

list.set(high,pivot);

return high;

} else {

return start;

}

}

/**

* 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();

}

}

Explanation / Answer

The error was actually, you were not retrieving element from the list properly. "list" variable is an arraylist and you cannot access an element from list in the form list(high). you need to access with the syntax list.get(high).

I have corrected your code. the error was only in PersonSort.java , so I am posting only that. I was not able to execute the code, as text file is missing. Please comment if you have any issues in this.

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() - 1; i++) {

int index = i;

int j = i + 1;

while (j < list.size()) {

if (list.get(j).compareTo(list.get(index)) < 0) {

index = j;

}

j++;

}

// swap index i with j

Person smaller = list.get(index);

list.set(index, list.get(i));

list.set(i, smaller);

}

}

/**

*

* 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

for (int i = 1; i < list.size(); i++) {

Person valueToSort = list.get(i);

int j = i;

while (j > 0 && list.get(j - 1).compareTo(valueToSort) > 0) {

list.set(j, list.get(j - 1));

j--;

}

list.set(j, valueToSort);

}

}

/**

*

* Sorts a list of Persons using merge sort

*

*

*

* @param list

*

*/

public static void mergeSort(ArrayList<Person> list) {

// Provide this code

if (list.size() > 1) {

// Merge sort the first half

ArrayList<Person> firstHalf = new ArrayList<>(list.size() / 2);

System.arraycopy(list, 0, firstHalf, 0, list.size() / 2);

mergeSort(firstHalf);

// Merge sort the second half

int secondHalfLength = list.size() - list.size() / 2;

ArrayList<Person> secondHalf = new ArrayList<>(secondHalfLength);

System.arraycopy(list, list.size() / 2, secondHalf, 0, secondHalfLength);

mergeSort(secondHalf);

// Merge firstHalf with secondHalf into list

merge(firstHalf, secondHalf, list);

}

}

/**

*

* 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 current1 = 0; // Current index in list1

int current2 = 0; // Current index in list2

int current3 = 0; // Current index in temp

while (current1 < list1.size() && current2 < list2.size()) {

if (list1.get(current1).getId() < list2.get(current2).getId())

temp.add(list1.get(current1++));

else

temp.add(list2.get(current2++));

}

while (current1 < list1.size()) {

temp.add(list1.get(current1++));

}

while (current2 < list2.size()) {

temp.add(list2.get(current2++));

}

}

/**

*

* 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

if (end > start) {

int pivotIndex = partition(list, start, end);

quickSort(list, start, pivotIndex - 1);

quickSort(list, pivotIndex + 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) {

// Provide this code and add in numCompares

Person pivot = list.get(start); // First element is the pivot

int low = start + 1; // Index for forward search

int high = end; // Index for backward search

while (high > low) {

while (low <= high && list.get(low).compareTo(pivot) <= 0) {

low++; // Search forward from left

}

while (low <= high && list.get(high).compareTo(pivot) > 0) {

high--; // Search backward from right

}

if (high > low) // Swap two elements in the list

{

Person temp = list.get(high);

list.set(high, list.get(low));

list.set(low, temp);

}

}

while (high > start && list.get(high).compareTo(pivot) >= 0) {

high--;

}

// Swap pivot with list[high]

if (pivot.compareTo(list.get(high)) > 0) {

list.set(start, list.get(high));

list.set(high, pivot);

return high;

} else {

return start;

}

}

/**

*

* 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

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.