Sorting
I would like to create a method that sorts an array list using the selectionsort algorithm. I've recieved the algorithm for an array, and this is what I have.
publicstaticvoid selectionSort (Comparable[] list)
{
int min;
Comparable temp;
for (int index = 0; index < list.length-1; index++)
{
min = index;
for (int scan = index+1; scan < list.length; scan++)
if (list[scan].compareTo(list[min]) < 0)
min = scan;
temp = list[min];
list[min] = list[index];
list[index] = temp;
}
}
How do I change it to sort ArrayList
thanks
[1048 byte] By [
darksssa] at [2007-11-27 0:09:20]
Take the tutorial: http://java.sun.com/docs/books/tutorial/collections/index.html
So I've modified the method to this
public static void selectionSort (ArrayList list) {
int min;
Comparable temp;
for (int index = 0; index < list.size()-1; index++) {
min = index;
for (int scan = index+1; scan < list.size(); scan++)
if (list.get(scan).compareTo(list.get(min) < 0))
min = scan;
// Swap the values
temp = list.get(min);
list.get(min) = list.get(index);
list.get(index) = temp;
}
}
and I get this error
operator < cannot be applied to java.lang.Object,int
if (list.get(scan).compareTo(list.get(min) < 0))
Why cant an int use the < operator?
Take a close look at that line. A parenthesis is in the wrong place!
it says illegal start of typeif ((list.get(scan)).compareTo(list.get(min))) < 0)
> Take a close look at that line. A parenthesis is in> the wrong place!
if (list.get(scan).compareTo(list.get(min)) < 0)cannot find symbolsymbol : method compareTo(java.lang.Object)location: class java.lang.Objectif (list.get(scan).compareTo(list.get(min)) < 0)
> if (list.get(scan).compareTo(list.get(min)) <
> 0)
> cannot find symbol
> symbol : method compareTo(java.lang.Object)
> location: class java.lang.Object
> if
> (list.get(scan).compareTo(list.get(min)) < 0)
The java.lang.Object class has no compareTo(Object) method. You'll need to cast the Objects from your ArrayList to a Comparable.
What type of object is your arraylist holding? Cast it into that object type and then compare them (if the object implements comparable).
could I do that by sayinglist = (Comparable)list;
no, comperable is an interface, not an object that you can cast to because nothing extends it.
> could I do that by saying> list = (Comparable)list;Comparable c = (Comparable)list.get(int);
> > could I do that by saying> > list = (Comparable)list;> > Comparable c = (Comparable)list.get(int);>How would that work, what if the object is not an instance of Comparable?
If you are using the current version of Java (Java SE 6) or the previous version (5),
you can use generics, which obviate the need for that cast:
public static void selectionSort (List < ? extends Comparable > list)
http://java.sun.com/docs/books/tutorial/extra/generics/index.html
> > > could I do that by saying
> > > list = (Comparable)list;
> >
> > Comparable c =
> (Comparable)list.get(int);
> >
>
> How would that work, what if the object is not an
> instance of Comparable?
ClassCastException
> ...> How would that work, what if the object is not an> instance of Comparable?What do you think?
> How would that work, what if the object is not an instance of Comparable?If an object doesn't have type Comparable, then it can't be sorted.Consider the previous code with the Comparable [ ] array -- didn't that code work?
It would throw ClassCastException
> no, comperable is an interface, not an object that> you can cast to because nothing extends it.Huh?
Comperable is generaly used as an interface, not as an object. I have never seen it used as an object.
> Comperable is generaly used as an interface, not as> an object. I have never seen it used as an object.Huh?
> Comperable is generaly used as an interface, not as
> an object. I have never seen it used as an object.
By doingComparable c = (Comparable)someArray[3];
you don't care what's in the array. It could be String's, Integer's, BigDecimal's... as long as it (the thing in the array) implements the Comparable interface.
And I said that not all implemented it.
> And I said that not all implemented it.
Yes, so? It would be silly to stuff an array (or a List) of objects that don't implement the Comparable interface into a sort(...) method in the first place!
If one makes such a mistake, a ClassCastException is thrown for such bad behavior.
An interface defines a type just like a class does. If a class implements an interface, then you can cast an object of that class to the interface. List and ArrayList is a common use of this.List myList = new ArrayList();
> > And I said that not all implemented it.
>
> Yes, so? It would be silly to stuff an array (or a
> List) of objects that don't implement the Comparable
> interface into a sort(...) method in the first
> place!
> If one makes such a mistake, a ClassCastException is
> thrown for such bad behavior.
Aye it is. I never disagreed with that. Not all programmers remember to implements Comparable when making objects, I don't all the time.
And all objects should override toString and equals
> And I said that not all implemented it.
Look at the pre-generics sort method of the java.util.Collections class:
public static void sort(List list)
....
Parameters:
list - the list to be sorted.
Throws:
ClassCastException - if the list contains elements that are not mutually comparable (for example, strings and integers).
UnsupportedOperationException - if the specified list's list-iterator does not support the set operation.
See Also:
Comparable
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#sort(java.util.List)
As you can see, it might throw a ClassCastException for the silly buggers that feed it somthing wrong.
Do you understand it now?
so when using generics, its basically casting it?and the ? is the name of the class I am in?(List < Sorting extends Comparable > list)
> ...
> Aye it is. I never disagreed with that. Not all
> programmers remember to implements Comparable when
> making objects, I don't all the time.
That's why the exception is thrown. What is you point?
> And all objects should override toString and equals
?
You're making less and less sense (to me). I don't follow you anymore.
> > ...
> > Aye it is. I never disagreed with that. Not all
> > programmers remember to implements Comparable when
> > making objects, I don't all the time.
>
> That's why the exception is thrown. What is you
> point?
>
>
> And all objects should override toString and equals
>
> ?
> You're making less and less sense (to me). I don't
> follow you anymore.
And to myself too. I wasn't even thinking about try/catch/finally things since you didn't show it with it, and being me and loving to argue and hate to lose face continued beating a dead horse.
is this correctpublic static void selectionSort (ArrayList<Comparable > list) {or do I have to dopublic static void selectionSort (ArrayList<Sorting extendsComparable > list) {where Sorting is the class the method selectionSort is in
try it and see, if it doesn't work give us the error message or try another way (or both).
class Sorting {
public static void selectionSort (ArrayList<Comparable > list) {
int min;
Comparable temp;
for (int index = 0; index < list.size()-1; index++) {
min = index;
for (int scan = index+1; scan < list.size(); scan++)
if (list.get(scan).compareTo(list.get(min)) < 0)
min = scan;
// Swap the values
temp = list.get(min);
list.get(min) = list.get(index);
list.get(index) = temp;
}
}
}
now I get unexpected type
required: variable
found: value
list.get(min) = list.get(index);
list.get(index) = temp;
> is this correct
> public static void selectionSort
> (ArrayList<Comparable > list) {
> or do I have to do
> public static void selectionSort (ArrayList<Sorting
> extendsComparable > list) {
>
> where Sorting is the class the method selectionSort
> is in
Was something wrong with reply #14?
> ...> Was something wrong with reply #14?No.
what doesunexpected typerequired: variablefound : valuelist.get(min) = list.get(index);list.get(index) = temp; mean
[url= http://java.sun.com/javase/6/docs/api/java/util/List.html#get(int)]get[/url] versus [url= http://java.sun.com/javase/6/docs/api/java/util/List.html#set(int,%20E)]set[/url]Extra credit: write that swap in one statement.Message was edited by: DrLaszloJamf
> > ...
> > Was something wrong with reply #14?
>
> No.
(had a little peek at the API)
Although without warnings it should be public static < T extends Comparable< ? super T >> void sort(List<T> list)
... perhaps a bit daunting for the OP.
*Gulp* You're right. That's a party pretzel.
