Demonstrate Big-O for the Oracle Java API Collections.sort(). Use the System clo

Question

Demonstrate Big-O for the Oracle Java API Collections.sort().

Use the System clock (milliseconds) or equivalent way to count operations and assess the run-time complexity, O(N), O(N^2), O(1)??? for Collections.sort(). Create an Excel workbook of your results, and clearly indicate your answer for Big-O. Your chart should have a title, label axes, a line that proposes your answer, and appropriate scales from zero to whatever is large enough to encompass your data. Everyone will have different data, but we might all come to the same Big-O conclusion that Collections.sort is O??? You will likely start with some preliminary results, often getting slightly different results, something like Preliminary.JPGView in a new window In the end you will clean things up and get a more polished final chart that displays on the first worksheet along with your data FinalEst.JPGView in a new window Hints: Your Collection must be large enough so sorting takes at least ideally one or two seconds. Anything higher (like minutes to hours for sorting) will likely be timing the problem of virtual memory instead of Big-O algorithm processing.

Submit 2 files here: 1. your Testing.java program, and 2. your Excel workbook.

Explanation / Answer

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;
import java.jxl.*;

class Employee implements Comparable {
private String name;

private double salary;

Employee(String name, double salary) {
this.name = name;
this.salary = salary;
}

String getName() {
return name;
}

double getSalary() {
return salary;
}

public String toString() {
return "Name = " + getName() + ", Salary = " + getSalary();
}

public int compareTo(Object o) {
if (!(o instanceof Employee))
throw new ClassCastException();

Employee e = (Employee) o;

return name.compareTo(e.getName());
}

static class SalaryComparator implements Comparator {
public int compare(Object o1, Object o2) {
if (!(o1 instanceof Employee) || !(o2 instanceof Employee))
throw new ClassCastException();

Employee e1 = (Employee) o1;
Employee e2 = (Employee) o2;

return (int) (e1.getSalary() - e2.getSalary());
}
}
}

class ArraySortExample {
public static void main(String[] args) {

try {
String fileName = "file.xls";
WritableWorkbook workbook = Workbook.createWorkbook(new File(fileName));
workbook.createSheet("Sheet1", 0);
workbook.createSheet("Sheet2", 1);
workbook.createSheet("Sheet3", 2);
workbook.write();
workbook.close();
} catch (WriteException e) {

}

long startTime = System.nanoTime();
//code
String[] names = { "A", "B", "C", "D" };

double[] salaries = { 2.0, 5.0, 6.0, 4.0 };

List l = new ArrayList();

for (int i = 0; i < names.length; i++)
l.add(new Employee(names[i], salaries[i]));

Collections.sort(l);

ListIterator liter = l.listIterator();

while (liter.hasNext())
System.out.println(liter.next());

Collections.sort(l, new Employee.SalaryComparator());

System.out.println("After Sorting");

liter = l.listIterator();

while (liter.hasNext())
System.out.println(liter.next());

long endTime = System.nanoTime();
long ns=endTime-startTime;
System.out.println("Took "+(endTime - startTime) + " ns");  
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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