John Casey John Casey - 3 years ago 190
Java Question

Implement a generic Java method using an O(n^2 ) sort and a comparator

Implement the following generic Java method using an O(n^2) sort and a comparator:

public static <E> void aSort(E[] list, Comparator<? super E> comparator)




Write test program that creates a list of at least 5 elements of the class type created in problem 3
above, calls the above method to sort the list, then outputs the sorted list via calls to toString.



Unsorted:
A Circle with the radius of: [1]
A Circle with the radius of: [15]
A Circle with the radius of: [10]
A Circle with the radius of: [12]
A Circle with the radius of: [100]


I don't know why it's printing this backwards but it is supposed to sort in ascending order

Sorted:
A Circle with the radius of: [100]
A Circle with the radius of: [12]
A Circle with the radius of: [10]
A Circle with the radius of: [15]
A Circle with the radius of: [1]


This is what I got so far

public static void main(String[] args) {

Circle c1 = new Circle();
Circle c2 = new Circle(15);
Circle c3 = new Circle(10);
Circle c4 = new Circle(12);
Circle c5 = new Circle(100);

Circle w[] = new Circle[5];
w[0] = c1;
w[1] = c2;
w[2] = c3;
w[3] = c4;
w[4] = c5;

CompareCircle cc = new CompareCircle();
System.out.println("Unsorted: ");
for (Circle go : w) {
System.out.println(go.toString());
}

bubbleSort(w, new CompareCircle());
System.out.println();
System.out.println("Sorted: ");
for (int i = 0; i < w.length; i++) {
System.out.println(w[i].toString());

}
public static <E> void bubbleSort(E[] list, Comparator<? super E> comparator) {
boolean needNextPass = true;

for (int k = 1; k < list.length && needNextPass; k++) {
// Array may be sorted and next pass not needed
needNextPass = false;
for (int i = 0; i < list.length - k; i++) {
if (comparator.compare(list[i], list[i + 1]) > 0) {
// Swap list[i] with list[i + 1]
E temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;

needNextPass = true; // Next pass still needed
}
}
}

}

}




This is my Circle class



import java.io.Serializable;
import java.util.Comparator;

public class Circle implements Serializable {

private int radius = 1;

public Circle() {
}

public Circle(int radius) {
setRadius(radius);

}

public void setRadius(int v) {
if (v > 0) {
this.radius = v;
}

}

public int getRadius() {
return this.radius;

}

@Override
public String toString() {
return "A Circle with the radius of: [" + radius + "]";
}


}




This is my CompareCircle class



import java.util.Comparator;

public class CompareCircle implements Comparator<Circle> {

@Override
public int compare(Circle o1, Circle o2) {
int radius1 = o1.getRadius();
int radius2 = o2.getRadius();

if (radius1 < radius2){
return radius2;
}
if (radius1 == radius2){
return radius1;
}
else
return radius1;
}

}

Answer Source

Your implementation of bubbleSort is perfectly fine. CircleComparator on the other hand is seriously malformed. No matter which Circles will be passed it will always return a positive integer. Thus in run n the first element will be "bubbled" up to index list.length - n, and all remaining elements (index <= list.length - n) will be pushed one index down, which in the end results in the list being reversed.

A correct comparison-function would return a negative number if the first value is smaller, a positive number if the second value is smaller, and 0 if the parameters are equal (see the documentation). E.g.:

public class CircleCompare implements Comparator<Circle>
{
    public int compare(Circle c1, Circle c2){
        return Integer.compare(c1.getRadius(), c2.getRadius());
    }
}

Or as an alternative way if you prefer doing the logic yourself:

public class CircleCompare implements Comparator<Circle>
{
    public int compare(Circle c1, Circle c2){
        return c2.getRadius() - c1.getRadius();
    }
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download