JAVA package algs21;

import stdlib.*;

// Exercise 2.1.14

/**

* Complete the following method to sort a deck of cards,

* with the restriction that the only allowed operations are to look

* at the values of the top two cards, to exchange the top two cards,

* and to move the top card to the bottom of the deck.

*/

public class MyDeckSort {

public static void sort (MyDeck d) {

// TODO

// You must sort the Deck using only the public methods of Deck.

// It should be sufficient to use the following:

// d.size ();

// d.moveTopToBottom ();

// d.topGreaterThanNext ();

// d.swapTopTwo ();

// While debugging, you will want to print intermediate results.

// You can use d.toString() for that:

// StdOut.format ("i=%-3d %s ", i, d.toString ());

}

private static double time;

private static void countops (MyDeck d) {

boolean print = true;

if (print) StdOut.println (d.toString ());

d.moveTopToBottom ();

if (print) StdOut.println (d.toString ());

Stopwatch sw = new Stopwatch ();

sort (d);

time = sw.elapsedTime ();

if (print) StdOut.println (d.toString ());

d.isSorted ();

}

public static void main (String[] args) {

int N = 10;

MyDeck d = new MyDeck (N);

countops (d);

//System.exit (0); // Comment this out to do a doubling test!

double prevOps = d.ops ();

double prevTime = time;

for (int i = 0; i < 12; i++) {

N *= 2;

d = new MyDeck (N);

countops (d);

StdOut.format ("%8d %10d %5.1f [%5.3f %5.3f] ", N, d.ops (), d.ops () / prevOps, time, time / prevTime);

prevOps = d.ops ();

prevTime = time;

}

}

}

/**

* The Deck class has the following API:

*

*

 
 * MyDeck (int N) // create a randomized Deck of size N
 
 * int size () // return the size of N
 
 * int ops () // return the number of operations performed on this Deck
 
 * boolean topGreaterThanNext () // compare top two items
 
 * void swapTopTwo () // swap top two itens
 
 * void moveTopToBottom () // move top item to bottom
 
 * void isSorted () // check if isSorted (throws exception if not)
 
 * 

*/

class MyDeck {

private int N;

private int top;

private long ops;

private int[] a;

public long ops () {

return ops;

}

public int size () {

return N;

}

public MyDeck (int N) {

this.N = N;

this.top = 0;

this.ops = 0;

this.a = new int[N];

for (int i = 0; i < N; i++)

a[i] = i;

StdRandom.shuffle (a);

}

public boolean topGreaterThanNext () {

int i = a[top];

int j = a[(top + 1) % N];

ops += 2;

return i > j;

}

public void swapTopTwo () {

int i = a[top];

int j = a[(top + 1) % N];

a[top] = j;

a[(top + 1) % N] = i;

ops += 4;

}

public void moveTopToBottom () {

top = (top + 1) % N;

ops += 1;

}

public String toString () {

StringBuilder b = new StringBuilder ();

b.append ('[');

for (int i = top;;) {

b.append (a[i]);

i = (i + 1) % N;

if (i == top) return b.append (']').toString ();

b.append (", ");

}

}

public void isSorted () {

boolean print = false;

long theOps = ops; // don't count the operations require by isSorted

for (int i = 1; i < N; i++) {

if (print) StdOut.format ("i=%-3d %s ", i, toString ());

if (topGreaterThanNext ()) throw new Error ();

moveTopToBottom ();

}

if (print) StdOut.format ("i=%-3d %s ", N, toString ());

moveTopToBottom ();

if (print) StdOut.format ("i=%-3d %s ", N + 1, toString ());

ops = theOps;

}

}