Results 1 to 5 of 5
- 02-17-2012, 12:57 AM #1
Member
- Join Date
- Dec 2011
- Posts
- 11
- Rep Power
- 0
generic implementation of insertion sort
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.
Java Code: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; } }
Last edited by cris9288; 02-17-2012 at 12:59 AM.
- 02-17-2012, 01:11 AM #2
Moderator
- Join Date
- Feb 2009
- Location
- New Zealand
- Posts
- 4,716
- Rep Power
- 17
Re: generic implementation of insertion sort
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.)
- 02-17-2012, 01:32 AM #3
Member
- Join Date
- Dec 2011
- Posts
- 11
- Rep Power
- 0
Re: generic implementation of insertion sort
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?
- 02-17-2012, 02:04 AM #4
Moderator
- Join Date
- Feb 2009
- Location
- New Zealand
- Posts
- 4,716
- Rep Power
- 17
Re: generic implementation of insertion sort
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.
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?
- 02-17-2012, 03:06 AM #5
Member
- Join Date
- Dec 2011
- Posts
- 11
- Rep Power
- 0
Similar Threads
-
Insertion Sort
By apiwowar in forum New To JavaReplies: 2Last Post: 08-31-2011, 08:20 AM -
Using a Generic Insertion Sort method
By dubois.ford in forum New To JavaReplies: 0Last Post: 02-06-2011, 04:08 AM -
Help with insertion sort
By daendoonge in forum Java AppletsReplies: 0Last Post: 01-30-2011, 12:28 AM -
Insertion Sort in Java
By Java Tip in forum AlgorithmsReplies: 0Last Post: 04-15-2008, 08:41 PM -
Insertion sort algorithm
By Albert in forum Advanced JavaReplies: 2Last Post: 06-28-2007, 09:26 PM
Bookmarks