Methods in this group of examples assume that the type to be sorted
implements Comparable interface. Sorting Comprable
objects by their compareTo method is refered to as "sorting
accoring to their natural ordering". We start by demonstrating a Comparable
version of Card and use a standard sorting method Arrays.sort.
The rest of the examples show how to write your own sorting methods in Java.
/**
* The class represents a playing card
* @author 2101 Fall 2011 class
* Post-authors: Kevin Viratyosin, Miles Taylor, Nick Fox
*/
public class Card implements Comparable<Card>{
private String suit; // the card's suit, one of Hearts, Diamonds,
// Clubs, and Spades
private String value; // the card's value, one of 2,3,4,5,6,7,8,9,10,J,Q,K,A
private int numericValue;
public final static String [] values = {"2","3","4","5","6","7","8","9","10","J","Q","K","A"};
public final static String [] suits = {"Clubs", "Diamonds", "Hearts", "Spades"};
/**
* The constructor creates a card with the given suit and value
*/
public Card(String suit, String value) throws InvalidCardException {
for(int i = 0; i < values.length; ++i) {
if (value.equals(values[i])) {
numericValue = i + 2;
break;
}
}
if (numericValue == 0) {
throw new InvalidCardException(value, "value");
}
// Determines if the suit given is valid
boolean validSuit = false;
for(int i = 0; i < suits.length; ++i) {
if (suit.equals(suits[i])) {
validSuit = true;
}
}
if ( !validSuit ) {
throw new InvalidCardException(suit, "suit");
}
this.suit = suit;
this.value = value;
}
/**
* The method returns the card's suit
*/
public String getSuit(){
return suit;
}
/**
* The method returns the card's value in a symbolic form,
* such as "5" or "K" (for King)
**/
public String getValue(){
return value;
}
/**
* The method returns the cards value as an int, such
* as 5 for a value "5" and 14 for a value "A" (Ace)
**/
public int getNumericValue() {
return numericValue;
}
/**
* The method takes a card and returns:
* - a negative number if this card has a value less than the
* other card
* - a positive number if this card has a value greater than the
* other card
* - 0 if they have equal values
**/
public int compareTo(Card other) {
return this.numericValue - other.numericValue;
}
public String toString(){
return value + " of " + suit;
}
}
InvalidCardException class:
public class InvalidCardException extends Exception{
public InvalidCardException(String invalidValue , String type){
super(" Invalid " + type + ": " + invalidValue);
}
}
Sorting the cards
import java.util.Random;
import java.util.Arrays;
public class SortCards {
public static void main(String [] args) throws InvalidCardException {
Card [] deck = shuffleAndDeal();
System.out.println("Shuffled deck:");
for (Card card: deck) {
System.out.println(card);
}
// Calling a predefined sort method. Works on arrays
// of comparable objects, uses compareTo for pairwise
// comparison
Arrays.sort(deck);
System.out.println("Sorted deck:");
for (Card card: deck) {
System.out.println(card);
}
}
public static Card [] shuffleAndDeal() throws InvalidCardException {
String [] suits = {"Spades", "Hearts", "Diamonds", "Clubs"};
String [] values = {"2","3","4","5","6","7","8","9","10","J","Q","K","A"};
Card [] deck = new Card [52];
//create a deck
int i = 0;
for (String suit: suits) {
for (String value: values) {
deck[i] = new Card(suit, value);
i++;
}
}
// shuffle the deck
Random rand = new Random();
for (int j = 0; j < 200; ++j) {
int index1 = rand.nextInt(52);
int index2 = rand.nextInt(52);
Card temp = deck[index1];
deck[index1] = deck[index2];
deck[index2] = temp;
}
return deck;
}
}
public class SortingMethods {
/**
* The method sorts an array using insertion sort
* @param <T> - the type of elements in the array (must extend Comparable<T>)
* @param arr - the array to be sorted
*/
public static <T extends Comparable<T>> void insertionSort(T [] arr) {
for (int i = 1; i < arr.length; ++i) {
// loop invariant: arr[0..i-1] is sorted
// the item to be inserted into the proper
// position in the sorted portion of the array
T nextItem = arr[i];
// iterating through the sorted portion backward
int j = i;
while (j > 0 && arr[j-1].compareTo(nextItem) > 0){
// loop invariant: nextItem is smaller than
// elements to the left of it
//shift arr[j-1] to the right
arr[j] = arr[j-1];
j--;
}
// insert the new item into its position
arr[j] = nextItem;
}
}
/**
* The method sorts an array using merge sort. The method is recursive.
* @param <T> - the type of elements in the array (must extend Comparable<T>)
* @param arr - the array to be sorted
*/
public static <T extends Comparable<T>> void mergeSort(T [] arr) {
if (arr.length > 1) {
// split the array into two halves
int length1 = arr.length/2;
int length2 = arr.length - arr.length/2;
// create the arrays:
T[] half1 = (T[]) new Comparable[length1];
T[] half2 = (T[]) new Comparable[length2];
// copy the corresponding portions of the array into new arrays
for(int i = 0; i<length1; i++) {
half1[i] = arr[i];
}
for(int i = length1; i < arr.length; i++) {
half2[i - length1] = arr[i];
}
// fill in the rest of your code here
}
}
}
Testing sorting methods
import java.util.Random;
public class TestSorting {
public static void main(String [] args) {
// the array must be of Integer, not int,
// otherwise it's not recognized as Comparable
System.out.println("======== Testing random array generating ==========");
Integer [] toSort = randomInts(1, 101, 20);
printIntArray(toSort);
System.out.println(isSorted(toSort));
System.out.println("======== Testing insertion sort ==========");
// small-scale test: print elements
toSort = randomInts(1,101, 10);
System.out.println("Before sorting: ");
printIntArray(toSort);
System.out.println("After sorting: ");
SortingMethods.insertionSort(toSort);
printIntArray(toSort);
// larger-scale test: run on several arrays and check if they
// are sorted
boolean allSorted = true;
for (int i = 0; i < 5; ++i) {
toSort = randomInts(1, 101, 20 * (i + 1));
SortingMethods.insertionSort(toSort);
boolean isSorted = isSorted(toSort);
allSorted = allSorted && isSorted;
System.out.println("An array of " + 20 *(i + 1) + " elements is sorted: " + isSorted);
if (!isSorted) {
System.out.println("This array was not sorted properly:");
printIntArray(toSort);
}
}
if (allSorted) {
System.out.println("Congratulations! Your insertion sort is working!");
} else {
System.out.println("There are problems with your insertion sort");
}
System.out.println("======== Testing merge sort ==========");
toSort = randomInts(1,101, 11);
System.out.println("Before sorting: ");
printIntArray(toSort);
System.out.println("After sorting: ");
SortingMethods.mergeSort(toSort);
printIntArray(toSort);
allSorted = true;
for (int i = 0; i < 5; ++i) {
toSort = randomInts(1, 101, 20 * (i + 1));
SortingMethods.mergeSort(toSort);
boolean isSorted = isSorted(toSort);
allSorted = allSorted && isSorted;
System.out.println("An array of " + 20 *(i + 1) + " elements is sorted: " + isSorted);
if (!isSorted) {
System.out.println("This array was not sorted properly:");
printIntArray(toSort);
}
}
if (allSorted) {
System.out.println("Congratulations! Your merge sort is working!");
} else {
System.out.println("There are problems with your merge sort");
}
}
/**
* Generates an array of random Integers in the range from
* min (inclusive) to max (exclusive). The number of elements
* is given by num.
* @param min - the minimum value (inclusive)
* @param max - the maximum value (exclusive)
* @param num - the number of elements in the array
* @return - the array of num random Integers between min and max
* @throws IllegalArgumentException if min >= max or num < 0
*/
public static Integer [] randomInts(int min, int max, int num) {
if (min >= max || num < 0) {
throw new IllegalArgumentException();
}
Integer [] theInts = new Integer[num];
Random rand = new Random();
for (int i = 0; i < num; ++i){
theInts[i] = rand.nextInt(max - min) + min;
}
return theInts;
}
/**
* Checks if the parameter array is sorted
* @param <T> - the type of the elements in the array. Must
* extend Comparable<T>
* An array is sorted if for every two consecutive elements
* arr[i].compareTo(arr[i+1]) <= 0
* @param arr - the given array
* @return true if the given array is sorted, false otherwise
*/
public static <T extends Comparable<T>> boolean isSorted(T [] arr) {
// fill in the code here
return true;
}
/**
*
* The method prints its argument <code>arr</code>
* element by element on one line, separated by commas,
* with [ before the first element and ] after the last one
* @param arr - an array of type Integer
*/
public static void printIntArray(Integer [] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; ++i) {
System.out.print(arr[i]);
if (i != arr.length - 1)
System.out.print(", ");
}
System.out.println("]");
}
}