/*
 * @(#)EQSortAlgorithm.java   1.0 95/06/26 Jim Boritz
 *
 * Copyright (c) 1995 UBC Microsystems, Inc. All Rights Reserved.
 *
 * 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.
 */

/** An enhanced quick sort demonstration algorithm. <br />
 *  <br />
 *  SortAlgorithm.java, Thu Oct 27 10:32:35 1994<br />
 *  Author: Jim Boritz, his version: 1.0, 26 Jun 1995<br />
 *  <br />
 *  21 Jun 1996: Modified code based on comments from Paul Haeberli, and
 *              Peter Schweizer. Used Daeron Meyer's code for the
 *              new pivoting code.<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 EQSortAlgorithm extends SortApplet.SortAlgorithm {
   
   void brute(int[] a, int lo, int hi) {
      if (hi - lo == 1) {
         if (a[hi] < a[lo]) {
            int T = a[lo];
            a[lo] = a[hi];
            a[hi] = T;
            pause();
         }
      }
      if (hi - lo == 2) {
         int pmin = a[lo] < a[lo + 1] ? lo : lo + 1;
         pmin = a[pmin] < a[lo + 2] ? pmin : lo + 2;
         if (pmin != lo) {
            int temp = a[lo];
            a[lo] = a[pmin];
            a[pmin] = temp;
            pause();
         }
         brute(a, lo+1, hi);
      }
      if ((hi - lo) == 3) {
         int pmin = a[lo] < a[lo + 1] ? lo : lo + 1;
         pmin = a[pmin] < a[lo + 2] ? pmin : lo + 2;
         pmin = a[pmin] < a[lo + 3] ? pmin : lo + 3;
         if (pmin != lo) {
            int temp = a[lo];
            a[lo] = a[pmin];
            a[pmin] = temp;
            pause();
         }
         int pmax = a[hi] > a[hi - 1] ? hi : hi - 1;
         pmax = a[pmax] > a[hi - 2] ? pmax : hi - 2;
         if (pmax != hi) {
            int temp = a[hi];
            a[hi] = a[pmax];
            a[pmax] = temp;
            pause();
         }
         brute(a, lo+1, hi-1);
      }
   } // brute(int[], int, ..
   
   void sort(int[] a, int lo0, int hi0) {
      int lo = lo0;
      int hi = hi0;
      pause(lo, hi);
      if (hi - lo <= 3) {
         brute(a, lo, hi);
         return;
      }
      
      /*
       *  Pick a pivot and move it out of the way
       */
      int pivot = a[(lo + hi) / 2];
      a[(lo + hi) / 2] = a[hi];
      a[hi] = pivot;
      
      while( lo < hi ) {
         /*  Search forward from a[lo] until an element is found that
          *  is greater than the pivot or lo >= hi 
          */
         while (a[lo] <= pivot && lo < hi) lo++;
 
         /*  Search backward from a[hi] until element is found that
          *  is less than the pivot, or hi <= lo 
          */
         while (pivot <= a[hi] && lo < hi ) hi--;
         
         /*
          *  Swap elements a[lo] and a[hi]
          */
         if( lo < hi ) {
            int temp = a[lo];
            a[lo] = a[hi];
            a[hi] = temp;
            pause();
         }
      }
      
      // Put the median in the "center" of the list
      a[hi0] = a[hi];
      a[hi] = pivot;
      
      /*  Recursive calls, elements a[lo0] to a[lo-1] are less than or
       *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
       *  pivot.
       */
      sort(a, lo0, lo-1);
      sort(a, hi+1, hi0);
   } // sort(int[], int, int)
   
   @Override void sort(int[] a) {
      sort(a, 0, a.length-1);
   }
} // class EQSortAlgorithm (15.11., 27.11.2005, A.W.)