Selection Sort type iteration with LinkedList
Hi,
It seems like Java's ListIterator isn't especially great for doing a "compare every element to every other element" traversion (like the type used in selection sort).
For example, this code works fine:
for(ListIterator<T> i = list.listIterator(); i.hasNext();){
T a = i.next();
for(ListIterator<T> j = list.listIterator(j.nextIndex()); j.hasNext();)
compare(a, j.next());
}
But LinkedList.listIterator(int) is a really poor choice because the iterator has to start at one end and make its way towards the middle before it's returned. So it's not very fast.
I would do this:
for(ListIterator<T> i = list.listIterator(); i.nextIndex() < list.size()-1;){
T a = i.next();
ListIterator<T> j = i.clone();
for(j.next(); j.hasNext();)
compare(a, j.next());
}
except that ListIterator.clone() isn't defined. There's also no copy constructor like in C++.
Any ideas?
[1239 byte] By [
Nialsha] at [2007-11-27 7:57:59]
# 3
> Any ideas?
An idea; for the second (inner) iterator, rather than iterating from the current element of the first iterator to the end, you may iterate from the beginning to the current element? The stop conditionmay be slightly more complicated, but as far as I can see, you obtain comparing every element to every other element exactly once without any superfluous traversel.
OleVVa at 2007-7-12 19:39:52 >
# 4
> An idea; for the second (inner) iterator, rather than
> iterating from the current element of the first
> iterator to the end, you may iterate from the
> beginning to the current element? The stop
> conditionmay be slightly more complicated, but as far
> as I can see, you obtain comparing every element to
> every other element exactly once without any
> superfluous traversel.
You are exactly right. I would do it from the end of the list to the position of the outer iterator.
But that sounds perfect. I guess I'm just frustrated that you can't clone iterators... it seems like such a fundamental ability.
Anyway, thanks for your help. My problem's solved.
# 5
> Instead of compare() I'm going to be
> doing structural modifications where the iterators are...
Another reason not to use iterators. I don't know what those "structural modifications" are but they are likely to make the iterators fail via ConcurrentModificationException.
And just another comment: you seem to be allowing your brain to be fogged by the idea of choosing the fastest method. The result of this is that you don't get any working methods at all. Don't optimize yet.
# 6
> Another reason not to use iterators. I don't know
> what those "structural modifications" are but they
> are likely to make the iterators fail via
> ConcurrentModificationException.
>
Yeah, I figured that one out pretty quickly.
> And just another comment: you seem to be allowing
> your brain to be fogged by the idea of choosing the
> fastest method. The result of this is that you don't
> get any working methods at all. Don't optimize yet.
That's valid. I actually have it working now, but based on the (minimal) experience I've had I always pick the most appropriate collection and then work it out from there.
Something inside me dies whenever I see remove(0) called on a long ArrayList.
