Wednesday, September 18, 2013

A poor way to do sorting in an OO language (java)

Going back to Java after so many years is an interesting experience. I made the classic rookie mistake with implementation of a sorting library. All good programming practices tell you that manipulation methods on a collection should always be static and not bound to the class. To top it all, this was the first time I was using generics after spending some time reading about them :)

I had done things the other way around, almost as if I had implemented a stack with data. My ego was too big for me not to succeed with that technique. Here is an implementation of selection sort. Below is what I ended up implementing

/**
 *
 * @author balbir
 * @param 
 */
public class SelectionSort < Item extends Comparable > {
    private Item[] elements;
    SelectionSort(int N)
    {
        elements = (Item[]) new Comparable[N];    
    }

    public void sort()
    {
        int min;
        for (int i = 0; i < elements.length; i++)
        {
            min = i;
            for (int j = i+1; j < elements.length; j++)
            {
                if (elements[j].compareTo(elements[min]) < 0)
                    min = j;
            }
            Item tmp;
            tmp = elements[i];
            elements[i] = elements[min];
            elements[min] = tmp;
            
        }
    }
    
    public void dump()
    {
        for (int i = 0; i < elements.length; i++)
            System.out.print(elements[i] + " ");
        System.out.println();
    }
    
    public void load(Item a[])
    {
        for (int i = 0; i < elements.length; i++)
            elements[i] = a[i];
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Integer[] a = {1, 2, -1, 3, 0, 5, 7, 9, 4};
        SelectionSort s = new SelectionSort(a.length);
        s.load(a);
        s.dump();
        s.sort();
        s.dump();
    }
    
}


It is funny how I had to use a load class to get the data and call the sort method. What a bad decision, the reason I shared this post is just to show that with generics one can indeed mix classes and class templates. I for example mixed Integer and Comparable and the default implementation worked.

No comments:

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...