/*
 * @(#)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. <br />
 *  <br />
 *  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.<br />
 *  <br />
 *  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.<br />
 *  <br />
 *  Note: Invented by Donald Lewis Shell [CACM, July, 1959, pages 30-32]<br />
 *  <br />
 *  Author Jason Harrison, his version 1.1, 12 Apr 2000 <br />
 *  <br />
 *  Modif. 15.11.2005, Albrecht Weinert (a-weinert.de) :<br />
 *  {@link SortApplet.SortAlgorithm} + Kleinigkeiten.<br />  
 *  <br />
 *  @author   Albrecht Weinert
 *  @version  V.161, 28.05.2011
 */
public final class ShellSortAlgorithm extends SortApplet.SortAlgorithm {
 
   @Override void sort(int[] a)  {
      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 be = 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] > be); j -= h) {
               if (stopRequested) return;
               a[j] = a[j-h];
               pause(i,j);
            }
            // insert B into the correct place
            a[j] = be;
            pause(j);
         }
         // all sets h-sorted, now decrease set size
         h = h / 3;
      }
   } // sort(int[])
   
}