TheDeveloperBlog.com


Java

Java Sort Examples: Arrays.sort, Comparable

Sorting adds no new items. Instead it rearranges existing elements. With Array.sort, we sort elements in array in place—no new array is created.


By default, sort() uses an ascending order—low values come before high ones. With objects, we use the Comparable interface, and implement its compareTo method, to support sorting.


A Comparable example. Here we introduce a custom class, Item, and have it implement Comparable(Item). It specifies the compareTo method. In compareTo we return the result Integer.compare.

CompareTo: This returns an int that indicates whether the first object is larger, equal in size, or smaller than the second object.

Integer.compare: Returns negative one, zero, or one if the first argument is smaller, equal, or larger than the second.

Based on:

Java 7

Java program that implements Comparable

import java.util.Arrays;

class Item implements Comparable<Item> {
    public int value;

    public Item(int value) {
	this.value = value;
    }

    public int compareTo(Item item) {
	// Compare both value fields.
	return Integer.compare(this.value, item.value);
    }

    public String toString() {
	return "Value = " + value;
    }
}

public class Program {
    public static void main(String[] args) {

	// Create array of four Item objects.
	Item[] items = new Item[4];
	items[0] = new Item(100);
	items[1] = new Item(0);
	items[2] = new Item(200);
	items[3] = new Item(50);

	// Sort the Items with their Comparable interface methods.
	Arrays.sort(items);

	// Display our results.
	for (Item element : items) {
	    System.out.println(element);
	}
    }
}

Output

Value = 0
Value = 50
Value = 100
Value = 200

Sorted objects. In the program, the Item objects are sorted in ascending order based on their "value" field. The array itself, "items," is unaffected—only its elements are reordered.


Descending sort, Comparable. Consider this change to the compareTo method in the previous example. I reverse the order of this.value and item.value. This changes the sort to descending.

Code that compares in opposite order: Java

public int compareTo(Item item) {
    // Compare both value fields.
    return Integer.compare(item.value, this.value);
}

Output

Value = 200
Value = 100
Value = 50
Value = 0

Integer.compare. We often use Integer.compare, and similar methods like Double.compare, in compareTo methods. These methods return one of three values—they indicate relative size.

Integer: int

Values: Negative one means "first is smaller." Positive one means "first is bigger." And zero means equal.

Java program that uses Integer.compare

public class Program {
    public static void main(String[] args) {

	System.out.println(Integer.compare(10, 1));
	System.out.println(Integer.compare(1, 100));
	System.out.println(Integer.compare(1, 1));
    }
}

Output

1    [first is larger]
-1   [first is smaller]
0    [both are equal]

Ascending array sort. For an ascending (low to high) sort on an array, please directly use Arrays.sort. No special compareTo method is needed.

Array: sort

Collections.sort. Suppose we have a collection (like a Vector, ArrayList) that needs sorting. We cannot directly use Arrays.sort here. Instead we invoke Collections.sort.

Note: Collections.sort is part of java.util.Collections. The collection (in this program, Vector) is modified in-place.

Vector
Java program that uses Collections.sort

import java.util.Collections;
import java.util.Vector;

public class Program {
    public static void main(String[] args) {

	// Create Vector of three values.
	Vector<Integer> values = new Vector<>();
	values.add(10);
	values.add(1);
	values.add(100);

	// Sort elements in vector.
	Collections.sort(values);

	// Display results.
	for (int value : values) {
	    System.out.println(value);
	}
    }
}

Output

1
10
100

Alphabetize letters. Sometimes additional steps are needed to sort things. To sort chars in a String, we must first use toCharArray to convert it into a char array.

Strings

Then: We call Arrays.sort. Finally we use the String class constructor create a new String from our modified array.

Java program that alphabetizes String

import java.util.Arrays;

public class Program {

    static String alphabetize(String value) {
	// Convert String to array and sort its elements.
	char[] values = value.toCharArray();
	Arrays.sort(values);
	return new String(values);
    }

    public static void main(String[] args) {

	// Alphabetize this String.
	System.out.println(alphabetize("zac"));
    }
}

Output

acz

ParallelSort. This method sorts with threads. Using threads may help make sorting faster on large arrays. The method calls Arrays.sort when too few elements are present for threads to help.

Caution: In my tests, parallelSort may not be faster than Arrays.sort. We must test parallelSort to see if it faster in a program.

Java program that uses parallelSort

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

	// ... Create new array of 1000 random integers.
	int[] numbers = new int[1000];
	for (int i = 0; i < numbers.length; i++) {
	    numbers[i] = (int) (Math.random() * 1000);
	}
	// ... Use parallelsort on them.
	Arrays.parallelSort(numbers);

	// ... Display first and last number.
	System.out.println(numbers[0]);
	System.out.println(numbers[numbers.length - 1]);
    }
}

Output

1
998

Comparator. We can sort elements according to a Comparator. We must create a class that implements the Comparator—the element type is specified within angle brackets.

Sort by lengths: We sort the strings in an array by their lengths, from low to high. We implement a Comparator called LengthComparator.

Integer.compare: In compare(), we return the result of Integer.compare. We compare lengths.

Arrays.sort: We pass our String array and an instance of our LengthComparator to Arrays.sort. This orders the array.

Java program that implements Comparator

import java.util.Arrays;
import java.util.Comparator;

class LengthComparator implements Comparator<String> {
    public int compare(String arg0, String arg1) {
	// Use Integer.compare to compare the two Strings' lengths.
	return Integer.compare(arg0.length(), arg1.length());
    }
}

public class Program {
    public static void main(String[] args) {

	String[] array = new String[5];
	array[0] = "this";
	array[1] = "array";
	array[2] = "has";
	array[3] = "five";
	array[4] = "elements";

	// Sort strings by their lengths with this LengthComparator.
	Arrays.sort(array, new LengthComparator());

	// Display our results.
	for (String value : array) {
	    System.out.println(value);
	}
    }
}

Output

has
this
five
array
elements

HashMap. Not all collections are easy to sort. A HashMap cannot be directly sorted, but we can get a view of its keys, in an ArrayList, and sort that.

HashMap: Sort Keys, Values

Custom. Many sorting algorithms can be written in Java. But usually, implementing Comparable, and the compareTo method, is best. This enables any two objects to be compared.


Shuffle. The dealer at a casino shuffles a deck of cards. So too can we shuffle elements in arrays in our Java programs (and lose less money on bets).

Shuffle

Arrays.sort. With this method, the low-level details of quick-sorting are provided. We focus on important high-level details. Often this leads to simpler, clearer programs.