By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,107 Members | 1,114 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,107 IT Pros & Developers. It's quick & easy.

Circle Sorting Help!!

P: 18
Hey all,

I'm in a Java data structures class in college and I have a problem with this one sorting assignment. I'm not very experienced in java and have tried tackling this assignment in an assortment of ways but have failed miserably. Basically, here is the assignment:::

================================================== ======
"If you look in http://csis.pace.edu/~bergin/temp/circles.zip , you will find a file containing, among other things, a file named circles.arraylist. This file was created by writing an ArrayList of circle objects on an object output stream. It contains 5000 circle objects. The circle class and the main that created the circles file is also included in the zip. The data is random.

You will need to include the trials.Circle class in your project. in particular, the package must be trials and you should not modify the circle class.

Your job is to:
(a) Sort the circles by radius, smallest first
(b) Sort the circles by the red component of their color, largest first, and for those with the same red component by the blue (largest first) and if the red and blue is the same, then by green (largest first). This requires three sorts, the last two of which need to be stable. First sort by green, then blue (stable) and finally by red( stable). Note that merge sort is fast and stable. Quick sort is fast, but not stable.

Also build an adequete JUnit test to show that you have indeed sorted them as required.
================================================== =======


Im really not to sure how to go about solving this. Im not asking you guys to solve this for me, but if someone could give me a push in the right direction and tell me what to do, I would appreciate it. Please keep in mind that Im an amateur programmer, and some things you guys will probably suggest might be out of my skill range, so a slight explanation wouldnt hurt :)

Thanks in advance.
Dec 16 '07 #1
Share this Question
Share on Google+
19 Replies


Ganon11
Expert 2.5K+
P: 3,652
Have you learned how to write sorting methods and get them to work?
Dec 16 '07 #2

P: 18
I'm not perfect with them but I think I can pull it off. What do you suggest?
Dec 17 '07 #3

Ganon11
Expert 2.5K+
P: 3,652
Well, then your program basically writes itself. You have a file that contains information about however many Circles - make a method to read them into an array/ArrayList/whatever and return that list/array. Then make a method to sort them by radius size. Then make a method to sort them by color (which, according to your problem, will be several methods combined). Then make a method to print out the circles in the array/list.

Go ahead and give it a try and let us know where you get.
Dec 17 '07 #4

BigDaddyLH
Expert 100+
P: 1,216
It's not clear from your assignment, but are you expected to code your own sort, or can you use the sorting methods in the API? If so, this is assignment is only a half page of code.
Dec 17 '07 #5

P: 18
Well he said we could build our own sort programs or use something built into the java libraries to do the sorts...


But anyway, I built one of my own that sorts the circle array....but Im not really sure how to adapt it so that it sorts the circles by radius, then by the green color component, then the blue, then red. I understand you're supposed to used comparators, just not sure how to do it.

Here's my circle sorting code so far...
================================================== =======

package trials;

import java.awt.Color;
import java.awt.Point;

public class SortCircle {

public static <Circle extends Comparable<Circle>> void sort (Circle[] circles)
{
Circle currentMax;
int currentMaxIndex;

for(int i = circles.length - 1; i >= 1; i--)
{ //Find the maximum in the list [0...i]
currentMax = circles[i];
currentMaxIndex = i;

for (int j = i - 1; j >= 0; j--)
{
if (currentMax.compareTo(circles[j]) < 0){
currentMax = circles[j];
currentMaxIndex = j;
}
}

//Swap circles[i] with circles[currentMaxIndex] if necessary
if (currentMaxIndex != i){
circles[currentMaxIndex] = circles[i];
circles[i] = currentMax;
}
}
}
Dec 17 '07 #6

BigDaddyLH
Expert 100+
P: 1,216
If you can use a sorting method like java.util.Arrays.sort or java.util.Collections.sort, I would prefer it to reinventing the wheel. Here is the tutorial page on Comparators:

http://java.sun.com/docs/books/tutor...x.html#sorting
Dec 17 '07 #7

P: 18
Since I have to sort the circles in order ( By Radius first, if radius's are equal, sort by the green color component of the circles, if both greens are equal, then sort by the blue component and so forth) should I use nested If statements with sorts in each, or should I do something different?
Dec 17 '07 #8

BigDaddyLH
Expert 100+
P: 1,216
Since I have to sort the circles in order ( By Radius first, if radius's are equal, sort by the green color component of the circles, if both greens are equal, then sort by the blue component and so forth) should I use nested If statements with sorts in each, or should I do something different?
A single comparator can order by one attribute first, then break times with a second attribute. For example:

Expand|Select|Wrap|Line Numbers
  1. import java.util.Comparator;
  2.  
  3. class Person {
  4.     public String getLastName() {...}
  5.     public String getFirstName() {...}
  6.    ...
  7. }
  8.  
  9. class NameComparator implements Comparator<Person> {
  10.     public int compare(Person x, Person y) {
  11.         int result = x.getLastName().compareTo(y.getLastName());
  12.         if (result == 0) {
  13.             result = x.getFirstName().compareTo(y.getFirstName());
  14.         }
  15.         return result;
  16.     }
  17. }
Dec 17 '07 #9

P: 18
The code above is a big help, thanks dude.

Im off to class now but when Im back, I'll continue working on the code and i'll come back here if I need anymore help. Thanks everyone.
Dec 17 '07 #10

P: 18
Im still getting errors. Im trying to understand why this class wont extend the circle class (which contains the methods I need such as getRadius(), etc in order for me to be able to sort. Here's what I have so far..

Expand|Select|Wrap|Line Numbers
  1. package trials;
  2.  
  3. import java.awt.Color;
  4. import java.awt.Point;
  5. import java.util.List;
  6. import java.util.ArrayList;
  7. import java.util.Comparator;
  8.  
  9. public class CircleSort extends Circle{
  10.  
  11.     class CircleComparator implements Comparator<Circle> {
  12.  
  13.         public int compare(Circle cOne, Circle cTwo) {
  14.  
  15.             int result = cOne.getRadius().compareTo(cTwo.getRadius());
  16.             if (cOne.getRadius() = cTwo.getRadius())
  17.             {
  18.                 result = cTwo.getColor().getGreen().compareTo(cTwo.getColor().getGreen());
  19.             }
  20.             else if (cOne.getColor().getGreen() = cTwo.getColor().getGreen())
  21.             {
  22.                 result = cTwo.getColor().getBlue().compareTo(cTwo.getColor().getBlue());
  23.             }
  24.             else if(cOne.getColor().getBlue() = cTwo.getColor().getBlue())
  25.             {
  26.                 result = cOne.getColor().getRed().compareTo(cTwo.getColor().getRed());
  27.             }
  28.  
  29.             return result;
  30.  
  31.         }
  32.  
  33.     }
  34. }
  35.  
What now?
Dec 17 '07 #11

P: 18
I keep getting this error "Cannot invoke compateTo(int) on the primitive type int" when Im trying to compare the colors. How do I fix that. I also need to know how to implement the sort in the main.
Dec 17 '07 #12

BigDaddyLH
Expert 100+
P: 1,216
I keep getting this error "Cannot invoke compateTo(int) on the primitive type int" when Im trying to compare the colors. How do I fix that. I also need to know how to implement the sort in the main.
int is a primitive type, so ints are not objects. To compare ints I usually rely on a simple utility method like:

Expand|Select|Wrap|Line Numbers
  1. public static int compareInts(int x, int y) {
  2.     if (x < y)
  3.         return -1;
  4.     else if (x > y)
  5.         return 1;
  6.     else
  7.          return 0;
  8. }
Or you can use the fact that the wrapper class Integer is comparable.
Dec 18 '07 #13

P: 18
Ok, but how would I incorporate that to my comparator? (I'm really bad at this lol)
Dec 18 '07 #14

P: 18
Nvm, I figured out how to incorporate it, I just need help with getting the sort to run in the main. How would I do that
Dec 18 '07 #15

P: 18
If someone can IM me on BiG DoGG 536, this could go by alot quicker.
Dec 18 '07 #16

P: 18
Here is my entire code. The thing looks fine, but I get a small error all the way down below in the main, where it says Collections.sort(circles, circleComp) (I've bolded and underlined where Eclipse gives me the error warning). The error reads: "The method sort(List<T>, Comparator<? super T>) in the type Collections is not applicable for the arguments (ArrayList<Circle>, SortCircle)"

I dont know how to fix this and I think this is the only error preventing me from making this code work, so please, can someone just take a look at it and tell me whats wrong with it? Im so close yet so far lol.

//Code
package trials;

import java.awt.Color;
import java.awt.Point;
import java.io.Serializable;

public class Circle implements Serializable{

private static final long serialVersionUID = -9207159802160528525L;
public Point center;
public int radius;
public Color color;

public Circle(Point center, int radius, Color color){
this.center = center;
this.radius = radius;
this.color = color;
}

public Point getCenter() {
return center;
}

public Color getColor() {
return color;
}

public Integer getRadius() {
return radius;
}
}
---------------------------------------------------------------------------------------

package trials;

import java.util.ArrayList;
import java.util.Comparator;


public class CircleSort {

private static final long serialVersionUID = -9207159802160528525L;
public static int compareInts(int x, int y){
if (x > y)
return -1;
else if (y > x)
return 1;
else
return 0;
}

public static void SortCircle (ArrayList<Circle> circles, Comparator<Circle> compare){

class CircleComparator implements Comparator<Circle> {

public int compare(Circle cOne, Circle cTwo) {

int result = compareInts(cOne.getRadius(), cTwo.getRadius());
if (cOne.getRadius()== cTwo.getRadius())
{
result = compareInts(cOne.getColor().getGreen(), cTwo.getColor().getGreen());
}
else if (cOne.getColor().getGreen() == cTwo.getColor().getGreen())
{
result = compareInts(cOne.getColor().getBlue(), cTwo.getColor().getBlue());
}
else if(cOne.getColor().getBlue() == cTwo.getColor().getBlue())
{
result = compareInts(cOne.getColor().getRed(), cTwo.getColor().getRed());
}

return result;
}
}
}
}
-----------------------------------------------------------------------------------------------
package trials;

import java.awt.Color;
import java.awt.Point;
import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Collections;

public class CircleSortMain {

public static void main(String[] args){

ArrayList<Circle> circles = new ArrayList<Circle>();
Random rint = new Random();
for(int i = 0; i < 5000; ++i){
circles.add(
new Circle(
new Point(rint.nextInt(500),rint.nextInt(500)),//sets center
rint.nextInt(500),//sets radius
new Color(rint.nextInt(256),rint.nextInt(256),rint.nex tInt(256))));//sets color
}
ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("circles.arraylist"));
out.writeObject(circles);

SortCircle circleComp = new SortCircle();
Collections.sort(circles, circleComp);
System.out.println(circles + "/n");
}
}
Dec 18 '07 #17

BigDaddyLH
Expert 100+
P: 1,216
Things are going wrong in class CircleSort. It has a method called SortCircle that takes two parameters (circles and compare) that are never used. All this method does is declare a local class which implements Comparator. That's too tricky. I suggest you keep it simple -- define the comparator as a top-level class - not nested in anything.

The logic of the comparator is also wrong. If should be
- compare radius
- if tied, compare green components
- if still tied compare red components,
- if still tied, compare blue components
(I may have the order wrong there, but I hope the intent is clear.)
Dec 18 '07 #18

P: 18
The logic of the comparator is exactly the way you said it should be isnt it? it first compares the radius, if equal, then compare the green color components and so forth. I took out the Sort circle method, but i still get an error in the main. How can I fix this error?
Dec 18 '07 #19

BigDaddyLH
Expert 100+
P: 1,216
Looking back on your original assignment, I'm not certain about the requirements:
Your job is to:
(a) Sort the circles by radius, smallest first
(b) Sort the circles by the red component of their color, largest first, and for those with the same red component by the blue (largest first) and if the red and blue is the same, then by green (largest first). This requires three sorts, the last two of which need to be stable. First sort by green, then blue (stable) and finally by red( stable). Note that merge sort is fast and stable. Quick sort is fast, but not stable.
That reads to me as a requirement that you are able to carry out two separate sorts: by radius and by color. Are you sure you are meant to only write one comparator: order by radius, then break ties by ordering by color?

Assuming that, the logic in your comparator (reply #17) is wrong:
Expand|Select|Wrap|Line Numbers
  1. int result = compareInts(cOne.getRadius(), cTwo.getRadius());
  2. if (cOne.getRadius()== cTwo.getRadius()) {
  3.     result = compareInts(cOne.getColor().getGreen(), cTwo.getColor().getGreen());
  4. } else if (cOne.getColor().getGreen() == cTwo.getColor().getGreen()) {
  5.  
This reads:

Compare radii; if they are equal, compare green else if green is equal... But if radii are different, you should be done!
Also note that the original requirement was to sort by red, then blue, then green, and your code is (attempting) green, then blue, then red.

I suggest you look more closely at my example in reply #9 -- note that my code does not have a single else in the comparator!!!

As for writing a comparator class, reply #9 shows how to do that as well. Understand that code and you are done.
Dec 18 '07 #20

Post your reply

Sign in to post your reply or Sign up for a free account.