SortSorting elements in a Java collection (ordering them) is not always as simple as calling sort(). Instead we may need Comparable, and special methods.
Array.sort arranges elements in place. By default, sort() uses an ascending order. With objects, we use the Comparable interface, and implement its compareTo method.
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 returns an int that indicates whether the first object is larger, equal in size, or smaller than the second object.CompareTo negative one, zero, or one if the first argument is smaller, equal, or larger than the second.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);
}
}
}Value = 0
Value = 50
Value = 100
Value = 200Consider 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.
public int compareTo(Item item) {
// Compare both value fields.
return Integer.compare(item.value, this.value);
}Value = 200
Value = 100
Value = 50
Value = 0Integer.compareWe often use Integer.compare, and similar methods like Double.compare, in compareTo methods. These methods return one of three values—they indicate relative size.
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));
}
}1 [first is larger]
-1 [first is smaller]
0 [both are equal]Collections.sortSuppose we have a collection (like a Vector, ArrayList) that needs sorting. We cannot directly use Arrays.sort here. Instead we invoke Collections.sort.
Collections.sort is part of java.util.Collections. The collection (in this program, Vector) is modified in-place.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);
}
}
}1
10
100It is possible to use a lambda expression argument to the Collections.sort method to sort elements in an ArrayList. Here we use records in an ArrayList, and sort by a field.
ArrayList by the "number" int field, in ascending order, and display them.import java.util.*;
public class Program {
public static void main(String[] args) {
// The record type.
record Item (String name, int number) {}
var items = new ArrayList<Item>();
// Add 3 elements to the ArrayList.
items.add(new Item("bird", 10));
items.add(new Item("cat", 200));
items.add(new Item("worm", 5));
// Use lambda expression with sort.
Collections.sort(items, (a, b) -> Integer.compare(a.number, b.number));
// Display the elements.
for (var item : items) {
System.out.println(item);
}
}
}Item[name=worm, number=5]
Item[name=bird, number=10]
Item[name=cat, number=200]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.
Arrays.sort. Finally we use the String class constructor create a new String from our modified array.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"));
}
}aczWe can sort elements according to a Comparator. We must create a class that implements the Comparator—the element type is specified within angle brackets.
LengthComparator.compare(), we return the result of Integer.compare. We compare lengths.String array and an instance of our LengthComparator to Arrays.sort. This orders the array.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);
}
}
}has
this
five
array
elementsParallelSortThis 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.
parallelSort may not be faster than Arrays.sort. We must test parallelSort to see if it is faster in a program.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]);
}
}1
998ParallelSort, benchmarkThis program tries to find out whether parallelSort is faster than sort. It allocates an int array of 1 million elements, and sets each third element to a number.
Arrays.parallelSort to sort the 1 million elements.Arrays.sort method to sort the same elements on a single thread.int array like the one here, we see a performance advantage (on a computer with 4-core Intel desktop processor).parallelSort is apparent on large arrays. The speedup is less than a factor of 2.import java.util.Arrays;
public class Program {
public static void main(String[] args) {
long t1 = System.currentTimeMillis();
// Version 1: use parallelSort on 1 million elements.
for (int i = 0; i < 100; i++) {
int[] values = new int[1000000];
for (int x = 0; x < values.length; x += 3) {
values[x] = x;
}
Arrays.parallelSort(values);
}
long t2 = System.currentTimeMillis();
// Version 2: use sort on 1 million elements.
for (int i = 0; i < 100; i++) {
int[] values = new int[1000000];
for (int x = 0; x < values.length; x += 3) {
values[x] = x;
}
Arrays.sort(values);
}
long t3 = System.currentTimeMillis();
// ... Times.
System.out.println(t2 - t1);
System.out.println(t3 - t2);
}
}473 ms Arrays.parallelSort
735 ms Arrays.sortWith Arrays.sort, the low-level details of quick-sorting are provided. We focus on important high-level details, and this leads to clearer programs.