/*
 * Optimizing the World's Worst Sorting Algorithm
 *
 * Backtracking to the rescue!
 *
 * World's worst sorting algorithm:  examine all possible permutations
 * of the array contents and select the one that has NO elements out
 * of order.  Note that this is an OPTIMAL method if the data are
 * already sorted:  n-1 comparisons to termination if the permutations
 * are examined as they are generated.
 *
 * Backtracking optimization:  as each permutation is being generated,
 * examine at position k whether each candidate contents introduces
 * an out-of-order situation.  If it does, abandon all permutations
 * that have this front end.  Otherwise recurse to position k+1.
 *
 * Author:  Timothy Rolfe
 */

public class BackSort
{
   // Test whether x[posn] is correctly positioned w.r.t. x[posn-1]
   static boolean test ( Comparable[] x, int posn )
   {  if (posn == 0) return true;    // true if there IS no predecessor
      else           return x[posn-1].compareTo(x[posn]) <= 0;
   }

   static void swap ( Comparable[] x, int p, int q )
   {  Comparable tmp = x[p]; x[p] = x[q]; x[q] = tmp;  }

   // NEARLY the world's WORST sorting algorithm:
   //
   // Examine all permutations of elements, but trim the permutations
   // through backtracking.
   static void backSort ( Comparable[] x )
   {  backSort(x, 0);  }

   static boolean backSort ( Comparable[] x, int posn )
   {  int size = x.length;
   // We have a solution if we've moved past the right end of x[]
      if ( posn == size )
         return true;
      else
      {  Comparable tmp;     // Hold cell contents during rotation
         int        k;       // Loop variable

         for ( k = posn; k < size; k++ )
         {//Swap next candidate into [posn]
            swap (x, k, posn);
         // then test:  if success, we're done
            if ( test(x, posn) && backSort (x, posn+1) )
                  return true;
         }
      // The loop above ends with the array [posn ... size-1] having
      // undergone a right-rotation by one element.  It is critical
      // that this be undone so that when we backtrack, the proper
      // value is in place to be used next for [posn-1].
         tmp = x[posn];
         for ( k = posn+1; k < size; k++ )
            x[k-1] = x[k];
         x[size-1] = tmp;
      }
      return false;
   }

   // Completely randomize positions within x[] from [0] to [n-1]
   static void shuffle (Comparable[] x, int n)
   {  while ( n > 1 )
      {  int k = (int) (Math.random() * n--);

         swap (x, k, n);
      }
   }

   static public void main ( String[] args )
   {  Data    x[];      // Array to be sorted
      int     size,     // Requested size for x
              k;        // Loop variable
      long    fact = 1;
      long    nCmp;
      java.util.Scanner console = new java.util.Scanner(System.in);

      System.out.print ("Size:  ");
      if ( args.length == 0 )
         size = console.nextInt();
      else
      {  size = Integer.parseInt(args[0]);  System.out.println(size);  }

      x = new Data[size];
      for ( k = 0; k < size;  )
      {  x[k] = new Data(size - k);
         fact *= ++k;
      }

      System.out.println (size + " gives " + fact + " possible sequences.");

   // The Data objects are reversed by the for loop above
      nCmp = Data.nCompares();    // Zero out the counter
      backSort(x);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Reversed data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.println (" --- " + nCmp + " comparisons.");

   // Completely randomize the data
      shuffle (x, size);
      nCmp = Data.nCompares();    // Zero out the counter
      backSort(x);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Random data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.println (" --- " + nCmp + " comparisons.");

   // Data left sorted from previous run.
      nCmp = Data.nCompares();    // Zero out the counter
      backSort(x);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Sorted data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.println (" --- " + nCmp + " comparisons.");
   }

   static class Data implements Comparable
   {  static private long nCompares = 0;
      private int value;
   
//    Default constructor
      Data ()
      {  value = 0;  }
   
//    Initializing constructor
      Data (int value)
      {  this.value = value;  }
   
//    Copy constructor
      Data (Data item)
      {  value = item.value;  }
   
      public void set(int value)
      {  this.value = value;  }
   
      public int  get()
      {  return value;  }
   
      public String toString()
      {  return Integer.toString(value);  }
   
      public int compareTo ( Object right )
      {  nCompares++;
         return this.value - ((Data)right).value;
      }
   
      static public long nCompares ()
      {  long temp = nCompares;
   
         nCompares = 0;
         return temp;
      }
   }
}
/* Specimen execution of the above code:

Size:  16
16 gives 20922789888000 possible sequences.
Reversed data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 524272 comparisons.
Random data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 357945 comparisons.
Sorted data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 15 comparisons.
*/