/*
 *      An unbelievably inefficient sorting algorithm
 *
 *      To sort 10 pseudo-random integers:
 *
 *          java SlowSort 10
 *
 *      To sort an int array toSort:
 *
 *          SlowSort.sort (toSort);
 *
 * @author William D Clinger
 *
 */

public class SlowSort {

    /** @param toSort is the int array to be sorted in place
     */

    static void sort (int[] toSort) {
	SlowSort ss = new SlowSort (toSort);
	ss.sort();
    }

    private int[] a;                // array to sort
    private int[] sortedarray;      // will become sorted array

    private SlowSort (int[] toSort) {
        this.a = (int[]) toSort.clone();
        this.sortedarray = toSort;
    }

    static void main (String[] args) {
	if (args.length == 0) {
	    System.err.println ("Usage: java SlowSort n");
	    System.exit(1);
	}
        int n = (Integer.decode (args[0])).intValue();
        benchmark (n);
    }

    private static void benchmark (int n) {
        SlowSort ss = new SlowSort (testCase (n));
        ss.benchmark();
    }

    /*  Returns a test array initialized with pseudo-random data.  */

    private static int[] testCase (int n) {
        int[] a = new int [n];
        for (int i = 0; i < n; i = i + 1)
            a[i] = Math.round ((float) (1000.0 * Math.random ()));
        return a;
    }

    // Copies a sorted version of this.a to this.sortedarray.

    private void sort () {
        generatePermutations (a.length);
    }

    // Generates all permutations of the array a
    // in a grey code order, using Zaks's algorithm:
    //   Shmuel Zaks: A New Algorithm for Generation of Permutations.
    //   BIT 24(2): 196-204 (1984).
    // Checks each permutation to see if it's sorted.
    // When a sorted permutation is found, copies it to sortedarray.

    private void generatePermutations (int n) {
	checkSorted();
        if (n > 1) {
            int i = 0;
            while (i < n - 1) {
                generatePermutations (n - 1);
                flip (n);
                i = i + 1;
            }
            generatePermutations (n - 1);
        }
    }

    // Reverses the first n elements of a.

    private void flip (int n) {
        int i = 0;

        // Loop invariant:
        //   0 <= 2 * i <= n
        //   this.a is a permutation of its original contents
        //   during the execution of this call to flip,
        //     a[0] through a[i-1] have been swapped with
        //     a[n-1] through a[n-i].

        while (i < n / 2) {
            swap (i, n - i - 1);
            i = i + 1;
        }
        checkSorted();
    }

    // Checks to see whether the array a is sorted.
    // If it is, then the sorted array is copied to sortedarray.

    private void checkSorted () {
        boolean ok = true;
        int j = a.length - 1;

        // Loop invariant:
        //   0 <= j < a.length
        //   ok is true if and only if
        //     a[j] through a[a.length - 1] are in sorted order

        while (j > 0) {
            j = j - 1;
            if (a[j] > a[j+1])
                ok = false;
        }

        if (ok) {
            int n = a.length - 1;

            // Loop invariant:
            //   -1 <= n < a.length
            //   a[n+1] through a[a.length - 1] are equal to
            //     sortedarray[n+1] through sortedarray[a.length - 1]

            while (n >= 0) {
                sortedarray[n] = a[n];
                n = n - 1;
            }
        }
    }

    // Swaps a[i] with a[j].

    private void swap (int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private void benchmark () {
        int n = a.length;
        int checksum = 0;
        boolean ok = true;
        System.out.print (startMsg);

        for (int i = 0; i < n; i = i + 1)
            checksum = checksum + a[i];

        sort ();

        for (int i = 0; i < n; i = i + 1) {
            checksum = checksum - sortedarray[i];
        }
        for (int i = 1; i < n; i = i + 1) {
            if (sortedarray[i-1] > sortedarray[i])
                ok = false;
            else;
        }

        if (checksum != 0)
            System.out.print (wrongContentsMsg);
        else if (! ok)
            System.out.print (wrongOrderMsg);
        else System.out.print (okMsg);
        System.out.println();

        for (int i = 0; i < n; i = i + 1) {
            System.out.print (sortedarray[i]);
            System.out.print (" ");
        }
        System.out.println();
    }

    static final String startMsg
        = "Slow sort...";
    static final String wrongContentsMsg
        = "failed because the contents are incorrect.";
    static final String wrongOrderMsg
        = "failed because the array is not sorted.";
    static final String okMsg
        = "succeeded.";

}