JCH
Java Community | Help. Code. Learn.•3d ago
JavaBot

Week 121 — What mechanisms do the Java standard libraries provide for sorting?

Question of the Week #121
What mechanisms do the Java standard libraries provide for sorting?
5 Replies
KineticMate
KineticMate•3d ago
Arrays can be sorted using the Arrays.sort methods: 
int[] arrayToBeSorted = {51,61,561,581,65,84,53,12,86,12,213,87,31,48};
Arrays.sort(arrayToBeSorted);
System.out.println(Arrays.toString(arrayToBeSorted));//[12, 12, 31, 48, 51, 53, 61, 65, 84, 86, 87, 213, 561, 581]
int[] arrayToBeSorted = {51,61,561,581,65,84,53,12,86,12,213,87,31,48};
Arrays.sort(arrayToBeSorted);
System.out.println(Arrays.toString(arrayToBeSorted));//[12, 12, 31, 48, 51, 53, 61, 65, 84, 86, 87, 213, 561, 581]
Sorting primitive types typically happens in ascending order of their values but when sorting arbitrary objects, one needs to decide how these should be sorted which can be done using a Comparator that compares two objects and returns - a positive value if the first object is considered greater than the second object - a negative value if the first object is considered smaller than the second object - zero if both objects are equal Objects that have a natural order can choose to implement Comparable which allows them to define a compareTo method specifying how these objects should be ordered by default (unless a custom Comparator is specified). For example, Strings are naturally ordered lexicographically so it is not necessary to provide a custom Comparator when that order is wanted. 
String[] stringsToBeSorted = {"Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted"};
Arrays.sort(stringsToBeSorted);
System.out.println(Arrays.toString(stringsToBeSorted));// [ - , Hello, This, World, an, array, be, example, is, sorted, to]

Comparator<String> caseInsensitiveComparator = String.CASE_INSENSITIVE_ORDER;
Arrays.sort(stringsToBeSorted, caseInsensitiveComparator);
System.out.println(Arrays.toString(stringsToBeSorted));// [ - , an, array, be, example, Hello, is, sorted, This, to, World]
String[] stringsToBeSorted = {"Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted"};
Arrays.sort(stringsToBeSorted);
System.out.println(Arrays.toString(stringsToBeSorted));// [ - , Hello, This, World, an, array, be, example, is, sorted, to]

Comparator<String> caseInsensitiveComparator = String.CASE_INSENSITIVE_ORDER;
Arrays.sort(stringsToBeSorted, caseInsensitiveComparator);
System.out.println(Arrays.toString(stringsToBeSorted));// [ - , an, array, be, example, Hello, is, sorted, This, to, World]
In addition to arrays, Lists can be sorted using the Collections.sort method. 
List<String> listToBeSorted = new ArrayList<>(List.of("Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted"));
Collections.sort(listToBeSorted);
System.out.println(listToBeSorted); // [ - , Hello, This, World, an, array, be, example, is, sorted, to]

Collections.sort(listToBeSorted, String.CASE_INSENSITIVE_ORDER);
System.out.println(listToBeSorted); // [ - , an, array, be, example, Hello, is, sorted, This, to, World]
List<String> listToBeSorted = new ArrayList<>(List.of("Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted"));
Collections.sort(listToBeSorted);
System.out.println(listToBeSorted); // [ - , Hello, This, World, an, array, be, example, is, sorted, to]

Collections.sort(listToBeSorted, String.CASE_INSENSITIVE_ORDER);
System.out.println(listToBeSorted); // [ - , an, array, be, example, Hello, is, sorted, This, to, World]
When elements are produced in some way and need to be consumed in their natural order (according to Comparable) or according to a custom Comparable), PriorityQueue is based on a heap and can be used which ensures that the "smallest" element is consumed first. 
Queue<String> heap = new PriorityQueue<>();//or new PriorityQueue<>(String.CASE_INSENSITIVE_ORDER); to use a custom comparator
for(String s : List.of("Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted")) {
  heap.add(s);
}

//prints the Strings in lexicographical order
while(!heap.isEmpty()) {
  System.out.println(heap.poll());
}
Queue<String> heap = new PriorityQueue<>();//or new PriorityQueue<>(String.CASE_INSENSITIVE_ORDER); to use a custom comparator
for(String s : List.of("Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted")) {
  heap.add(s);
}

//prints the Strings in lexicographical order
while(!heap.isEmpty()) {
  System.out.println(heap.poll());
}
KineticMate
KineticMate•3d ago
Similarly, TreeSet can be used to create a Set which does not allow duplicates and is always sorted. 
SortedSet<String> alwaysSortedSet = new TreeSet<>(List.of("Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted") /*, String.CASE_INSENSITIVE_ORDER*/);

alwaysSortedSet.add(".");
alwaysSortedSet.addAll(List.of("New entries are put 'in the right spot' automatically".split(" ")));

System.out.println(alwaysSortedSet);// [ - , 'in, ., Hello, New, This, World, an, are, array, automatically, be, entries, example, is, put, right, sorted, spot', the, to]
SortedSet<String> alwaysSortedSet = new TreeSet<>(List.of("Hello", "World", " - ", "This", "is", "an", "example", "array", "to", "be", "sorted") /*, String.CASE_INSENSITIVE_ORDER*/);

alwaysSortedSet.add(".");
alwaysSortedSet.addAll(List.of("New entries are put 'in the right spot' automatically".split(" ")));

System.out.println(alwaysSortedSet);// [ - , 'in, ., Hello, New, This, World, an, are, array, automatically, be, entries, example, is, put, right, sorted, spot', the, to]
📖 Sample answer from dan1st
KineticMate
KineticMate•3d ago
There are a number of different mechanisms for sorting objects and values in a Java program. Which one to use depends on the data structure being used. The foundation of sorting comes down to two interfaces: java.lang.Comparable<T> and java.util.Comparator<T> Comparable is implemented by classes that want to have an intrinsic comparison order between objects of that class. For instance, a Person class might implement Comparable<Person> that sorts Person objects by last name, then first name: 
class Person implements Comparable<Person> {
  // ...
  @Override
  public int compareTo(final Person o) {
    int lnCompare = lastName.compareTo(o.lastName);
    if (lnCompare == 0) {
      return firstName.compareTo(o.firstName);
    }
    return lnCompare;
  }
}
class Person implements Comparable<Person> {
  // ...
  @Override
  public int compareTo(final Person o) {
    int lnCompare = lastName.compareTo(o.lastName);
    if (lnCompare == 0) {
      return firstName.compareTo(o.firstName);
    }
    return lnCompare;
  }
}
Comparator provides a mechanism for creating external comparison ordering operations. These are often implemented as lambdas, but do not have to be. To continue the Person example, another class can be created to order those objects by years of service: 
public class Person implements Comparable<Person> {
  public static Comparator<Person> SORT_BY_YEARS_OF_SERVICE = (left, right) -> {
    final float diff = left.yearsOfService - right.yearsOfService;
    if (diff == 0) {
      return 0;
    }
    return diff > 0 ? 1 : -1;
  };
  // ...
}
public class Person implements Comparable<Person> {
  public static Comparator<Person> SORT_BY_YEARS_OF_SERVICE = (left, right) -> {
    final float diff = left.yearsOfService - right.yearsOfService;
    if (diff == 0) {
      return 0;
    }
    return diff > 0 ? 1 : -1;
  };
  // ...
}
KineticMate
KineticMate•3d ago
Once the comparison logic is defined, it can be used in a number of ways.... COLLECTIONS Many classes in the Java Collections framework understand classes that implement Comparable, and will use the "natural ordering" exposed by that interface. Those same collection classes will often allow a separate Comparator implementation to be supplied in the constructor to use for ordering. For instance,TreeSet expects objects added to it to implement Comparable, unless a separate Comparator has been supplied to the constructor. The List interface defines a sort(Comparator) method, which also allows for a null parameter, in which case the "natural ordering" is used. ARRAYS The Collections framework also provides the Arrays class, which contains a number of static methods for working with arrays, including comparison, sorting, and searching operations. Some of the methods accept a Comparator, which can be null to trigger the use of "natural ordering" (similar to the List::sort(Comparator) method). Some require that the objects implement the Comparable interface. Note that Arrays also provides methods for comparing, sorting, and searching arrays of numeric primitives, which are inherently comparable.
⭐ Submission from dangerously_casual
KineticMate
KineticMate•3d ago
The Java standard libraries provide several mechanisms for sorting: 1. Arrays.sort() Used for sorting arrays. Works for primitive types (e.g., int[]) and objects (e.g., String[], Integer[]). Overloads allow custom sorting via Comparator. ex; Arrays.sort(array); Arrays.sort(array, Comparator.reverseOrder()); 2. Collections.sort() Used for sorting List collections (e.g., ArrayList). Can sort using natural order or with a custom Comparator. ex; Collections.sort(list); Collections.sort(list, comparator); 3. List.sort() (Java 8+) Direct method on List interface using a lambda or Comparator. ex; list.sort(Comparator.comparing(Person::getName)); 4. Streams API (Java 8+) Used for sorting streams, especially in functional-style processing. ex; list.stream().sorted().collect(Collectors.toList()); list.stream().sorted(Comparator.comparing(...)); These mechanisms use efficient sorting algorithms internally, like TimSort for object sorting.
Submission from h_s_j_1107_83351

Did you find this page helpful?