The Java Sorting Algorithm Playground

Algorithms and I have a love-hate history. I met them in college in a course in fifth semester, and I was pretty excited about it because it was the first course of the Software Development track of my major. Systems Engineering (that’s what Computing Professionals study in Pery) in my university has a very peculiar curricula, and to start coding you have to first pass several hard and heavy math and science courses. So after two years of suffering with engineering fundamentals I finally get to what I really expect from College education: to learn how to code.

But bad luck is always after me, and I got the worst teacher from the entire faculty. It was and old school guy that teaches algorithms with pseudo-code and diagrams and never –I mean NEVER- showed us a running program or a software demonstration. And also the syllabus of the course was very light and superficial (I don’t remember even a mention of Binary Search Trees). The semester ended, I got a nice grade and I forgot about algorithms for a very long time.

A few years ago my interest for algorithms was renewed when I discovered that all Computer Science dream Jobs –like Google or Facebook- have an algorithm-based interview in their hiring process, so I decided to get ready when the moment comes and start to learn by myself all the topics that I was supposed to learn at college. I did a light forum-research for recommendations of good algorithm books and started my training with Skienna and his Algorithm Design Manual. It’s a very theoretical book and while reading I needed a lot of Wikipedia searching to get some notions. Reading was hard and slow –but very instructive- and the coding part was written all in C, a Programming Language that I’m not very familiar with (I know, shame on me!). So learning algorithm concepts was hard and getting C syntax made it harder, so I decided to get a Java-Based Algorithm Book and speed up my learning process.

The selected book was Data Structures and Algorithms in Java by Robert Lafore and was more beginner-friendly than the academically-oriented Skienna book. Reading was lots of fun, until I found code like this:

// insertSort.java
// demonstrates insertion sort
// to run this program: C>java InsertSortApp
//--------------------------------------------------------------
class ArrayIns
	{
	private long[] a; // ref to array a
	private int nElems; // number of data items
	//--------------------------------------------------------------
	public ArrayIns(int max) // constructor
		{
		a = new long[max]; // create the array
		nElems = 0; // no items yet
		}
	//--------------------------------------------------------------
	public void insert(long value) // put element into array
		{
		a[nElems] = value; // insert it
		nElems++; // increment size
		}
	//--------------------------------------------------------------
	public void display() // displays array contents
		{
		for(int j=0; j<nElems; j++) // for each element,
		System.out.print(a[j] + “ “); // display it
		System.out.println(“”);
		}
	//--------------------------------------------------------------
	public void insertionSort()
		{
		int in, out;
		for(out=1; out<nElems; out++) // out is dividing line
			{
			long temp = a[out]; // remove marked item
			in = out; // start shifts at out
			while(in>0 && a[in-1] >= temp) // until one is smaller,
				{
				a[in] = a[in-1]; // shift item to right
				--in; // go left one position
				}
			a[in] = temp; // insert marked item
			} // end for
		} // end insertionSort()
	//--------------------------------------------------------------
} // end class ArrayIns

That code violated almost all the coding conventions that Sun established and that almost every Java Programmer in the world know. Just to mention some of them:

  • The method-separator comment lines are a really weird convention .
  • There are several patterns for bracket usage (or not using them when they should) and indentation.
  • All the variables/attributes had non descriptive names like “a”, “temp”, “in” and “out”.

Maybe I’m just been too picky, but I think those issues -at least for me – really make the code less readable and more hard to understand. And it’s not a problem only in Lafore book, many other books that I consulted have the same problem: Coding style that doesn’t follow industry-accepted practices. So when I got the assignment in my Algorithm Course to write a Sorting Algorithm Demonstration program I decided the improve the way Java algorithms are presented and rewrite them in a more Convention-Based way, that’s also a more less intimidating way of presenting algorithms to the students (like myself). And that project is now finished and available to everyone interested in my Github account.

For example, let’s see now Insertion Sort:

package pe.edu.pucp.algorithms.sorting.algs.impl;

import pe.edu.pucp.algorithms.sorting.algs.BaseSorter;

/**
 * Implementation of Insertion Sort algorithm. Based on the implementation
 * described in Robert Sedgewick's Algorithm book.
 * 
 * @author Carlos Gavidia (cgavidia@acm.org)
 * 
 * @param <T>
 *            Type of the array to be sorted
 */
public class InsertionSorter<T extends Comparable<T>> extends BaseSorter<T> {

    public InsertionSorter(Class<T> clazz, T[] data) {
        super(clazz, data);
    }

    /*
     * (non-Javadoc)
     * 
     * @see pe.edu.pucp.algorithms.sorting.algs.BaseSorter#sortData()
     */
    @Override
    public void sortData() {
        for (int currentIndex = 0; currentIndex < getLength(); currentIndex++) {
            T currentItem = getDataAtIndex(currentIndex);
            int auxIndex = currentIndex;
            while (auxIndex > 0
                    && getDataAtIndex(auxIndex - 1).compareTo(currentItem) >= 0) {
                setDataAtIndex(auxIndex, getDataAtIndex(auxIndex - 1));
                --auxIndex;
            }
            setDataAtIndex(auxIndex, currentItem);
        }
    }

}

I got some ideas from the Sedgewick book to build an Algorithm Framework that allow the sorting of any Type –that implement Comparable- and to extract the common logic to a Base Class to get the Algorithm Class the cleaner possible, with the only responsibility of implementing the algorithm logic. Also, the access to the array to sort is encapsulated by some methods to makes easier the Observer Pattern implementation required to implement the Sorting process animation. And that animation looks like this (captions in Spanish):

Algorithm Demo

Top-Down merge while executing

As professor requests, I included in the program implementations of Bubble Sort, Merge Sort, Insertion Sort, Quick Sort and some bonus algorithms like Several Unique Sort and Odd-Even Transposition (as you can see in the SortingAlgorithm enumeration). Building the software required a lot of time but I entertained myself doing it, and I really hope that the code can help some other Algorithm Expert wannabe to learn sorting algorithms a little faster (and easier).

Advertisements