001package algs21; 002import stdlib.*; 003// Exercise 2.1.14 004/** 005 * Complete the following method to sort a deck of cards, 006 * with the restriction that the only allowed operations are to look 007 * at the values of the top two cards, to exchange the top two cards, 008 * and to move the top card to the bottom of the deck. 009 */ 010public class MyDeckSort { 011 public static void sort (MyDeck d) { 012 // TODO 013 // You must sort the Deck using only the public methods of Deck. 014 // You may not change the Deck class. 015 // It should be sufficient to use the following: 016 // d.size (); 017 // d.moveTopToBottom (); 018 // d.topGreaterThanNext (); 019 // d.swapTopTwo (); 020 // While debugging, you will want to print intermediate results. 021 // You can use d.toString() for that: 022 // StdOut.format ("i=%-3d %s\n", i, d.toString ()); 023 } 024 025 private static double time; 026 private static void countops (MyDeck d) { 027 boolean print = false; 028 if (print) StdOut.println (d.toString ()); 029 Stopwatch sw = new Stopwatch (); 030 sort (d); 031 time = sw.elapsedTime (); 032 if (print) StdOut.println (d.toString ()); 033 d.isSorted (); 034 } 035 public static void main (String[] args) { 036 int N = 10; 037 MyDeck d = new MyDeck (N); 038 countops (d); 039 //System.exit (0); // Comment this out to do a doubling test! 040 double prevOps = d.ops (); 041 double prevTime = time; 042 for (int i = 0; i < 11; i++) { 043 N *= 2; 044 d = new MyDeck (N); 045 countops (d); 046 StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, d.ops(), d.ops() / prevOps, time, time/prevTime); 047 prevOps = d.ops (); 048 prevTime = time; 049 } 050 } 051} 052 053/** 054 * The Deck class has the following API: 055 * 056 * <pre> 057 * MyDeck (int N) // create a randomized Deck of size N 058 * int size () // return the size of N 059 * int ops () // return the number of operations performed on this Deck 060 * boolean topGreaterThanNext () // compare top two items 061 * void swapTopTwo () // swap top two itens 062 * void moveTopToBottom () // move top item to bottom 063 * void isSorted () // check if isSorted (throws exception if not) 064 * </pre> 065 */ 066class MyDeck { 067 private int N; 068 private int top; 069 private long ops; 070 private int[] a; 071 072 public long ops () { 073 return ops; 074 } 075 public int size () { 076 return N; 077 } 078 public MyDeck (int N) { 079 this.N = N; 080 this.top = 0; 081 this.ops = 0; 082 this.a = new int[N]; 083 for (int i = 0; i < N; i++) 084 a[i] = i; 085 StdRandom.shuffle (a); 086 } 087 public boolean topGreaterThanNext () { 088 int i = a[top]; 089 int j = a[(top + 1) % N]; 090 ops += 2; 091 return i > j; 092 } 093 public void swapTopTwo () { 094 int i = a[top]; 095 int j = a[(top + 1) % N]; 096 a[top] = j; 097 a[(top + 1) % N] = i; 098 ops += 4; 099 } 100 public void moveTopToBottom () { 101 top = (top + 1) % N; 102 ops += 1; 103 } 104 public String toString() { 105 return toStringUnshifted() + toStringShifted(); 106 } 107 public String toStringUnshifted () { 108 if (N==0) return "[]"; 109 StringBuilder b = new StringBuilder (); 110 b.append ('['); 111 int last = (top + N - 1) % N; 112 for (int k = top; ; k = (k + 1) % N) { 113 b.append (a[k]); 114 if (k == last) return b.append (']').toString(); 115 b.append (' '); 116 } 117 } 118 public String toStringShifted () { 119 if (N==0) return "()"; 120 StringBuilder b = new StringBuilder (); 121 b.append ('('); 122 int last = N-1; 123 for (int k = 0; ; k = k + 1) { 124 b.append((top==k) ? '^' : ' '); 125 b.append (a[k]); 126 if (k == last) return b.append (')').toString(); 127 b.append (' '); 128 } 129 } 130 public void isSorted () { 131 boolean print = false; 132 long theOps = ops; // don't count the operations require by isSorted 133 for (int i = 1; i < N; i++) { 134 if (print) StdOut.format ("i=%-3d %s\n", i, toString ()); 135 if (topGreaterThanNext ()) throw new Error (); 136 moveTopToBottom (); 137 } 138 if (print) StdOut.format ("i=%-3d %s\n", N, toString ()); 139 moveTopToBottom (); 140 if (print) StdOut.format ("i=%-3d %s\n", N + 1, toString ()); 141 ops = theOps; 142 } 143}