CSC300 / CSC402: MyDeckSort Hints [3/3] Previous pageContents

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.)

Previous pageContents