CSC300 / CSC402: Comparable and Comparator

Contents [0/7]

Comparison [1/7]
Cards as Strings [2/7]
Defining a Comparator [3/7]
Natural Order [4/7]
Defining a Comparable [5/7]
A fully fleshed-out Card class [6/7]
Using the Card class [7/7]

(Click here for one slide per page)


Comparison [1/7]

Three aspects of comparison-based sorting:

  1. the data to be sorted
  2. how to compare two elements? (comparison algorithm)
  3. how to sort? (sorting algorithm)

Cards as Strings [2/7]

file:XSortCards00.java [source]
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
 
package algs21;
import stdlib.*;

public class XSortCards00 {
  public static void show (String title, String[] d) {
    StdOut.println (title);
    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) {
    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 ("Initial", d);
    StdRandom.shuffle (d);
    show ("Shuffled", d);
    Selection.sort (d);
    show ("Sorted", d);
  }
}

Initial
 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 

Shuffled
 4S  JH  9S  3S 10C  2C  5C  4H  KC  6H  5D  8D  6C 
 KS 10H  AS  7H  AD 10D  6D  KD  5S  JS 10S  8H  7C 
 9D  3H  9H  QH  JD  QS  7S  QD  2H  2D  AC  3C  6S 
 9C  5H  4C  4D  8C  8S  JC  KH  QC  7D  3D  AH  2S 

Sorted
10C 10D 10H 10S  2C  2D  2H  2S  3C  3D  3H  3S  4C 
 4D  4H  4S  5C  5D  5H  5S  6C  6D  6H  6S  7C  7D 
 7H  7S  8C  8D  8H  8S  9C  9D  9H  9S  AC  AD  AH 
 AS  JC  JD  JH  JS  KC  KD  KH  KS  QC  QD  QH  QS

Defining a Comparator [3/7]

file:XSortCards0.java [source]
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
 
package algs21;
import stdlib.*;
import java.util.Comparator;

public class XSortCards0 {
  public static void show (String title, String[] d) {
    StdOut.println (title);
    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<String> {
    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 (suit(c1) < suit(c2)) return -1;
      if (suit(c1) > suit(c2)) return +1;
      if (rank(c1) < rank(c2)) return -1;
      if (rank(c1) > rank(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 ("Initial", d);
    StdRandom.shuffle (d);
    show ("Shuffled", d);
    Insertion.sort (d);
    show ("Sort1", d);
    Insertion.sort (d, new CardComparator ());
    show ("Sort2", d);
    
    String c1 = "@E";
    d[0] = c1;
    StdRandom.shuffle (d);
    Insertion.sort (d, new CardComparator ());
    show ("Sort3", d);
  }
}

Sort1
10C 10D 10H 10S  2C  2D  2H  2S  3C  3D  3H  3S  4C 
 4D  4H  4S  5C  5D  5H  5S  6C  6D  6H  6S  7C  7D 
 7H  7S  8C  8D  8H  8S  9C  9D  9H  9S  AC  AD  AH 
 AS  JC  JD  JH  JS  KC  KD  KH  KS  QC  QD  QH  QS 

Sort2
 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 

Sort3
 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  @E 
 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

Natural Order [4/7]

Natural order String is dictionary order

External order specified by CardComparator

Defining a Comparable [5/7]

file:XCardSimple.java [source]
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<XCardSimple> {
  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);
  }
}

A fully fleshed-out Card class [6/7]

file:XCard.java [source]
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
69
70
71
72
73
74
75
76
77
78
79
80
81
 
package algs12;
import stdlib.*;

public class XCard implements Comparable<XCard> {
  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 Rank rank;
  public 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;
  }
  /* 
   * NOTE: We don't need to override Object.equals 
   *  because there is only one possible instance of each card.
   *  But if you did do it, it would look like this:
   */
  //public boolean equals (Object that) {
  //  if (that == null)
  //    return false;
  //  if (this.getClass() != that.getClass())
  //    return false;
  //  XCard thatCard = (XCard) that;
  //  return (this.rank == thatCard.rank) && (this.suit == thatCard.suit);
  //}

  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<protoDeck.length; i++)
      deck[i] = protoDeck[i];
    return deck;
  }

  public static void main (String[] args) {
    XCard[] d1 = XCard.newDeck ();  final XCard c1 = d1[51];
    XCard[] d2 = XCard.newDeck ();  final XCard c2 = d2[50];
    StdOut.println (c1 + (c1.equals(c2) ? " equals " : " does not equal ") + c2);
  }
}

Using the Card class [7/7]

file:XSortCards2.java [source]
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
 
package algs21;
import stdlib.*;
import algs12.XCard;
import java.util.Comparator;

public class XSortCards2 {
  public static void show (String title, XCard[] d) {
    StdOut.println (title);
    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<XCard> {
    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 ("Initial", d);
    StdRandom.shuffle (d);
    show ("Shuffled", d);
    Insertion.sort (d);
    show ("Sort1", d);
    Insertion.sort (d, new RankFirstComparator ());
    show ("Sort2", d);
  }
}

Sort1
 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 

Sort2
 2C  2D  2H  2S  3C  3D  3H  3S  4C  4D  4H  4S  5C 
 5D  5H  5S  6C  6D  6H  6S  7C  7D  7H  7S  8C  8D 
 8H  8S  9C  9D  9H  9S 10C 10D 10H 10S  JC  JD  JH 
 JS  QC  QD  QH  QS  KC  KD  KH  KS  AC  AD  AH  AS