Results 1 to 5 of 5
  1. #1
    cris9288 is offline Member
    Join Date
    Dec 2011
    Posts
    11
    Rep Power
    0

    Default 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.

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default 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.)

  3. #3
    cris9288 is offline Member
    Join Date
    Dec 2011
    Posts
    11
    Rep Power
    0

    Default 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?

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default 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.
    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.

  5. #5
    cris9288 is offline Member
    Join Date
    Dec 2011
    Posts
    11
    Rep Power
    0

    Default Re: generic implementation of insertion sort

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

Similar Threads

  1. Insertion Sort
    By apiwowar in forum New To Java
    Replies: 2
    Last Post: 08-31-2011, 08:20 AM
  2. Using a Generic Insertion Sort method
    By dubois.ford in forum New To Java
    Replies: 0
    Last Post: 02-06-2011, 04:08 AM
  3. Help with insertion sort
    By daendoonge in forum Java Applets
    Replies: 0
    Last Post: 01-30-2011, 12:28 AM
  4. Insertion Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 08:41 PM
  5. Insertion sort algorithm
    By Albert in forum Advanced Java
    Replies: 2
    Last Post: 06-28-2007, 09:26 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •