Java Tutorials Made Easy banner


Sorting and Searching using the Java API

The Java API provides several ways to sort data. The sort methods of the Arrays class sort Java arrays by their natural order, the order defined by their objects, or using the provided comparator. The sort methods of the Collections class sort lists by the order defined by their objects or using the provided comparator. Java streams sort their elements by the order defined by their objects or using the provided comparator.

The Java API also provides ways to search arrays, lists, and streams. The binarySearch methods of the Arrays class search for an element in a Java array. The indexOf method List implementations and the binarySearch methods of the Collections class search for an element in a list. Java streams can be searched for elements in sequential order.

Section 1 - Sorting Java Arrays using the Arrays Class

The primitive sort methods of the Arrays class sort the elements in an array in ascending order according to the natural ordering of the primitive type.

 

         static void sort(byte[] a)

         static void sort(char[] a)

         static void sort(double[] a)

         static void sort(float[] a)

         static void sort(int[] a)

         static void sort(long[] a)

         static void sort(short[] a)

The following example sorts an array of int primitives in ascending order.

int[] ia = { 3, 1, 5 ,2 };

Arrays.sort(ia);

for (int i=0; i< ia.length; i++)

    System.out.print(ia[i] + " ");

System.out.println();

OUTPUT:

1 2 3 5

The object sort method sorts an array of comparable objects based on the order defined by the objects.

         static void sort(Object[] a)

The following example sorts an array of strings in lexicographical (character by character) order:

String[] sa =

    { "Pluto", "Neptune", "Uranus", "Saturn" }; // Yes, Pluto

Arrays.sort(sa);

for (int i=0; i< sa.length; i++)

    System.out.print(sa[i] + " ");

System.out.println();

OUTPUT:

Neptune Pluto Saturn Uranus

If the elements of the array passed to the object sort method are not comparable, a ClassCastException occurs at run time. The Interval class below is not comparable.

class Interval

{

    int start;

    int end;

    Interval(int s, int e) { start = s; end = e; }

    @Override public String toString() { return start + "." + end; }

}

Therefore, sorting an array of Interval objects throws a ClassCastException at run time. Note that the array elements remain in the original order.

Interval[] inta = { new Interval(5, 9),

                    new Interval(3, 7),

                    new Interval(4, 6),  

                    new Interval(2, 7)};

try {

    Arrays.sort(inta);

}

catch (ClassCastException e) {

    System.out.println(e.getMessage());

}

for (int i=0; i< inta.length; i++)

    System.out.print(inta[i] + " ");

System.out.println();

OUTPUT:

sortingsearching.Interval cannot be cast to java.lang.Comparable

5.9 3.7 4.6 2.7

If the Interval class is made comparable, it can be sorted by the object sort method. The ComparableInterval class compares ComparableInterval objects by their start values followed by their end values.

class ComparableInterval implements Comparable<ComparableInterval>

{

    int start;

    int end;

    ComparableInterval(int s, int e) { start = s; end = e; }

    @Override public String toString() { return start + "." + end; }

    @Override public int compareTo(ComparableInterval c)

    {

        if (start == c.start)

            return end - c.end;

        return start - c.start;

    }

    @Override public boolean equals(Object o)

    {

        ComparableInterval c = (ComparableInterval)o;

        return start == c.start && end ==c.end;

    }

}

       

ComparableInterval[] cinta = { new ComparableInterval(5, 7),

                               new ComparableInterval(4, 6),  

                               new ComparableInterval(2, 4),

                               new ComparableInterval(4, 5) };  

Arrays.sort(cinta);

for (int i=0; i< cinta.length; i++)

    System.out.print(cinta[i] + " ");

System.out.println();

OUTPUT:

2.4 4.5 4.6 5.7

An array of non-comparable objects can be sorted if a comparator is supplied. This method is generic for objects of type T.

         static <T> void sort(T[] a, Comparator<? super T> c)

The following example defines a comparator that compares Interval objects by their end values. The comparator is used by the sort method to order an array of Interval objects by their end values followed by their start values.

Comparator<Interval> byEndFirst = (x, y) ->

      (x.end == y.end)? x.start - y.start : x.end - y.end;

Arrays.sort(inta, byEndFirst);

for (int i=0; i< inta.length; i++)

    System.out.print(inta[i] + " ");

System.out.println();

OUTPUT:

4.6 2.7 3.7 5.9

Section 2 - Sorting Lists using the Collections Class

The Collections class has static sort methods that can be used sort lists.

Lists of comparable objects can be sorted using the following method. The method is generic for type T extends Comparable<? super T> .

         public static <T extends Comparable<? super T>> void sort(List<T> list)  

Since the String class is comparable, a list of strings can be sorted.

List<String> colors = Arrays.asList("RED", "GREEN", "BLUE");

Collections.sort(colors);

System.out.println(colors);

OUTPUT:

[BLUE, GREEN, RED]

The ComparableInterval class is also comparable. The following example sorts a list of ComparableIntervals by their start values followed by their end values:

List<ComparableInterval> cintervals

    = Arrays.asList(new ComparableInterval(5, 7),

                    new ComparableInterval(4, 6),  

                    new ComparableInterval(2, 4),

                    new ComparableInterval(4, 5));

Collections.sort(cintervals);

System.out.println(cintervals);

OUTPUT:

[2.4, 4.5, 4.6, 5.7]

Since the Interval class is not comparable, the following example generates a compilation error since generic type T does not extend Comparable<? super T> :

List<Interval> intervals = Arrays.asList( new Interval(5, 9),

                                          new Interval(3, 7),

                                          new Interval(2, 7),  

                                          new Interval(4, 6));

Collections.sort(intervals); // ERROR

Lists of non-comparable objects can be sorted if a comparator is supplied. This method is generic for objects of type T.       

         public static <T> void sort(List<T> list, Comparator<? super T> c)        

The following example provides a comparator that compares Interval objects by their end values followed by their start values. The comparator is used to sort the array of Interval objects.

Comparator<Interval> byEndFirst = (x, y) ->

      (x.end == y.end)? x.start - y.start : x.end - y.end;

Collections.sort(intervals, byEndFirst );

System.out.println(intervals);

OUTPUT:

[4.6, 2.7, 3.7, 5.9]

Section 3 - Sorting Stream Elements

The sorted method of the Stream<T> class sorts the stream’s elements provided they are comparable.

         Stream<T> sorted()

The following example sorts a stream of Integer elements.

        Stream.of( 4, 1, 5 ,3 )

              .sorted()

              .forEach(x -> System.out.print(x + " "));

        System.out.println();

OUTPUT:

       

1 3 4 5

If the sorted method is called on a stream of elements that are not comparable, a ClassCastException will occur. Since the Interval class is not comparable, the following example throws a ClassCastException when the sorted method is called on a stream of Interval elements.

List<Interval> intervals = Arrays.asList( new Interval(5, 9),

                                          new Interval(3, 7),

                                          new Interval(2, 7),  

                                          new Interval(4, 6));

try {

    intervals.stream()

             .sorted()

             .forEach(x -> System.out.print(x + " "));

    System.out.println();

}

catch (ClassCastException e) {

    System.out.println(e.getMessage());

}

OUTPUT:

sortingsearching.Interval cannot be cast to java.lang.Comparable

Since the ComparableInterval class is comparable, the sorted method can be used to sort a stream of ComparableInterval elements.

Stream.of(new ComparableInterval(5, 7),

          new ComparableInterval(4, 6),  

          new ComparableInterval(2, 4),

          new ComparableInterval(4, 5))

      .sorted()

      .forEach(x -> System.out.print(x + " "));

System.out.println();

OUTPUT:

2.4 4.5 4.6 5.7

If a comparator is provided, the sorted method can sort a stream of non-comparable elements.

         Stream<T> sorted(Comparator<? super T> comparator)

In the following example, the byEndFirst comparator compares Interval objects by end values followed by start values. This comparator is supplied to the sorted method which sorts a stream of Interval elements by end values followed by start values.

 

Comparator<Interval> byEndFirst = (x, y) ->

      (x.end == y.end)? x.start - y.start : x.end - y.end;

       

Stream<Interval> ints2 = Stream.of(new Interval(5, 9),

                                   new Interval(3, 7),

                                   new Interval(4, 6),  

                                   new Interval(2, 7));

ints2.sorted(byEndFirst)

    .forEach(x -> System.out.print(x + " "));

System.out.println();

OUTPUT:

4.6 2.7 3.7 5.9

Section 4 - Sequential vs. Binary Searches

A sequential search starts at the beginning of a data structure of size n and sequentially checks each element until a match is found. In the worst-case all n elements need to be checked, so the worst-case performance is O(n).

A binary search starts at the midpoint of the data and divides the selected interval in size by two until a match is found. The worst-case performance of a binary search is O(log n), which is considerably faster than the sequential search. The drawback is that data structure must be sorted in order to use the binary search, while the elements can be in any order to use the sequential search.

Section 5 - Performing Binary Searches on Arrays using the Arrays class

The primitive binarySearch methods of the Arrays class search a sorted Java array for an element of the primitive type. The element matched may not be the first occurrence of the element in the array.

If found, the binarySearch method returns the position in the array at which the element was found (referenced from 0). If not present, it returns a negative result indicating the the elements position if it were present in the array (referenced from 1).

         static int binarySearch(byte[] a, byte key)

         static int binarySearch(char[] a, charkey)

         static int binarySearch(double[] a, double key)

         static int binarySearch(float[] a, float key)

         static int binarySearch(int[] a, int key)

         static int binarySearch(long[] a, long key)

         static int binarySearch(short[] a, short key)

The following example calls binarySearch with a sorted array of int primitives. It returns 1 for int value 3, since 3 is found at position 1 (from 0). It returns -2 for int value 2, since 2 would be placed at position 2 (from 1) in the array.

        int[] ia = { 4, 1, 5 ,3 };

        Arrays.sort(ia);                // 1 3 4 5

        System.out.println("index of " + 3 + " is " + Arrays.binarySearch(ia, 3));

        System.out.println("index of " + 2 + " is " + Arrays.binarySearch(ia, 2));

       

OUTPUT:

index of 3 is 1

index of 2 is -2

The object binarySearch methods search a sorted Java array for an object.

         static int binarySearch(Object[] a, Object key)

In the following example, a sorted array of strings is searched for the string “Uranus” which is found at position 3 (from 0). The array is then searched for the string “Mars” which would be placed at position 1 (from 1) if inserted into the sorted array.

 

String[] sa = { "Pluto", "Neptune", "Uranus", "Saturn" };

Arrays.sort(sa);        // Neptune Pluto Saturn Uranus

System.out.println("index of Uranus is " +

                   Arrays.binarySearch(sa, "Uranus"));

System.out.println("index of Mars is " +

                   Arrays.binarySearch(sa, "Mars"));

OUTPUT:

index of Uranus is 3

index of Mars is -1

If the object to find is not comparable to the objects in the array being searched, the binarySearch method will throw a ClassCastException. The following example attempts to use the binarySearch method to find Interval(2, 7) in an array of intervals. Since the Interval class is not comparable, a ClassCastException is thrown.

 

        Interval[] inta = { new Interval(4, 6),

                            new Interval(2, 7),

                            new Interval(3, 7),  

                            new Interval(5, 9)};

        try {

            int oindex = Arrays.binarySearch(inta, new Interval(2, 7));

        }

        catch (ClassCastException e) {

            System.out.println(e.getMessage());

        }

OUTPUT:

sortingsearching.Interval cannot be cast to java.lang.Comparable

Since ComparableInterval objects are comparable, the binarySearch method can be used to find a ComparableInterval object in a sorted array of ComparableInterval objects.

In the following example, the object ComparableInterval(5, 7) is found at position 3 (from 0) in the sorted array. The object ComparableInterval(4, 7) would be placed at position 4 (from 1) if inserted into the sorted array.

ComparableInterval[] cinta = { new ComparableInterval(5, 7),

                               new ComparableInterval(4, 6),  

                               new ComparableInterval(2, 4),

                               new ComparableInterval(4, 5) };  

Arrays.sort(cinta);

ComparableInterval findMe = new ComparableInterval(5, 7);

System.out.println("index of " + findMe + " is " +

                   Arrays.binarySearch(cinta, findMe));

ComparableInterval notPresent = new ComparableInterval(4, 7);

System.out.println("index of " + notPresent + " is " +

                   Arrays.binarySearch(cinta, notPresent));

OUTPUT:

index of 5.7 is 3

index of 4.7 is -4

A comparator can be provided to perform a binary search on an array of non-comparable objects or to override the ordering specified by the objects. This method is generic for type T. The array must be sorted using the specified comparator before calling binarySearch.

         static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

The following example defines a comparator that compares Interval objects by end values followed by start values. The comparator is used first to sort an array of Intervals, then to search for several Interval objects in the array. The object Interval(3, 7) is found at position 2 (from 0) in the sorted array. The object Interval(1, 7) would be placed at position 2 (from 1) if inserted in the sorted array.

Comparator<Interval> byEndFirst = (x, y) ->

      (x.end == y.end)? x.start - y.start : x.end - y.end;

Interval[] intb = { new Interval(5, 9),

                    new Interval(3, 7),

                    new Interval(4, 6),  

                    new Interval(2, 7)};

Arrays.sort(intb, byEndFirst);

       

Interval findInt = new Interval(3, 7);

System.out.println("index of " + findInt + " is " +

           Arrays.binarySearch(intb, findInt, byEndFirst));

Interval intNotPresent = new Interval(1, 7);

System.out.println("index of " + intNotPresent + " is " +

           Arrays.binarySearch(intb, intNotPresent, byEndFirst));

OUTPUT:

index of 3.7 is 2

index of 1.7 is -2

Section 6 - Performing Sequential Searches on Lists using List Implementations

The indexOf method of List implementations finds the index of the first occurrence of an Object within the list. If the Object is not found, -1 is returned.

int indexOf(Object o)

In the following example, "GREEN" is located at position 1 in a list of strings. Since "YELLOW" is not found in the list, -1 is returned.

 

List<String> list = Arrays.asList("RED", "GREEN", "BLUE");

System.out.println("index of GREEN is " + list.indexOf("GREEN"));

System.out.println("index of YELLOW is " + list.indexOf("YELLOW"));

OUTPUT:

index of GREEN is 1

index of YELLOW is -1

The indexOf method matches the Object to list elements based on the Object’s equals method. If the Object has not overridden the equals method, the method matches the Object if it refers to the same object as the list element.

Since the Interval class has not overridden the equals method and findInt does not refer to an element in the list, the indexOf method is not able locate Interval(4, 6) even though it exists in the list, and -1 is returned.

List<Interval> inta = Arrays.asList(new Interval(5, 9),

                                    new Interval(3, 7),

                                    new Interval(4, 6),  

                                    new Interval(2, 7));

Interval findInt = new Interval(4, 6);

System.out.println("index of " + findInt + " is " +

                   inta.indexOf(findInt));

OUTPUT:

index of 4.6 is -1

Since the ComparableInterval method overrides the equals method, the indexOf method locates ComparableInterval(4,5) at position 3 in the list.

List<ComparableInterval> cintervals

    = Arrays.asList(new ComparableInterval(5, 7),

                    new ComparableInterval(4, 6),  

                    new ComparableInterval(2, 4),

                    new ComparableInterval(4, 5));

ComparableInterval findCInt = new ComparableInterval(4, 5);

System.out.println("index of " + findCInt + " is " +

                   cintervals.indexOf(findCInt));

OUTPUT:

index of 4.5 is 3

Section 7 - Performing Binary Searches on Arrays using the Collections class

The Collections class has static binarySearch methods that can be used search for objects in lists.

A binary search can be performed on lists of comparable objects using the following method. The method is generic for type T extends Comparable<? super T> .

         static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

The following example creates a sorted list of strings. The color “GREEN” is found at position 1 (from 0) in the sorted list. The color “YELLOW” would be placed at position 4 (from 1) if inserted into the sorted list.

 

List<String> colors = Arrays.asList("RED", "GREEN", "BLUE");

Collections.sort(colors);        // BLUE GREEN RED

System.out.println("index of GREEN is " +

                   Collections.binarySearch(colors, "GREEN"));

System.out.println("index of YELLOW is " +

                   Collections.binarySearch(colors, "YELLOW"));

       

OUTPUT:

index of GREEN is 1

index of YELLOW is -4

A compilation error occurs if the object to find is not comparable to the objects in the list. Since the Interval class is not comparable, the binarySearch method in the following example generates a compilation error:

 

List<Interval> intervals = Arrays.asList(new Interval(4, 6),

                                         new Interval(2, 7),

                                         new Interval(3, 7),  

                                         new Interval(5, 9));

Interval findInt = new Interval(3, 7);

System.out.println("index of " + findInt + " is " +

           Collections.binarySearch(intervals, findInt)); // ERROR

Since the ComparableInterval class is comparable, the binarySearch method can be used to find a ComparableInterval object in a list of ComparableInterval objects. In the following example, ComparableInterval(5, 7) is found at position 3 (from 0) in the sorted list. ComparableInterval(2, 5) would be placed at position 2 (from 1) if inserted into the sorted list.

List<ComparableInterval> cintervals

    = Arrays.asList(new ComparableInterval(5, 7),

                    new ComparableInterval(4, 6),  

                    new ComparableInterval(2, 4),

                    new ComparableInterval(4, 5));

Collections.sort(cintervals);

ComparableInterval findCInt = new ComparableInterval(5, 7);

System.out.println("index of " + findCInt + " is " +

           Collections.binarySearch(cintervals, findCInt));

ComparableInterval notPresentCInt = new ComparableInterval(2, 5);

System.out.println("index of " + notPresentCInt + " is " +

           Collections.binarySearch(cintervals, notPresentCInt));

OUTPUT:

index of 5.7 is 3

index of 2.5 is -2

A comparator can be provided to perform a binary search on a list of non-comparable objects or to override the ordering specified by the objects. This method is generic for type T. The list must be sorted using the specified comparator before calling binarySearch.

         static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

The following example defines a comparator that compares Interval objects by end values followed by start values. The comparator is used first to sort a list of Intervals, then to search for several Interval objects in the list. The object Interval(3, 7) is found at position 2 (from 0) in the sorted list. The object Interval(4, 9) would be placed at position 4 (from 1) if inserted in the sorted list.

Comparator<Interval> byEndFirst = (x, y) ->

      (x.end == y.end)? x.start - y.start : x.end - y.end;

List<Interval> intervals2 = Arrays.asList( new Interval(5, 9),

                                          new Interval(3, 7),

                                          new Interval(2, 7),  

                                          new Interval(4, 6));

Collections.sort(intervals2, byEndFirst);

Interval findInt = new Interval(3, 7);

System.out.println("index of " + findInt + " is " +

    Collections.binarySearch(intervals2, findInt, byEndFirst));

Interval notPresentInt = new Interval(4, 9);

System.out.println("index of " + notPresentInt + " is " +  

    Collections.binarySearch(intervals2, notPresentInt, byEndFirst));

OUTPUT:

index of 3.7 is 2

index of 4.9 is -4

Section 8 - Searching for an Element in a Stream

The Stream interface’s anyMatch method can be used to determine if a stream contains a particular element based on the predicate provided.

         boolean anyMatch(Predicate<? super T> predicate)

The anyMatch method in the following example returns true since it found the element ComparableInterval(4, 5)  in the stream of ComparableInterval elements.

List<ComparableInterval> cintervals

    = Arrays.asList(new ComparableInterval(5, 7),

                    new ComparableInterval(4, 6),  

                    new ComparableInterval(2, 4),

                    new ComparableInterval(4, 5));

   

ComparableInterval findCInt = new ComparableInterval(4, 5);

System.out.println(findCInt + " found? " +

              cintervals.stream()

                        .anyMatch( x -> x.equals(findCInt)));

OUTPUT:

4.5 found? true

To extract the matched element from the stream, the filter method can be used in conjunction with the findFirst or findAny method. The filter method returns the stream of all elements that match the provided predicate. The findFirst method returns an Optional object containing the first element in the filtered stream. The findAny method returns an Optional object containing any element in the filtered stream.

         Stream<T> filter(Predicate<? super T> predicate)

         Optional<T> findFirst()

         Optional<T> findAny()

The following example uses the filter method to create a stream containing the single element that matches ComparableInterval(4, 5).  It is placed in an Optional<ComparableInterval> by the findAny method, then displayed using the Optional class’s ifPresent method.

    cintervals.stream()

              .filter( x -> x.equals(findCInt))

              .findAny()

              .ifPresent(x -> System.out.println(x));

OUTPUT:

4.5

In the following example, the element ComparableInterval(3, 6) is not found in the stream and the Optional object generated by the  findAny method is empty. Therefore,The Optional class’s orElseThrow method generates an exception.

ComparableInterval notPresent = new ComparableInterval(3, 6);

try

{

    cintervals.stream()

              .filter( x -> x.equals(notPresent))

              .findAny()

              .orElseThrow(() ->

                   new Exception(notPresent + " not found"));

}

catch (Exception e)

{

    System.out.println(e.getMessage());

}

OUTPUT:

3.6 not found


This tutorial was written by:

Ralph Lecessi banner
CLICK HERE
to read books by Ralph