Javaを使用してヒープソートを実装するタスクが与えられました。ソートは年俸で行われますが、オブジェクトの従業員は名前の文字列と給与の int の両方を受け入れます。基本的に同じクラスでバブルソートに成功しましたが、ヒープソートに問題があります。これが私のコードです：
import java.util.ArrayList;
import java.util.Scanner;
public class Company {
//create a default heap using array list
private ArrayList<Employee> list = new ArrayList<Employee>();
/* Add a new object into the binary heap */
//building a heap
public void addEmployee(Employee employee) {
list.add(employee); //append to the heap
}
public Employee remove() {
int count = 0;
if (list.isEmpty())
return null;
Employee removedObject = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while (currentIndex < list.size()) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
// find the maximum between the two children
if (leftChildIndex >= list.size())
break; // the tree is a heap
int maxIndex = leftChildIndex;
if (rightChildIndex < list.size()) {
if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0) {
maxIndex = rightChildIndex;
count++;
}
}
// swap if the current node is less than the maximum
if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
Employee temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
count++;
}
else
break;
}
// This is what I changed.
//list.add(0, removedObject);
//count++;
System.out.println(count);
return removedObject;
}
/*
* Method to print all elements in the ArrayList
*/
public void listEmployees(){
for (Employee employee : list)
System.out.println(employee.toString());
System.out.println();
}
public void listEmployeesSorted() {
ArrayList<Employee> copy = new ArrayList<Employee>(list);
StringBuilder builder = new StringBuilder();
while (list.size()>0) {
Employee e = this.remove();
builder.append(e.toString()+"\n");
}
this.list = copy;
System.out.println(builder.toString());
}
public static void main(String[] args) {
/*
* Instantiate object and call it 'direct'
*/
Company direct = new Company();
Scanner input=new Scanner(System.in);//Scanner Declaration
String name;
int salary;
/*
* Enter all the employee data
*/
direct.addEmployee(new EmployeeImp("John Hughes",36100));
direct.addEmployee(new EmployeeImp("Stephen Hughes",22100));
direct.addEmployee(new EmployeeImp("Michael Smith", 0));
direct.addEmployee(new EmployeeImp("Ludmilia Petrushevskaya", 120120));
direct.addEmployee(new EmployeeImp("Amy Gu", 36100));
direct.addEmployee(new EmployeeImp("Marta Villanueva Cortez", 34020));
direct.addEmployee(new EmployeeImp("Ian Palmer-Jones", 23090));
direct.addEmployee(new EmployeeImp("Andrew Andrews", 220100));
direct.addEmployee(new EmployeeImp("Andy Rainsford", 67000));
direct.addEmployee(new EmployeeImp("Bob Bobsworth", 23000));
direct.addEmployee(new EmployeeImp("Paul Smith", 29000));
direct.addEmployee(new EmployeeImp("James James", 23023));
direct.addEmployee(new EmployeeImp("Henry Cooper", 33900));
direct.addEmployee(new EmployeeImp("Ian Paisley", 33901));
direct.addEmployee(new EmployeeImp("Alan Ball", 45000));
direct.addEmployee(new EmployeeImp("Mick Channon", 55600));
direct.addEmployee(new EmployeeImp("Paul Halibut", 26780));
direct.addEmployee(new EmployeeImp("Raj Patel", 33090));
direct.addEmployee(new EmployeeImp("Mary James", 23000));
direct.addEmployee(new EmployeeImp("Alison Frogget", 78100));
direct.addEmployee(new EmployeeImp("Jenny Eclair", 40000));
direct.addEmployee(new EmployeeImp("Sasha Lane", 21000));
direct.addEmployee(new EmployeeImp("Sarah Milligan", 100300));
direct.addEmployee(new EmployeeImp("Zico", 120000));
direct.addEmployee(new EmployeeImp("Pippa Forester", 90000));
direct.addEmployee(new EmployeeImp("Angela Landsdowne", 8000));
direct.addEmployee(new EmployeeImp("Emily Taxem", -1000));
direct.addEmployee(new EmployeeImp("Jill Beans", 654000));
direct.addEmployee(new EmployeeImp("Alan Salt", 33333));
direct.addEmployee(new EmployeeImp("Imran Khan", 87000));
direct.addEmployee(new EmployeeImp("Matt Demon", 66666));
direct.addEmployee(new EmployeeImp("Douglas Adams", 42000));
System.out.println("\tName\t\t Salary");
direct.listEmployees();//print out all elements in ArrayList before sorting
System.out.println("\tName\t\t Salary");
System.out.println("__________________________________________________");
direct.listEmployeesSorted();//print out all elements in ArrayList after sorting
/*
* Use scanner to get user input (name,salary) to be entered into
* the existing sorted list
*/
System.out.print("Please enter a new employee's name: ");
name=input.nextLine();
System.out.print("Please enter the employee's associated salary: ");
salary=input.nextInt();
direct.addEmployee(new EmployeeImp(name,salary));
direct.listEmployeesSorted();
}//end main
}//end class Company
少数のデータの場合はうまくソートされますが、負の数または0、または通常の正の値を追加し始めると、ソート全体が狂ってしまいます。誰かがこれを修正するのを手伝ってくれるかどうか疑問に思っていました。実際、問題を引き起こしているのはヒープソートメソッドの実装であることを知っています。他のすべては問題ないはずです...笑...助けてください
これは従業員クラスです。
public abstract class Employee implements Comparable<Employee>{
private String name;
private int salary;
/*
* Two-Arguement Constructor
*/
Employee(String name, int salary){
this.name = name;
this.salary = salary;
}//end method
public int getSalary(){
return salary;
}//end method
/*
* Return the employee's name
*/
public String getName(){
return name;
}//end method
/*
* Return the compareTo
*/
public int compareTo(Employee x){
if (this.salary < x.salary)
return -1;
else if (this.salary > x.salary)
return 1;
else
return 0;
}//end method
public String toString(){
StringBuffer buffer = new StringBuffer();
buffer.append("\t");
buffer.append(getName());
buffer.append("\t ");
buffer.append(getSalary());
buffer.append("\t ");
return buffer.toString();
}
}
これは、employee を実装するサブクラスです。
class EmployeeImp extends Employee{
EmployeeImp(String name, int salary) {
super(name, salary);
}
}
