/*
 * @(#)ShellSortAlgorithm.java	1.1 2000/04/12 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 shell sort demonstration algorithm
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 * Note: Invented by Donald Lewis Shell [CACM, July, 1959, pages 30-32]
 * @author Jason Harrison@cs.ubc.ca
 * @version 	1.0, 23 Jun 1995
 * @version 	1.1, 12 Apr 2000 
 *              -- fixed java.lang.ArrayIndexOutOfBoundsException
 *                 Joel Berry <jmbshifty@yahoo.com> found this bug
 */

/* http://www.auto.tuwien.ac.at/~blieb/woop/shell.html 
 *
 * Shellsort is a simple extension of insertion sort which gains speed
 * by allowing exchanges of elements that are far apart. The idea is
 * to rearrange the array to give it the property that every hth
 * element (starting anywhere) yields a sorted array. Such an array
 * is said to be h-sorted.
 *
 * By h-sorting for some large values of h, we can move elements in
 * the array long distances and thus make it easier to h-sort for
 * smaller values of h. Using such a procedure for any sequence of
 * values h which ends in 1 will produce a sorted array.
 */

class ShellSortAlgorithm extends SortAlgorithm {
    void sort(int a[]) throws Exception {
	int h = 1;
        /* 
         * find the largest h value possible 
         */
        while ((h * 3 + 1) < a.length) {
	    h = 3 * h + 1;
	}

        /* 
         * while h remains larger than 0 
         */
        while( h > 0 ) {
            /* 
             * for each set of elements (there are h sets)
             */
            for (int i = h - 1; i < a.length; i++) {
                /* 
                 * pick the last element in the set
                 */
                int B = a[i];
                int j = i;
                /*
                 * compare the element at B to the one before it in the set
                 * if they are out of order continue this loop, moving
                 * elements "back" to make room for B to be inserted.
                 */
                for( j = i; (j >= h) && (a[j-h] > B); j -= h) {
                    if (stopRequested) {
		        return;
                    }
                    a[j] = a[j-h];
		    pause(i,j);
                }
                /*
                 *  insert B into the correct place
                 */
                a[j] = B;
	        pause(j);
            }
            /* 
             * all sets h-sorted, now decrease set size
             */
            h = h / 3;
        }
    }
}