001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
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;
}
}
|
