Ordering Elements in Lists

In order to sort the elements of a collection by their natural ordering or by another total ordering, the elements must implement the Comparable<E> (§14.4, p. 761) or the Comparator<E> (§14.5, p. 769) interface, respectively.

The Collections class provides two generic static methods for sorting lists.

Click here to view code image

<E extends Comparable<? super E>> void sort(List<E> list)
<E> void sort(List<E> list, Comparator<? super E> comparator)

The first method sorts the elements in the list according to their natural ordering. The second method does the sorting according to the total ordering defined by the comparator.

In addition, all elements in the list must be mutually comparable: The method call e1.compareTo(e2) (or e1.compare(e2) in the case of the comparator) must not throw a ClassCastException for any elements e1 and e2 in the list. In other words, it should be possible to compare any two elements in the list. Note that the second method does not require that the type parameter E is Comparable<E>.

If the specified comparator is null then the natural ordering for the elements is used, requiring elements in this list to implement the Comparable<E> interface.

Click here to view code image

<E> Comparator<E> reverseOrder()
<E> Comparator<E> reverseOrder(Comparator<E> comparator)

The first method returns a comparator that enforces the reverse of the natural ordering. The second method reverses the total ordering defined by the comparator. Both are useful for maintaining objects in reverse-natural or reverse-total ordering in sorted collections and arrays.

The List<E> interface also defines an abstract method for sorting lists, with semantics equivalent to its namesake in the Collections class.

Click here to view code image

// Defined in the List <E> interface.
void sort(Comparator<? super E> comparator)

This list is sorted according to the total ordering defined by the specified comparator. If the specified comparator is null then the natural ordering for the elements is used, requiring elements in this list to implement the Comparable<E> interface.

This code shows how a list of strings is sorted according to different criteria. We have used the sort() method from the List<E> interface and from the Collections class.

Click here to view code image

List<String> strList = new ArrayList<>();
Collections.addAll(strList, “biggest”, “big”, “bigger”, “Bigfoot”);
strList.sort(null);                                      // Natural order
strList.sort(Comparator.comparing(String::length));      // length order
strList.sort(Collections.reverseOrder());                // Reverse natural order
Collections.sort(strList, String.CASE_INSENSITIVE_ORDER);// Case insensitive order
Collections.sort(strList,                        // Reverse case insensitive order
                 Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));

The output below shows the list before sorting, followed by the results from the calls to the sort() methods above, respectively:

Click here to view code image

Before sorting:                             [biggest, big, bigger, Bigfoot]
After sorting in natural order:             [Bigfoot, big, bigger, biggest]
After sorting in length order:              [big, bigger, Bigfoot, biggest]
After sorting in reverse natural order:     [biggest, bigger, big, Bigfoot]
After sorting in insensitive order:         [big, Bigfoot, bigger, biggest]
After sorting in reverse insensitive order: [biggest, bigger, Bigfoot, big]

It is important to note that either the element type of the list must implement the Comparable<E> interface or a Comparator<E> must be provided. The following code sorts a list of StringBuilder according to their natural ordering, as the class String-Builder implements the Comparable<StringBuilder> interface.

Click here to view code image

List<StringBuilder> sbList = new ArrayList<>();
Collections.addAll(sbList, new StringBuilder(“smallest”),
                   new StringBuilder(“small”), new StringBuilder(“smaller”));
Collections.sort(sbList);                 // [small, smaller, smallest]

Below is an example of a list whose elements are not mutually comparable. Raw types are used intentionally to create such a list. Predictably, the sort() method throws an exception because the primitive wrapper classes do not permit interclass comparison.

Click here to view code image

List freakList = new ArrayList();                   // Raw types.
Collections.addAll(freakList, 23, 3.14, 10L);
freakList.sort(null);                               // ClassCastException

The comparator returned by the reverseOrder() method can be used with sorted collections. The elements in the following sorted set would be maintained in descending order:

Click here to view code image

Set<Integer> intSet = new TreeSet<>(Collections.reverseOrder());
Collections.addAll(intSet, 9, 11, -4, 1);
System.out.println(intSet);          // [11, 9, 1, -4]

The following utility methods in the Collections class apply to any list, regardless of whether the elements are Comparable<E> or not:

void reverse(List<?> list)

Reverses the order of the elements in the list.

Click here to view code image

void rotate(List<?> list, int distance)

Rotates the elements toward the end of the list by the specified distance. A negative value for the distance will rotate toward the start of the list.

Click here to view code image

void shuffle(List<?> list)
void shuffle(List<?> list, Random rnd)

Randomly permutes the list—that is, shuffles the elements.

Click here to view code image

void swap(List<?> list, int i, int j)

Swaps the elements at indices i and j.

The effect of these utility methods can be limited to a sublist—that is, a segment of the list. The following code illustrates rotation of elements in a list. Note how the rotation in the sublist view is reflected in the original list.

Click here to view code image

// intList refers to the following list:                        [9, 11, -4, 1, 7]
Collections.rotate(intList, 2);        // Two to the right.     [1, 7, 9, 11, -4]
Collections.rotate(intList, -2);       // Two to the left.      [9, 11, -4, 1, 7]
List intSublist = intList.subList(1,4);// Sublist:                 [11, -4, 1]
Collections.rotate(intSublist, -1);    // One to the left.         [-4, 1, 11]
                                       // intList is now:       [9, -4, 1, 11, 7]

Leave a Reply

Your email address will not be published. Required fields are marked *