CSC300: Homework (MyDeckSort)

+ Read Algorithms through the end of 2.5 (you can skip 2.2,2.3).

+ Do the MyDeckSort assignment and hand in MyDeckSort.java
  Your goal is to implement the sort(MyDeck) method of MyDeckSort.
  You can use only the public method of MyDeck.
  You should not change the functionality of MyDeck.
  Hand in only MyDeckSort.java

  This is based on problem 2.1.14 from the text.

  To get started, download MyDeckSort from d2l.
  You need only edit the MyDeckSort class.
  Leave the Deck class (in the same file) alone.

  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)

file:MyDeckSort.java [source] [doc-public] [doc-private]

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.
    // You may not change the Deck class.
    // 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\n", i, d.toString ());
  }

  private static double time;
  private static void countops (MyDeck d) {
    boolean print = false;
    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 < 11; i++) {
      N *= 2;
      d = new MyDeck (N);
      countops (d);
      StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, d.ops(), d.ops() / prevOps, time, time/prevTime);
      prevOps = d.ops ();
      prevTime = time;
    }
  }
}

/**
 * The Deck class has the following API:
 *
 * <pre>
 * 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)
 * </pre>
 */
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() {
    return toStringUnshifted() + toStringShifted();
  }
  public String toStringUnshifted () {
    if (N==0) return "[]";
    StringBuilder b = new StringBuilder ();
    b.append ('[');
    int last = (top + N - 1) % N;
    for (int k = top; ; k = (k + 1) % N) {
      b.append (a[k]);
      if (k == last) return b.append (']').toString();
      b.append (' ');
    } 
  }
  public String toStringShifted () {
    if (N==0) return "()";
    StringBuilder b = new StringBuilder ();
    b.append ('(');
    int last = N-1;
    for (int k = 0; ; k = k + 1) {
      b.append((top==k) ? '^' : ' ');
      b.append (a[k]);
      if (k == last) 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\n", i, toString ());
      if (topGreaterThanNext ()) throw new Error ();
      moveTopToBottom ();
    }
    if (print) StdOut.format ("i=%-3d %s\n", N, toString ());
    moveTopToBottom ();
    if (print) StdOut.format ("i=%-3d %s\n", N + 1, toString ());
    ops = theOps;
  }
}

MyDeckSort Hints [3/3]

Deck d has d.size() cards. You can go through the whole deck using a loop:

for (int i=0; i<d.size(); i++) {
  ...
  d.moveTopToBottom ()
}

You can also go through the deck d.size() times!

for (int i=0; i<d.size(); i++) {
  for (int j=0; j<d.size(); j++) {
    ...
    d.moveTopToBottom ()
  }
}

You can do different things at different point of the process!

for (int i=0; i<d.size(); i++) {
  for (int j=0; j<i; j++) {
    ...
    d.moveTopToBottom ()
  }
  for (int j=i; j<d.size(); j++) {
    ...
    d.moveTopToBottom ()
  }
}

If you want to print intermediate results, you can do it like this:

boolean print = true;
for (int i=0; i<d.size(); i++) {
  if (d.topGreaterThanNext()) {
    d.swapTopTwo ();
  }
  d.moveTopToBottom ();
  if (print) StdOut.format ("i=%-3d %s\n", i, d.toString ());
}

Try sorting a list of 4 numbers using these capabilities... Start with the list that is sorted except that the min is at the end. It will work something like this: (In the square brackets, I am showing "deck of cards" with the top first. In the parenthesis, I am showing the underlying array, with the top element indidcated by a preceding ^.)

[3 2 1 0](^3  2  1  0)
            [3 2 1 0](^3  2  1  0)
i=1   j=1   [3 1 0 2]( 2 ^3  1  0)
i=1   j=2   [3 0 2 1]( 2  1 ^3  0)
i=1   j=3   [3 2 1 0]( 2  1  0 ^3)
i=1         [2 1 0 3](^2  1  0  3)
i=2   j=1   [2 0 3 1]( 1 ^2  0  3)
i=2   j=2   [2 3 1 0]( 1  0 ^2  3)
i=2   j=3   [3 1 0 2]( 1  0  2 ^3)
i=2         [1 0 2 3](^1  0  2  3)
i=3   j=1   [1 2 3 0]( 0 ^1  2  3)
i=3   j=2   [2 3 0 1]( 0  1 ^2  3)
i=3   j=3   [3 0 1 2]( 0  1  2 ^3)
i=3         [0 1 2 3](^0  1  2  3)
[0 1 2 3](^0  1  2  3)

If you look just at the iterations of the outer loop, you have:

            [3 2 1 0](^3  2  1  0)
i=1         [2 1 0 3](^2  1  0  3) // 3 in proper place
i=2         [1 0 2 3](^1  0  2  3) // 2 in proper place
i=3         [0 1 2 3](^0  1  2  3) // 1 in proper place

Each iteration of the outer loop gets (at least) one element in the proper place. (Note that if N-1 elements are in the proper place, then the Nth element is also going to be in the proper place.)

Revised: 2008/03/17 13:01