Java Notes

Searching and Sorting Overview

Why searching and sorting are often treated together

Searching and sorting algorithms are often grouped together for a couple of reasons.

Comparisons are used by both types of algorithms.
Searching often requires a data structure that is already sorted.
Searching and sorting are common operations on data structures.

Comparing 3 ways - Operators, Comparable, Comparator

Comparisons are at the heart of both searching and sorting. Comparison turns out not to be quite as simple as it first appears to be. There are three ways values can be compared.

Comparison operators (< <= == != >= >) for primitive values.
```
    if (a < b) ...
```
Implementing the Comparable interface requires defining a compare() method. Java classes that have a natural sorting order (eg, String) often implement Comparable. That Comparable is implemented as an instance method of the class that is being compared (in contrast to Comparator).
```
    if (s.compareTo(t) < 0) ...
```
Implementing the Comparator interface requires defining a the compare() method. This method is not defined in the classes that are being compared, but usually in a small utility class which only defines this method. Comparators are very useful for classes that can be sorted in multiple ways.
```
    if (comparator.compare(x, y) < 0) ...
```

Use predefined sorting and searching methods if possible.

Java defines a number of searching and sorting methods. You should always use these in preference to writing your own because the library methods are almost always faster and have been well tested. However, there are times that the predefined methods don't work for your data structures, so it's also good to understand how these algorithms work.

Predefined sorting and searching methods for arrays

See Array Library Methods for a brief description of the static Array.binarySearch() and Array.sort() methods.

Predefined sorting and searching in the Collections classes

See Collections Class for a brief description of the static Collections.binarySearch() and Collections.sort() methods. This also has a brief discussion of data structures classes which are automatically sorted (those based on trees), or which have better than linear search methods (based on trees or hashing).