Sorting methods in Java

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.

Comparable version of Card


public class Card implements Comparable<Card> {

        private String suit;
        private int intValue;
        private String stringValue;

        public Card(String suit, String value){
                this.suit = suit;
                stringValue = value;
                intValue = convertToInt(stringValue);
        }

        private int convertToInt(String stringValue) {
                String [] faceValues = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
                for (int i = 0; i < faceValues.length; i++) {
                        if (faceValues[i].equals(stringValue)) {
                                return i + 2;
                        }

                }
                System.out.println("Invalid Card Value");
                System.exit(0);
                return -1;
        }

        public String getSuit() {
                return suit;
        }

        public String getValue() {
                return stringValue;
        }

        public int getNumericValue() {
                return intValue;
        }

        public int compareTo(Card other){
                if (this.intValue < other.intValue) {
                        return -1;
                }else if (this.intValue > other.intValue) {
                        return 1;
                }else {
                        return 0;
                }
        }

        public String toString() {
	    return stringValue + " of " + suit;
        }

}

Sorting the cards


import java.util.Random;
import java.util.Arrays;

public class SortCards {
    public static void main(String [] args) {
	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() {
	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;
    }
}

Sorting methods (static, similar to Arrays class)


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: they need to be of type T, 
			// need reflection to create them at run-time
			T[] half1 = (T []) java.lang.reflect.Array.newInstance(
					arr.getClass().getComponentType(), length1);
			T[] half2 = (T []) java.lang.reflect.Array.newInstance(
					arr.getClass().getComponentType(), 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("]");
	}

}

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.