generic implementation of insertion sort

[cris9288]

I am trying to figure out a way to implement an insertion sort method that takes in any kind of collection. However since the collection class does not have any methods allowing me to access an element at a particular index, and it's iterator methods only have methods to return the next item, i'm a little stumped as to how I can do this. This is my solution so far, but I am quite unsatisfied. Is there a better way? Not looking for someone to post a full answer, but hoping to get some ideas. Thanks.

    public static <AnyType> void sort(Collection<? extends AnyType> coll, 
            Comparator<? super AnyType> cmp) {
        
        Object [] arr = coll.toArray();
        
        for (int p = 1; p < arr.length; p++){
            
            Object temp = arr[p];
            int j = p;
            
            for (; j > 0 && cmp.compare((AnyType) temp, (AnyType) arr[j - 1]) < 0; j--)
                arr[j] = arr[j - 1];
            arr[j] = temp;
        }
        
        
    }

[pbrockway2]

That method seems to sort the array arr. Is that your intention? I ask because you don't do anything with arr.

Collections are not, in general ordered (they don't have a first, a second a third etc element). So it doesn't make sense to speak of them being sorted: at best something else is sorted. Imagine someone comparing eggs by weight and placing them largest first into a bag. Is the bag of eggs sorted? Were they to place them into an egg carton then the egg carton of eggs *would* be sorted.

It seems to me that your method should *return* an ordered collection. (Including an array that is implicitly ordered by its index.)

[cris9288]

My intention was to sort coll, if for some reason you had an ArrayList or some other kind of List that needed to be sorted. Of course, Collection is abstract so I wouldn't be able to just return that. I would have to return either an array that would be added to a specific list in some other application or a specific kind of list, rendering this "generic" method kind of useless. I guess I misunderstood the idea of a collection. Really what I wanted was to try and be comfortable with working with generic syntax and to be able to implement a method in anyway I wanted. I guess that's why I am not a teacher. So would you say this method would work better for any kind of List?

[pbrockway2]

However since the collection class does not have any methods allowing me to access an element at a particular index, and it's iterator methods only have methods to return the next item, i'm a little stumped as to how I can do this.

I think this observation of yours gets right to the heart of things. "Sorting" requires that a collection have an ordering (like an egg carton, but not like a bag). Sorting consists of making the collection's ordering congruent with the ordering of the collection elements (as given by the comparator). The collection's ordering can come from some notion of index value, or at least a guarantee that iterators will always return the collection's elements in some particular order.

There are two ways to go if you want a generic sorter method (or so it seems to me, others may disagree). Either return a new collection that really does have an ordering and which contains the same elements, but sorted. This could be a List of some sort, or an array. In your case it might mean changing the method so that it returns an array and then returning arr. Better might be to return an instance of List<AnyType> - which is straightforward but involves changing your method to use List.get()/set() in place of the array accesses.

In this case the caller has to understand that the collection they get back is different from the collection they passed as an argument. It contains the same elements, of course, and is sorted, which is what they want.

The alternative is to make the method a little less general and have it require a List<AnyType> to be passed, rather than a Collection. Now the sorting is "in place" and the method really can be void. Although less general this does cover the specific cases you mention.

So would you say this method would work better for any kind of List?

That is certainly an option. (the second above). And in that case you don't actually need the arr array, you can use the get()/set() methods directly on the list that is passed.

[cris9288]

Thank you for this. I have a much better understanding of what I want to do now.