/*
 * @(#)SwapSortAlgorithm.java	1.0 95/06/26 Jason Harrison
 *
 * Copyright (c) 1995 University of British Columbia
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies. Please refer to the file "copyright.html"
 * for further important copyright and licensing information.
 *
 * UBC MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. UBC SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 */

/**
 * A swap sort demonstration algorithm
 *
 *  We know how the data was constructed and can use this to our advantage.
 *  THIS IS NOT A SORT!  DO NOT USE THIS ROUTINE FOR REAL APPLICATIONS.
 *  IT IS ONLY A DEMONSTRATION OF HOW LONG IT TAKES JAVA TO SWAP N ELEMENTS.
 *  
 *  EQUIVALENT CODE:
 *     for (int i = 0; i < a.length; i++ ) {
 *         a[i] = i;
 *     }
 *
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author Jason Harrison@cs.ubc.ca
 * @version 	1.0, 26 Jun 1995
 *
 */
class SwapSortAlgorithm extends SortAlgorithm {
    void sort(int a[]) throws Exception {
	int max = a[0];

        /*
         *  The array a holds values from 0 to max where a.length = max / f.
         *  Here we find max.
         */
	for (int i = 1; i < a.length; i++) {
            if (max < a[i]) {
                max = a[i];
	    }
	}

        /*
         *  Now find f, the scaling factor for drawing the contents of
         *  the array a.  The correct value for a[j] is j / f.
         */
	double f = ((double) a.length - 1.0) / (double) max;

        /*
         *  Each time through the loop we remove a value, find it's correct
         *  position in the array, and place it there.  The displaced 
         *  value becomes the next value to place.
         */
	int T = a[0];
	for (int i = 0; i < a.length; i++) {
	    if (stopRequested) {
		return;
            }
	    int S;
	    S = a[(int) (T * f)];
	    a[(int) (T * f)] = T;
	    T = S;
	    pause((int) (S * f), (int) (T * f));
        }
    }
}