Sort Literate Programming Example

Result = 1,2,3,6,8,12,12,32,42,99,

package org.berlin.math.algo;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * A look at the quick sort/sort algorithms from GNU classpath.
 @author berlin brown 
 */
public class QuickSort3 {
    private int comps = 0;
    
    public static void main(final String [] argsthrows Exception {
        System.out.println("Testing");
        final int [] a = new int [] {
                12
                3
                9,
                23,
                55
                2                
        };        
        System.out.println("Done");
        final QuickSort3 t = new QuickSort3();        
        t.sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println("-]" + a[i]);
        // End of the for //        
        final QuickSort3 tt = new QuickSort3();
        tt.read();
        
    // End of the method main //
    
    // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n)
    // performance on many arrays that would take quadratic time with a standard
    // quicksort.
    public void sort(final int [] a) {
        sort(a, 0, a.length);
    // End of the method //
    
    /**
     * Performs a stable sort on the elements, arranging them according to their
     * natural order.
     */
    public void sort(final int[] a, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException();
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        qsort(a, fromIndex, toIndex - fromIndex);
    }

    /**
     * Performs a recursive modified quicksort.
     */
    protected void qsort(int[] array, int from, int count) {
        // Use an insertion sort on small arrays.
        if (count <= 7) {
            for (int i = from + 1; i < from + count; i++)
                for (int j = i; j > from && array[j - 1> array[j]; j--)
                    swap(j, j - 1, array);
            return;
        }
        // Determine a good median element.
        int mid = from + count / 2;
        int lo = from;
        int hi = from + count - 1;
        if (count > 40) { // big arrays, pseudomedian of 9
            int s = count / 8;
            lo = med3(lo, lo + s, lo + * s, array);
            mid = med3(mid - s, mid, mid + s, array);
            hi = med3(hi - * s, hi - s, hi, array);
        }
        mid = med3(lo, mid, hi, array);
        int a, b, c, d;
        int comp;
        // Pull the median element out of the fray, and use it as a pivot.
        swap(from, mid, array);
        a = b = from;
        c = d = from + count - 1;
        // Repeatedly move b and c to each other, swapping elements so
        // that all elements before index b are less than the pivot, and all
        // elements after index c are greater than the pivot. a and b track
        // the elements equal to the pivot.
        while (true) {
            while (b <= c && (comp = compare(array[b], array[from])) <= 0) {
                if (comp == 0) {
                    swap(a, b, array);
                    a++;
                }
                b++;
            }
            while (c >= b && (comp = compare(array[c], array[from])) >= 0) {
                if (comp == 0) {
                    swap(c, d, array);
                    d--;
                }
                c--;
            }
            if (b > c)
                break;
            swap(b, c, array);
            b++;
            c--;
        }
        // Swap pivot(s) back in place, the recurse on left and right sections.
        hi = from + count;
        int span;
        span = Math.min(a - from, b - a);
        vecswap(from, b - span, span, array);
        span = Math.min(d - c, hi - d - 1);
        vecswap(b, hi - span, span, array);
        span = b - a;
        if (span > 1)
            qsort(array, from, span);
        span = d - c;
        if (span > 1)
            qsort(array, hi - span, span);
    // End of the method //

    /**
     * Swaps the elements at two locations of an array
     */
    protected void swap(int i, int j, int[] a) {
        int c = a[i];
        a[i= a[j];
        a[j= c;
    }

    /**
     * Swaps two ranges of an array.
     */
    protected void vecswap(int i, int j, int n, int[] a) {
        for (; n > 0; i++, j++, n--)
            swap(i, j, a);
    }

    /**
     * Finds the index of the median of three array elements.     
     */
    protected int med3(int a, int b, int c, int[] d) {
      return (d[a< d[b]
              (d[b< d[c? b : d[a< d[c? c : a)
              (d[b> d[c? b : d[a> d[c? c : a));
    }
    
    /**
     * Compares two integers in natural order, since a - b is inadequate.
     */
    protected int compare(final int a, final int b) {
        comps++;
        return (a < b? -(a == b1;
    }
    
    public void read() throws Exception {
        final List<Integer> list = new ArrayList<Integer>();
        final FileInputStream stream = new FileInputStream("./numbers.dat");
        final BufferedReader reader = new BufferedReader(new InputStreamReader(stream));
        String data = "";
        try {
            do {
                data = reader.readLine();
                if (data != null) {
                    final int i = Integer.parseInt(data.trim());
                    list.add(i);
                // End of the if //
            while(data != null);
        catch(final Exception e) {
            e.printStackTrace();
        finally {
            if (stream != null) {
                try {
                stream.close();
                catch(Exception ee) { }
            }
        }        
        final int [] arr = toint(list);
        sort(arr);
        for (int j = 0; j < 13; j++) {
            System.out.println("->j:" + j + " " + arr[j]);
        }
        System.out.println("Compares : " + comps);
    // End of read method //
    
    protected int[] toint(final List<Integer> integers) {
        int[] ret = new int[integers.size()];
        for (int i=0; i < ret.length; i++)
        {
            ret[i= integers.get(i).intValue();
        }
        return ret;
    // End of the method //
    
// End of the class //