Friday, April 8, 2011

quicksort - book's code, cleaned-up version

Ref: Listing 7.3 in text book.

The book's code is, well, kind of messy.
Cannot stand the while-loop desined with break statements.
So, I fixed it!

///// quicksort /////

package cis55_quicksort03;
/**
 * CIS-55 Data Structure
 * Project: QuickSort
 * Date:    2011-04-08
 * @author tetsuro
 */

public class QuickSort {
    private long[] qsData;
    private int nElem;

    public QuickSort(int max) {
        qsData = new long[max];
        nElem = 0;
    }

    public void insert(long value) {
        qsData[nElem] = value;
        nElem++;
    }

    public int size() {
        return nElem;
    }

    public void display() {
        System.out.print("Data = ");
        for (int i = 0; i < nElem; i++) {
            System.out.printf("%3d ",qsData[i]);
        }
        System.out.println("");
    }

    //
    // I removed
    //    public void quickSort()
    // because don't need this extra stuff
    // Instead, use this
    //    public void sort(int left, int right)
    // When call this in main, do this:
    //    arr.sort(0, arr.size()-1);

    //
    public void sort(int left, int right) {

        // base case is: (right-left <= 0), which is omitted in code
        if (right-left > 0) {
            long pivot = qsData[right];
            int px = partition(left, right, pivot);
            sort(left, px - 1);
            sort(px + 1, right);
        }

    }
    //
    // Along with removing break s statement,
    // I removed the stuff like left-- and left+1.
    // If nothing holds me back, I would say that's really stupid.
    // The reason for that was, I think, to have
    // a one-line while-loop for "left".
    // Just have "left++" in the while loop.
    //
   
    private int partition(int left, int right, long pivot) {
        int temp = right;
        boolean flag = true;
        while (flag) {
            while (qsData[left] < pivot) {
                left++;
            }
            while ((right > 0) && (qsData[--right] > pivot)) {
            }
            if (left < right) {
                swap(left, right);

                left++;
            } else {
                flag = false;
            }
        }
        swap(left, temp);
        return left;
    }

    public void swap(int x, int y) {
        long temp;
        temp = qsData[x];
        qsData[x] = qsData[y];
        qsData[y] = temp;
    }
}



///// main /////

package cis55_quicksort03;
/**
 * CIS-55 Data Structure
 * Project: QuickSort
 * Date:    2011-04-08
 * @author tetsuro
 */

public class QuickSortApp {
    public static void main(String[] args) {
        int maxSize = 16;
        QuickSort arr;
        arr = new QuickSort(maxSize);

        for (int i = 0; i < maxSize; i++) {
            long n = (int)(java.lang.Math.random()*199);
            arr.insert(n);
        }

        arr.display();
        arr.sort(0, arr.size()-1);
        arr.display();
    }

}

1 comment: