sort.java

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

package /*{*/edu.odu.cs.zeil.AlgAE.Demos.Sort./*}*/DataStructures;

/*{*/ // /*}*/import /*{*/edu.odu.cs.zeil.AlgAE.Demos.Sort./*}*/Supporting.*;
import /*{*/edu.odu.cs.zeil.AlgAE.Demos.Sort./*}*/Supporting.Comparable;
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Sort.HeapTree;
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Sort.IntegerPair;
/*{*/
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Utils.Alias;
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Utils.AliasArray;
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Utils.ShadowArray;
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Utils.VisibleInteger;
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Utils.VisibleVector;
/*{*/import edu.odu.cs.zeil.AlgAE.Demos.Utils.WhiteBox;
/*{*/import edu.odu.cs.zeil.AlgAE.Server.algae;
/*{*/import edu.odu.cs.zeil.AlgAE.Server.Visible;
/*{*/import java.awt.Color;

/**
 * A class that contains several sorting routines,
 * implemented as static methods.
 * Arrays are rearranged with smallest item first,
 * using compares.
 * @author Mark Allen Weiss
 */
public final class Sort
{
    /**
     * Simple insertion sort.
     * @param a an array of Comparable items.
     */
    public static void insertionSort( Comparable [ ] a /*{*/, AliasArray aa/*}*/)
    {
/*{*/     WhiteBox wb = new WhiteBox (false);
/*{*/     wb.getRendering().show();
/*{*/     VisibleInteger vj = new VisibleInteger(99, Color.yellow); 
/*{*/     vj.getRendering().setName("j");
/*{*/     vj.indexes(aa); 
/*{*/     wb.add (vj);
/*{*/     VisibleInteger vp = new VisibleInteger(99, Color.yellow); 
/*{*/     vp.getRendering().setName("p");
/*{*/     vp.indexes(aa); 
/*{*/     wb.add (vp);
        for( int p = 1; p < a.length; p++ )
	  {
/*{*/         vp.setInt(p);
            Comparable tmp = a[ p ];
/*{*/           Alias vtmp = new Alias(tmp, Color.green); 
/*{*/           vtmp.getRendering().setName("tmp");
/*{*/           wb.add (vtmp);
/*{*/         algae.FRAME("Where to place p'th object?"); 
            int j = p;
/*{*/         vj.setInt (j);
/*{*/         algae.FRAME("Start looking here."); 
            for( ; j > 0 && tmp.lessThan( a[ j - 1 ] ); j-- )
/*{*/        {
/*{*/            vj.setInt(j); 
/*{*/            algae.FRAME("Move j-1 element up."); 
                a[ j ] = a[ j - 1 ];
/*{*/        }
/*{*/         vj.setInt(j); algae.FRAME("Found where to put tmp."); 
            a[ j ] = tmp;
/*{*/         wb.remove (vtmp);
        }
/*{*/     wb.getRendering().hide();
/*{*/     algae.FRAME("Done."); 
    }

    /**
     * Shellsort, using a sequence suggested by Gonnet.
     * @param a an array of Comparable items.
     */
    public static void shellsort( Comparable [ ] a /*{*/, AliasArray aa/*}*/)
    {
/*{*/     WhiteBox wb = new WhiteBox (false);
/*{*/     wb.getRendering().show();
/*{*/     VisibleInteger vgap = new VisibleInteger(99, Color.cyan); 
/*{*/     vgap.getRendering().setName("gap");
/*{*/     wb.add (vgap);
/*{*/     VisibleInteger vj = new VisibleInteger(99, Color.yellow); 
/*{*/     vj.getRendering().setName("j");
/*{*/     vj.indexes(aa); 
/*{*/     wb.add (vj);
/*{*/     VisibleInteger vi = new VisibleInteger(99, Color.yellow); 
/*{*/     vi.getRendering().setName("i");
/*{*/     vi.indexes(aa); 
/*{*/     wb.add (vi);
        for( int gap = a.length / 2; gap > 0;
                     gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
/*{*/         { vgap.setInt(gap);
            for( int i = gap; i < a.length; i++ )
            {
/*{*/           vi.setInt(i);
                Comparable tmp = a[ i ];
/*{*/           Alias vtmp = new Alias(tmp, Color.green); 
/*{*/           vtmp.getRendering().setName("tmp");
/*{*/           wb.add (vtmp);

/*{*/           aa.highlight(i % gap, i+1, gap);
/*{*/		   
/*{*/           algae.FRAME("Shell: Where to place i'th object?"); 
                int j = i;
/*{*/           vj.setInt(j);

/*{*/           algae.FRAME("Shell: Start looking at a[j]."); 
                for( ; j >= gap && tmp.lessThan( a[ j - gap ] ); j -= gap )
/*{*/        {
/*{*/            vj.setInt(j); 
/*{*/            algae.FRAME("Shell: Move j-gap element up."); 
                    a[ j ] = a[ j - gap ];
/*{*/        }
/*{*/         vj.setInt(j); algae.FRAME("Shell: Found where to put tmp."); 
                a[ j ] = tmp;
/*{*/         algae.unHighlightAll(); algae.FRAME("Shell: Done with this element."); 
/*{*/           wb.remove (vtmp);
            }
/*{*/    algae.FRAME("Shell: Now decrease the gap."); }
/*{*/    wb.getRendering().hide(); algae.FRAME("Shell: Done."); 
    }
     
/*{*/private static void highlightSubtreeRecursion 
/*{*/   (AliasArray aa, HeapTree t, int i, Color c)
/*{*/{
/*{*/  Visible v = t.elementAt(i);
/*{*/  if (v != null)
/*{*/    {
/*{*/      v.getRendering().highlight(c);
/*{*/      aa.aliasAt(i).getRendering().highlight(c);
/*{*/      highlightSubtreeRecursion (aa, t, 2*i+1, c);
/*{*/      highlightSubtreeRecursion (aa, t, 2*i+2, c);
/*{*/    }
/*{*/}
/*{*/
/*{*/private static void highlightSubtree (AliasArray aa, HeapTree t, int i, Color c)
/*{*/{
/*{*/  algae.unHighlightAll();
/*{*/  highlightSubtreeRecursion (aa, t, i, c);
/*{*/}
 
  
    

    /**
     * Standard heapsort.
     * @param a an array of Comparable items.
     */
    public static void heapsort( Comparable [ ] a /*{*/, AliasArray aa/*}*/)
    {
/*{*/  HeapTree tree = new HeapTree (a, Color.cyan);
/*{*/  tree.setSize (a.length); tree.show();
/*{*/  algae.FRAME ("Start to build heap from array"); 
/*{*/  VisibleInteger vi = new VisibleInteger (99, Color.yellow);
/*{*/  vi.indexes (aa); vi.getRendering().setName("i"); vi.getRendering().show();
        for( int i = a.length / 2; i >= 0; i-- )  /* buildHeap */ 
/*{*/     { vi.setInt (i);
/*{*/       highlightSubtree (aa, tree, i, Color.magenta);
/*{*/       algae.FRAME ("percolate down from here");
            percDown( a, i, a.length  /*{*/, tree, aa/*}*/);
/*{*/     } algae.FRAME("Start deleting elements");
        for( int i = a.length - 1; i > 0; i-- )
        {
/*{*/       vi.setInt (i);
/*{*/       tree.setSize (i+1);
/*{*/       algae.FRAME ("deleteMax: swap max element to end");
            swapReferences( a, 0, i );            /* deleteMax */
/*{*/       tree.setSize (i);
/*{*/       algae.FRAME ("deleteMax: restore heap by percolating down");
            percDown( a, 0, i  /*{*/, tree, aa/*}*/);
        }
/*{*/  tree.hide(); vi.getRendering().hide();
/*{*/  algae.FRAME ("heap sort: done");
    }

    /**
     * Internal method for heapsort.
     * @param i the index of an item in the heap.
     * @return the index of the left child.
     */
    private static int leftChild( int i )
    {
        return 2 * i + 1;
    }

    /**
     * Internal method for heapsort that is used in
     * deleteMax and buildHeap.
     * @param a an array of Comparable items.
     * @index i the position from which to percolate down.
     * @int n the logical size of the binary heap.
     */
    private static void percDown( Comparable [ ] a, int i, int n /*{*/, HeapTree tree, AliasArray aa/*}*/)
    {
        int child;
        Comparable tmp;

/*{*/   highlightSubtree (aa, tree, i, Color.magenta);
/*{*/   algae.FRAME ("percDown percolate down from here");
/*{*/     WhiteBox wb = new WhiteBox (false);
/*{*/     wb.getRendering().show();
/*{*/     VisibleInteger vi = new VisibleInteger(99, Color.magenta); 
/*{*/     vi.getRendering().setName("i");
/*{*/     vi.indexes(aa); 
/*{*/     wb.add (vi);
/*{*/     VisibleInteger vchild = new VisibleInteger(99, Color.magenta); 
/*{*/     vchild.getRendering().setName("child");
/*{*/     vchild.indexes(aa); 
/*{*/     wb.add (vchild);
/*{*/           Alias vtmp = new Alias(vchild, Color.green); 
/*{*/           vtmp.getRendering().setName("tmp");
/*{*/           wb.add (vtmp);
        for( tmp = a[ i ]; leftChild( i ) < n; i = child )
        {
            child = leftChild( i );
/*{*/           vtmp.setAliased (tmp);
/*{*/           vi.setInt (i);
/*{*/           vchild.setInt (child);
/*{*/       highlightSubtree (aa, tree, i, Color.magenta);
/*{*/         algae.FRAME("Move down?"); 
            if( child != n - 1 && a[ child ].lessThan( a[ child + 1 ] ) )
/*{*/   {        algae.FRAME("Right child is larger"); 
                child++;
/*{*/   }   vchild.setInt (child); algae.FRAME("Swap with larger child?"); 
            if( tmp.lessThan( a[ child ] ) )
/*{*/   {        algae.FRAME("Yes, swap with larger child."); 
                a[ i ] = a[ child ];
/*{*/   }
            else
                break;
        }
/*{*/   algae.FRAME("Fill tmp into 'hole' at i");
        a[ i ] = tmp;
/*{*/   wb.getRendering().hide();
    }

    /**
     * Mergesort algorithm.
     * @param a an array of Comparable items.
     */
    public static void mergeSort( Comparable [ ] a /*{*/, AliasArray aa/*}*/)
    {
        Comparable [ ] tmpArray = new Comparable[ a.length ];

/*{*/   VisibleVector stack = new VisibleVector(Color.red, true);      
/*{*/   AliasArray visibletmp = new AliasArray (tmpArray, Color.black, false, Color.cyan, true);
/*{*/   visibletmp.getRendering().setName ("tmpArray");  visibletmp.getRendering().show();

/*{*/   algae.FRAME("Set up for recursive merge sort"); stack.getRendering().show();
        mergeSort( a, tmpArray, 0, a.length - 1 /*{*/, stack, visibletmp, aa /*}*/);
/*{*/   algae.FRAME("Completed recursive merge sort"); stack.getRendering().hide(); visibletmp.getRendering().hide();
    }

    /**
     * Internal method that makes recursive calls.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param left the left-most index of the subarray.
     * @param right the right-most index of the subarray.
     */
    private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
               int left, int right /*{*/, VisibleVector stack, AliasArray vtmpArray, AliasArray aa /*}*/)
    {
/*{*/stack.push (new IntegerPair (left, right, Color.pink, Color.red));
/*{*/algae.unHighlightAll();  aa.highlight (left, right+1, 1);
/*{*/algae.FRAME("New call to mergeSort");
        if( left < right )
        {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center /*{*/, stack, vtmpArray, aa /*}*/);
/*{*/algae.FRAME("mergeSort: returned from 1st recursive call");
            mergeSort( a, tmpArray, center + 1, right /*{*/, stack, vtmpArray, aa /*}*/);
/*{*/algae.unHighlightAll();
/*{*/Color c = a[0].getRendering().color(); 
/*{*/aa.setColor (left, center+1, 1, Color.green); 
/*{*/aa.setColor (center+1, right+1, 1, Color.magenta); 
/*{*/vtmpArray.setColor (left, right+1, 1, Color.lightGray); 
/*{*/algae.FRAME("mergeSort: returned from 2nd recursive call");
            merge( a, tmpArray, left, center + 1, right /*{*/, vtmpArray, aa /*}*/);
/*{*/algae.FRAME("mergeSort: merge completed");
/*{*/aa.setColor (left, right+1, 1, c); 
/*{*/vtmpArray.setColor (left, right+1, 1, c);