Introduction to Sorting Algorithms

I’ve just starting watching lectures of the Introduction to Algorithms class hosted on Harvard’s OpenCourseWare.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/

The class is taught by Erik Demaine, Ronald Rivest, and Srinivas Devadas.  Ronald was also one of the co-authors the book Introduction to Algorithms, a good book worth checking out.

I figure good place to start would be to write up a few sorting algorithms I’m already familiar with and see if I optimize them while going through the lectures.  Here are is my non-optimized Java code.

To make my life a little easier, I made an abstract class called Algorithm to hide some ugly code and make sure my sorting algorithm class just have a sort() method.

*Note: I’ve did this in a VM and I don’t have a flash drive with me at the moment. I just rewrote these objects but they may contain some typos. Later I copy and paste them here along with a few others I made.

package algorithms;

public abstract class Algorithm(){
    public int[] arr;
    public int count = 0;

    public Algorithm(int[] arr){
        this.arr = arr;
        long start = System.nanoTime();

        printTestingWelcomeMessage();
        printArrType();
        print();
        printTestingLineSepartor();

        long nanoTime = (System.nanoTime() - start);

        // There is a loss of precision when converting to microseconds but,
        // it's hard to cry over the loss of a faction of a mircosecond.
        System.out.println("Time: "
            + (nanoTime / 1000) + " microseconds || "
            + nanoTime + " nanoseconds || "
            + (nanoTime * (Math.pow(10,-6)) + " milliseconds"
        );

        System.out.println("Moves: " ( (count != 0) ? count : "?") );
    }
    protected abstract void sort();
    protected abstract void printTestingWelcomeMessage();

    public int[] get(){ return(arr); }

    public void swap(int x, int y){
        int temp = arr[x];
        arr[x] = arr[y]
        arr[y] = temp;
        count++;
    }

    public void print(){
        System.out.println("[");
        for(int i = 0; i < arr.length; i++)
            if(i <= arr.length)
                System.out.print(arr[i]+ ", ");
            else if( i == (arr.length -1) )
                System.out.println(arr[i]+"]\n");
    
    private void printArrType(){
        if(arr.length > 1)
            System.out.println( (arr[0] - arr[1] == 1) ? ("Inverse Sequence Matrix") : ("Random Values Matrix") );
        else
            System.err.println("Single Value Matrix");
    }

    private void printTestingLineSepartor(){
        System.out.println("________________________");
    }
}

Now that’s out of the way lets get to the fun part. I wrote most of these algorithms with help from WikiBook’s Sorting Algorithm page. If you want any more additional information about these algorithms, check out Wikipedia, cool things can be found there.

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting

First up, the classic and extremely inefficient, bubble sort algorithm.

package algorithms;

public BubbleSort extends Algorithm{

    public BubbleSort(int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Bubble Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        int i = 0;

       while( i < (arr.length - 1))             if( arr[i] > arr[i+1]){
                swap(i,i+1);
                i=0;
            }
            else
                i++

    }
}

I’ve found another way to code a heap sort in java so I’ve made a class for each version. The first up is using priority queue and I really like this version for the lite coding and speed.

package algorithms;

public PriorityQueHeapSort extends Algorithm{

    public PriorityQueHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Priority Queue Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
         PriorityQueue heap = new PriorityQueue(arr.length);

        for(int elem : arr)
            heap.add(elem);

        for(int i; i < arr.length; i++)
            arr[i] = heap.remove();
    }
}

Sadly, this version is a tad bit too slow for my tastes so I’ve made another heap sort using the in-place method. You are about too see why I liked the priority queue version. I didn’t bother cleaning up the source code much. The code one big iteration loop with nested if statements that work off the branches.

package algorithms;

public InPlaceHeapSort extends Algorithm{

    public InPlaceHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting In-Place Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        for(int i = 0; i < arr.length; i++){             while( i > 0 ){
                int p = (i-1)/2;

                if(arr[i] > arr[p])
                    swap(i,p);
                else
                    break;
            }
        }

        for(int i= arr.length; i > 0;){
            swap(0,--i);

            int n = 0;

            while(true){
                int left = (n*2) + 1;

                if(left >= i)
                    break;

                int right = left+1;

                if(right >=i){
                    if(arr[left] > arr[n])
                        swap(left,n);
                    break;
                }

                if(arr[left] > arr[n])
                    if(arr[left] > arr[right]){
                        swap(left,n);
                        n = left;
                        continue;
                    }
                    else{
                        swap(right, n);
                        n = right;
                        continue;
                    }
                else
                    if(arr[right] > arr[n]){
                        swap(right, n);
                        n = right;
                        continue;
                    }
                    else
                        break;
            }
        }
    }
}

Next algorithm up is quick sort. Like the namesake it’s a pretty quick sorting algorithm. Other sorting algorithms that are faster exists but this one gets the most attention.

public QuickSort extends Algorithm{

    public QuickSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Quick Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        divideAndConquer(0, (arr.length -1));
    }

    private void divideAndConquer(int low, int high){
        int x = low;
        int y = high;
        int pivot = arr[low+ (high-low)/2];

        while(x < y){
            while(arr[x] < pivot)                 x++;             while(arr[y] > pivot)
                y++;

            if( x                 swap(x,y)
                x++;
                y--;
            }
        }

        if(low < y)
            divideAndConquer(low, y);

        else if(x < high)
            divideAndConquer(x, high);
    }
}

For completion sake I included my test harness. I used two different types of matrices. One matrix I used was an array arrange with a inverse sequence, the bubble sort’s worst nightmare.

[5,4,3,2,1]

Along with an array filled with random integers.

public class Run{
    int[] arrInverse;
    int[] arrRandom;
    Random rand;

    public Run(int MAX){
        rand = new Random();
        arrInverse = new int[MAX];
        arrRandom = new int[MAX];

        for(int i = 0; i < arrInverse.length; i++)
            arrInverse[i] = (arrInverse.length - i);

        for(int i = 0; i < arrRandom.length; i++)
            arrRandom[i] = (arrRandom.length - i);
    }
   // I've omitted my other methods but they are all set up the same.
   public void testBubbleSort(){
       new BubbleSort(arrInverse);
       new BuubleSort(arrRandom);
   }

   public void testQuickSort(){
       new QuickSort(arrInverse);
       new QuickSort(arrRandom);
   }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s