# CSC300: Lecture 8 (Elementary Sorts, Objects as Data: Comparable, Objects as Functions: Comparator (1.2, 2.1, 2.5))

 Contents [0/6]

 Homework [1/6] XSortCards0 [2/6] XCardSimple [3/6] XSortCards1 [4/6] XCard [5/6] XSortCards2 [6/6]

 Homework [1/6]

• Read Algorithms 1.4 again. Also read 2.1. Also read the discussion of stability in section 2.5 (page 341 in the third printing of the text).

• Complete MyDequeUsingStacks.java

 XSortCards0 [2/6]

 file:XSortCards0.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ``` ```package algs21; import stdlib.*; import java.util.Comparator; public class XSortCards0 { public static void show (String[] d) { for (int i=0; i<4; i++) { for (int j=0; j<13; j++) { StdOut.format ("%3s ", d[i*13+j]); } StdOut.println (); } StdOut.println (); } private static class CardComparator implements Comparator { private static char suit (String s) { return s.charAt (s.length () - 1); } private static int rank (String s) { char rank = s.charAt (0); switch (rank) { case '1' : return 10; case 'J' : return 11; case 'Q' : return 12; case 'K' : return 13; case 'A' : return 14; default: return rank - '0'; } } public int compare (String c1, String c2) { if (rank(c1) < rank(c2)) return -1; if (rank(c1) > rank(c2)) return +1; if (suit(c1) < suit(c2)) return -1; if (suit(c1) > suit(c2)) return +1; return 0; } } public static void main (String[] args) { String[] d = { "2C", "3C", "4C", "5C", "6C", "7C", "8C", "9C", "10C", "JC", "QC", "KC", "AC", "2D", "3D", "4D", "5D", "6D", "7D", "8D", "9D", "10D", "JD", "QD", "KD", "AD", "2H", "3H", "4H", "5H", "6H", "7H", "8H", "9H", "10H", "JH", "QH", "KH", "AH", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "10S", "JS", "QS", "KS", "AS" }; show (d); StdRandom.shuffle (d); show (d); Insertion.sort (d); show (d); Insertion.sort (d, new CardComparator ()); show (d); String c1 = "@E"; d[0] = c1; StdRandom.shuffle (d); Insertion.sort (d, new CardComparator ()); show (d); } } ```

 XCardSimple [3/6]

 file:XCardSimple.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ``` ```package algs12; import stdlib.*; public class XCardSimple implements Comparable { public static enum Rank { TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE } public static enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES } public final Rank rank; public final Suit suit; public XCardSimple (Rank r, Suit s) { this.rank = r; this.suit = s; } public String toString () { return rank + " of " + suit; } public int compareTo (XCardSimple that) { if (this.suit.compareTo (that.suit) < 0) return -1; if (this.suit.compareTo (that.suit) > 0) return +1; if (this.rank.compareTo (that.rank) < 0) return -1; if (this.rank.compareTo (that.rank) > 0) return +1; return 0; } public boolean equals (Object that) { if (that == null) return false; if (this.getClass() != that.getClass()) return false; // This does the right thing but is inefficient. // Since equals may be used more than compareTo, there is usually a separate implementation. return 0 == this.compareTo ((XCardSimple) that); } public static void main (String[] args) { Suit s1 = Suit.CLUBS; //Suit s2 = new Suit(); XCardSimple c1 = new XCardSimple(Rank.ACE, Suit.SPADES); XCardSimple c2 = new XCardSimple(Rank.ACE, Suit.SPADES); StdOut.println (c1 + (c1.equals(c2) ? " equals " : " does not equal ") + c2); } } ```

 XSortCards1 [4/6]

 file:XSortCards1.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` ```package algs21; import stdlib.*; import algs12.XCard; public class XSortCards1 { public static void show (XCard[] d) { for (int i=0; i<4; i++) { for (int j=0; j<13; j++) { StdOut.format ("%3s ", d[i*13+j]); } StdOut.println (); } StdOut.println (); } public static void main (String[] args) { XCard[] d = XCard.newDeck (); show (d); StdRandom.shuffle (d); show (d); Insertion.sort (d); show (d); } } ```

 XCard [5/6]

 file:XCard.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 ``` ```package algs12; import stdlib.*; public class XCard implements Comparable { public static enum Rank { TWO("2"), THREE("3"), FOUR("4"), FIVE("5"), SIX("6"), SEVEN("7"), EIGHT("8"), NINE("9"), TEN("10"), JACK("J"), QUEEN("Q"), KING("K"), ACE("A"); private final String name; private Rank (String name) { this.name = name; } public String toString () { return name; } } public static enum Suit { CLUBS("C"), DIAMONDS("D"), HEARTS("H"), SPADES("S"); private final String name; private Suit (String name) { this.name = name; } public String toString () { return name; } } public final Rank rank; public final Suit suit; private XCard (Rank r, Suit s) { this.rank = r; this.suit = s; } public String toString () { return rank.toString () + suit.toString (); } public int compareTo (XCard that) { if (this.suit.compareTo (that.suit) < 0) return -1; if (this.suit.compareTo (that.suit) > 0) return +1; if (this.rank.compareTo (that.rank) < 0) return -1; if (this.rank.compareTo (that.rank) > 0) return +1; return 0; } private static XCard[] protoDeck = new XCard[52]; static { // This is how you run a loop to initialize a static variable. int i = 0; for (Suit s : Suit.values ()) for (Rank r : Rank.values ()) { protoDeck[i] = new XCard (r, s); i++; } } public static XCard[] newDeck () { XCard[] deck = new XCard[protoDeck.length]; for (int i = 0; i

 XSortCards2 [6/6]

 file:XSortCards2.java [source] [doc-public] [doc-private]
 ``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ``` ```package algs21; import stdlib.*; import algs12.XCard; import java.util.Comparator; public class XSortCards2 { public static void show (XCard[] d) { for (int i=0; i<4; i++) { for (int j=0; j<13; j++) { StdOut.format ("%3s ", d[i*13+j]); } StdOut.println (); } StdOut.println (); } private static class RankFirstComparator implements Comparator { public int compare (XCard c1, XCard c2) { if (c1.rank.compareTo (c2.rank) < 0) return -1; if (c1.rank.compareTo (c2.rank) > 0) return +1; if (c1.suit.compareTo (c2.suit) < 0) return -1; if (c1.suit.compareTo (c2.suit) > 0) return +1; return 0; } } public static void main (String[] args) { XCard[] d = XCard.newDeck (); show (d); StdRandom.shuffle (d); show (d); Insertion.sort (d); show (d); Insertion.sort (d, new RankFirstComparator ()); show (d); } } ```

Revised: 2008/03/17 13:01