sort.java

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

        }
/*{*/stack.pop ();
    }

    /**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
           int leftPos, int rightPos, int rightEnd /*{*/, AliasArray vtmp, AliasArray aa/*}*/)
    {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
/*{*/     WhiteBox wb = new WhiteBox (false);
/*{*/     wb.getRendering().show();
/*{*/     VisibleInteger vleftPos = new VisibleInteger(leftPos, Color.yellow); 
/*{*/     vleftPos.getRendering().setName("leftPos");
/*{*/     wb.add (vleftPos);
/*{*/     VisibleInteger vrightPos = new VisibleInteger(rightPos, Color.yellow); 
/*{*/     vrightPos.getRendering().setName("rightPos");
/*{*/     wb.add (vrightPos);
/*{*/     VisibleInteger vtmpPos = new VisibleInteger(tmpPos, Color.orange); 
/*{*/     vtmpPos.getRendering().setName("tmpPos");
/*{*/     wb.add (vtmpPos);

        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd ) /*{*/{
/*{*/algae.unHighlightAll(); 
/*{*/aa.aliasAt(leftPos).getRendering().highlight(Color.yellow);
/*{*/aa.aliasAt(rightPos).getRendering().highlight(Color.yellow);
/*{*/vleftPos.setInt (leftPos); vrightPos.setInt (rightPos); 
/*{*/vtmpPos.setInt (tmpPos); 
/*{*/vtmp.aliasAt(tmpPos).getRendering().highlight(Color.orange);
/*{*/algae.FRAME ("Main merge loop: copy smaller element");
            if( a[ leftPos ].lessThan( a[ rightPos ] ) )
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            else
                tmpArray[ tmpPos++ ] = a[ rightPos++ ]; /*{*/}

/*{*/algae.unHighlightAll(); 
/*{*/aa.highlight (leftPos, leftEnd+1, 1, Color.yellow);
/*{*/if (tmpPos < a.length) vtmp.aliasAt(tmpPos).getRendering().highlight(Color.orange);
/*{*/vleftPos.setInt (leftPos); vrightPos.setInt (rightPos); 
/*{*/vtmpPos.setInt (tmpPos); 
/*{*/algae.FRAME ("Copy rest of first half");
        while( leftPos <= leftEnd )    // Copy rest of first half
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];

/*{*/algae.unHighlightAll(); 
/*{*/aa.highlight (rightPos, rightEnd+1, 1, Color.yellow);
/*{*/if (tmpPos < a.length) vtmp.aliasAt(tmpPos).getRendering().highlight(Color.orange);
/*{*/vleftPos.setInt (leftPos); vrightPos.setInt (rightPos); 
/*{*/vtmpPos.setInt (tmpPos); 
/*{*/algae.FRAME ("Copy rest of right half");
        while( rightPos <= rightEnd )  // Copy rest of right half
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

        // Copy TmpArray back
/*{*/algae.unHighlightAll(); 
/*{*/vleftPos.setInt (leftPos); vrightPos.setInt (rightPos); 
/*{*/vtmpPos.setInt (tmpPos); 
/*{*/algae.FRAME ("Copy TmpArray back");
        for( int i = 0; i < numElements; i++, rightEnd-- )
            a[ rightEnd ] = tmpArray[ rightEnd ];
/*{*/algae.FRAME ("Done with this merge"); wb.getRendering().hide();
    }

    /**
     * Quicksort algorithm.
     * @param a an array of Comparable items.
     */
    public static void quicksort( Comparable [ ] a /*{*/, AliasArray aa/*}*/)
    {
/*{*/   VisibleVector stack = new VisibleVector(Color.red, true);      
/*{*/   algae.FRAME("Set up for recursive quicksort"); stack.getRendering().show();
       quicksort( a, 0, a.length - 1 /*{*/, stack, aa /*}*/);
/*{*/   algae.FRAME("Completed recursive quicksort"); stack.getRendering().hide();
    }

  private static final int CUTOFF = 3; // more realistically, = 10;

    /**
     * Method to swap to elements in an array.
     * @param a an array of objects.
     * @param index1 the index of the first object.
     * @param index2 the index of the second object.
     */
    public static void swapReferences( Object [ ] a, int index1, int index2 )
    {
        Object tmp = a[ index1 ];
        a[ index1 ] = a[ index2 ];
        a[ index2 ] = tmp;
    }

    /**
     * Internal quicksort method that makes recursive calls.
     * Uses median-of-three partitioning and a cutoff of 10.
     * @param a an array of Comparable items.
     * @param low the left-most index of the subarray.
     * @param high the right-most index of the subarray.
     */
    private static void quicksort( Comparable [ ] a, int low, int high /*{*/, VisibleVector stack, AliasArray aa/*}*/)
     {/*{*/stack.push (new IntegerPair (low, high, Color.pink, Color.red));
/*{*/ aa.highlight (low, high+1, 1, Color.magenta);
      if( low + CUTOFF > high ) /*{*/ {
	/*{*/algae.FRAME("Cutting off quicksort");/*}*/insertionSort( a, low, high ); /*{*/ }
        else
        {
                // Sort low, middle, high
            int middle = ( low + high ) / 2;
/*{*/     WhiteBox wb = new WhiteBox (false);
/*{*/     wb.getRendering().show();
/*{*/     VisibleInteger vlow = new VisibleInteger(low, Color.yellow); 
/*{*/     vlow.getRendering().setName("low");
/*{*/     vlow.indexes(aa); 
/*{*/     wb.add (vlow);
/*{*/     VisibleInteger vmiddle = new VisibleInteger(middle, Color.yellow); 
/*{*/     vmiddle.getRendering().setName("middle");
/*{*/     vmiddle.indexes(aa); 
/*{*/     wb.add (vmiddle);
/*{*/     VisibleInteger vhigh = new VisibleInteger(high, Color.yellow); 
/*{*/     vhigh.getRendering().setName("high");
/*{*/     vhigh.indexes(aa); 
/*{*/     wb.add (vhigh);
/*{*/     algae.FRAME ("Sort low, middle, high");
            if( a[ middle ].lessThan( a[ low ] ) )
                swapReferences( a, low, middle );
            if( a[ high ].lessThan( a[ low ] ) )
                swapReferences( a, low, high );
            if( a[ high ].lessThan( a[ middle ] ) )
                swapReferences( a, middle, high );

                // Place pivot at position high - 1
/*{*/     algae.FRAME ("Place pivot at position high - 1");
            swapReferences( a, middle, high - 1 );
            Comparable pivot = a[ high - 1 ];

                // Begin partitioning
/*{*/           Alias vpivot = new Alias(pivot, Color.green); 
/*{*/           vpivot.getRendering().setName("pivot");
/*{*/           wb.add (vpivot);
/*{*/     algae.FRAME ("Begin partitioning");
            int i, j;
/*{*/     VisibleInteger vi = new VisibleInteger(-1, Color.yellow); 
/*{*/     vi.getRendering().setName("i");
/*{*/     vi.indexes(aa); 
/*{*/     wb.add (vi);
/*{*/     VisibleInteger vj = new VisibleInteger(-1, Color.yellow); 
/*{*/     vj.getRendering().setName("j");
/*{*/     vj.indexes(aa); 
/*{*/     wb.add (vj);
/*{*/     AliasArray nulla = null;
/*{*/     vlow.indexes (nulla);
/*{*/     vmiddle.indexes (nulla);
/*{*/     vhigh.indexes (nulla);
            for( i = low, j = high - 1; ; )
            {
/*{*/        vi.setInt(i); vj.setInt(j);
/*{*/        algae.FRAME("Increase i till a[i] >= pivot");
                while( a[ ++i ].lessThan( pivot ) )
		    /*{*/{vi.setInt(i); algae.FRAME("Increasing i");}/*}*/;
/*{*/        vi.setInt(i);
/*{*/        algae.FRAME("Decrease j till a[j] <= pivot");
                while( pivot.lessThan( a[ --j ] ) )
		    /*{*/{vj.setInt(j); algae.FRAME("Decreasing j");}/*}*/;
/*{*/        vj.setInt(j);
		    if( i < j ) /*{*/{
/*{*/               algae.FRAME("Exchange a[i] and a[j]");
                    swapReferences( a, i, j );/*{*/}
                else
                    break;
/*{*/        algae.FRAME("Exchanged");
            }

                // Restore pivot
/*{*/        algae.FRAME("Restore pivot");
            swapReferences( a, i, high - 1 );

/*{*/        aa.aliasAt(i).getRendering().setColor(Color.lightGray);
/*{*/        algae.FRAME("Recursive calls"); wb.getRendering().hide(); aa.unHighlight (low, high+1, 1);
            quicksort( a, low, i - 1 /*{*/, stack, aa /*}*/);    // Sort small elements
/*{*/        aa.highlight (low, high+1, 1, Color.magenta); algae.FRAME("Return from 1st recursive call"); aa.unHighlight (low, high+1, 1);
            quicksort( a, i + 1, high /*{*/, stack, aa /*}*/);   // Sort large elements
/*{*/        aa.highlight (low, high+1, 1, Color.magenta); algae.FRAME("Return from 2nd recursive call"); 
        }
/*{*/  stack.pop(); aa.unHighlight (low, high+1, 1);
    }

    /**
     * Internal insertion sort routine for subarrays
     * that is used by quicksort.
     * @param a an array of Comparable items.
     * @param low the left-most index of the subarray.
     * @param n the number of items to sort.
     */
    private static void insertionSort( Comparable [ ] a, int low, int high )
    {
        for( int p = low + 1; p <= high; p++ )
        {
            Comparable tmp = a[ p ];
            int j;

            for( j = p; j > low && tmp.lessThan( a[ j - 1 ] ); j-- )
                a[ j ] = a[ j - 1 ];
            a[ j ] = tmp;
        }
    }

    /**
     * Quick selection algorithm.
     * Places the kth smallest item in a[k-1].
     * @param a an array of Comparable items.
     * @param k the desired rank (1 is minimum) in the entire array.
     */     
    public static void quickSelect( Comparable [ ] a, int k )
    {
        quickSelect( a, 0, a.length - 1, k );
    }

    /**
     * Internal selection method that makes recursive calls.
     * Uses median-of-three partitioning and a cutoff of 10.
     * Places the kth smallest item in a[k-1].
     * @param a an array of Comparable items.
     * @param low the left-most index of the subarray.
     * @param high the right-most index of the subarray.
     * @param k the desired rank (1 is minimum) in the entire array.
     */
    private static void quickSelect( Comparable [ ] a, int low, int high, int k )
    {
        if( low + CUTOFF > high )
            insertionSort( a, low, high );
        else
        {
                // Sort low, middle, high
            int middle = ( low + high ) / 2;
            if( a[ middle ].lessThan( a[ low ] ) )
                swapReferences( a, low, middle );
            if( a[ high ].lessThan( a[ low ] ) )
                swapReferences( a, low, high );
            if( a[ high ].lessThan( a[ middle ] ) )
                swapReferences( a, middle, high );

                // Place pivot at position high - 1
            swapReferences( a, middle, high - 1 );
            Comparable pivot = a[ high - 1 ];

                // Begin partitioning
            int i, j;
            for( i = low, j = high - 1; ; )
            {
                while( a[ ++i ].lessThan( pivot ) )
                    ;
                while( pivot.lessThan( a[ --j ] ) )
                    ;
                if( i < j )
                    swapReferences( a, i, j );
                else
                    break;
            }

                // Restore pivot
            swapReferences( a, i, high - 1 );

                // Recurse; only this part changes
            if( k <= i )
                quickSelect( a, low, i - 1, k );
            else if( k > i + 1 )
                quickSelect( a, i + 1, high, k );
        }
    }
}