SCJP - Sortowanie list i tablic oraz wyszukiwanie binarne

Dziś będzie o sortowaniu list i tablic oraz o wyszukiwaniu binarnym w tychże, a więc o klasach java.util.Arrays i java.util.Collections (nie mylmy z interfejsem java.util.Collection) oraz interfejsach java.util.Comparator<T> i java.lang.Comparable<T>.

Klasy Arrays oraz Collections to klasy narzędziowe implementujące szereg operacji statycznych ułatwiających pracę z kolekcjami i tablicami. Różnych ciekawych metod jest tam kilka, jednak z perspektywy egzaminu SCJP interesują nas głównie operacje sort(…) i binarySearch(…) zaimplementowane w wielu wersjach w obydwu klasach.

Operacja sort(…) z klasy Arrays służy do sortowania tablic a analogiczna operacja zaimplementowana w klasie Collections do sortowania list. Podstawowa wersja operacji sort(…) z klasy Arrays akceptuje jeden argument – tablicę wartości prymitywnych lub tablicę obiektów. Mamy także wersje sortujące tylko pewien fragment tablicy. Wtedy jako drugi argument wywołania podajemy indeks tablicy od którego (włącznie) należy zacząć sortowanie a jako trzeci argument indeks końca (nie włącznie) sortowanego fragmentu. Mamy więc do dyspozycji następujące funkcje:

  // dla tablic byte[], short[], int[], long[], float[], double[], char[] i Object[]
public static void sort(int[] tab)

  // dla tablic byte[], short[], int[], long[], float[], double[], char[] i Object[]
public static void sort(int[] tab, int fromIndex, int toIndex)

Operacje te sortują elementy tablicy w porządku rosnącym. Oczywiste jest, jak wygląda ten porządek w przypadku liczb – znaki (tablica char[]) sortowane są alfabetycznie – co jednak z sortowaniem tablicy obiektów? Żeby posortować elementy musimy wiedzieć, jak porównać je między sobą (który z dwu obiektów jest większy?) – obiekty w sortowanej tablicy muszą być więc porównywalne. W języku Java obiekty są porównywalne jeśli implementują interfejs Comparable<T>. Interfejs ten definiuje jedną metodę:

int compareTo(T obj) 

Metoda ta zwraca liczbę ujemną, jeśli obiekt dla którego ją wywołano jest mniejszy od obiektu przekazanego jako argument; liczbę 0 jeśli obiekty są równe; liczbę dodatnią jeśli jest większy.

Interfejs Comparable<T> implementowany jest przez wiele klas z Javy SE, w tym przez wszystkie klasy opakowujące typów prostych (np. Integer, Double, Character) a także klasy Calendar, Date, Time czy String.

A co jeśli chcemy posortować tablicę zgodnie z innym porządkiem niż rosnący? A może tablicę Stringów chcemy posortować inaczej niż leksykograficznie (standardowy porządek dla Stringów to porządek leksykograficzny)? Może ważniejsza jest dla nas w danym zastosowaniu długość Stringa? A może chcielibyśmy posortować ignorując wielkość liter? Da się? Da! Wystarczy zdefiniować interesujący nas porządek implementując interfejs Comparator<T>. Klasa Arrays oprócz dwu wersji operacji sort(…) pokazanych powyżej implementuje jeszcze dwie wersje różniące się tym, że jako kolejny argument wywołania dodajemy obiekt implementujący interfejs Comparator<T>, który to określa porządek sortowanych elementów. Poniżej przykład.

public class TestClass {
    public static void main(String[] args) {
        String[] strings = { "Urszula", "Ola", "Agata", "Jola" };
  
        Arrays.sort(strings, new LengthComparator());
        
        for(String s : strings)
            System.out.print(s + " ");
    }
}
  
    // określa sortowanie Stringów od najkrótszego do najdłuższego
class LengthComparator implements Comparator<String> {
    public int compare(String strA, String strB) {
        return strA.length() - strB.length();
    }
}

Interfejs Comparator<T> wymaga implementacji metody compare(…), która zwraca liczbę ujemną, jeśli pierwszy argument wywołania jest mniejszy niż drugi; liczbę 0, jeśli są równe; liczbę dodatnią jeśli pierwszy argument jest większy. Efektem uruchomienia powyższego programu będzie wyświetlenie napisu:

Ola Jola Agata Urszula

Klasa Collections implementuje dwie wersje metody sort(…). Pierwsza służy do sortowania listy elementów które są porównywalne same z siebie, tj. implementują interfejs Comparable<T> zaś druga do sortowania listy dowolnych obiektów, ale za to musimy określić porządek sortowania przekazując jako drugi argument wywołania instancję komparatora, tj. instancję klasy implementującej interfejs Comparator<T>. Sygnatury tych metod wyglądają nieco odstraszająco i są następujące:

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

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

Wyszukiwanie w kontekście list i tablic oznacza szukanie odpowiedzi na pytanie, czy dana lista lub tablica zawiera zadany element i jeśli tak to na której pozycji. Wyszukiwanie binarne implementowane przez metody binarySearch(…) z klasy Collections oraz Arrays to algorytm, który działa tylko dla kolekcji (list i tablic) posortowanych. Wyszukiwanie z zastosowaniem tego algorytmu działa o rząd wielkości szybciej niż wyszukiwanie liniowe (tj. przeglądanie listy element po elemencie) ale musimy pamiętać, że można go użyć tylko i wyłącznie do wyszukiwania w listach lub tablicach posortowanych. Co więcej, użycie algorytmu wyszukiwania binarnego dla listy czy tablicy nie posortowanej nie spowoduje błędu kompilacji czy wyjątku. Metoda binarySearch(…) wykona się, tyle że otrzymamy wynik nie zgodny ze stanem faktycznym.

W klasie Collections zaimplementowano dwie wersje metody binarySearch(…). Analogicznie jak w przypadku sortowania, pierwsza z nich służy do wyszukiwania z listy elementów, które są porównywalne a więc implementują interfejs Comparable<T>. Druga wersja służy do wyszukiwania z listy elementów, które same z siebie nie są porównywalne a więc musimy przekazać także komparator – obiekt, który będzie używany do porównywania – a więc obiekt implementujący interfejs Comparator<T>. Sygnatury tych metod są następujące:

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

Drugiej wersji metody – tej w której przekazujemy także komparator – należy użyć także w przypadku, gdy lista posortowana jest zgodnie z porządkiem innym niż naturalny (określony przez metodę compareTo(…) interfejsu Comparable<T>). W szczególności, jeśli listę sortowaliśmy z użyciem konkretnego komparatora to do wyszukiwania binarnego powinniśmy użyć tego samego komparatora.

W klasie Arrays zaimplementowano po jednej metodzie dwuargumentowej dla tablicy każdego typu prostego i dla tablicy obiektów. Pierwszym argumentem jest tablica a drugim szukany element. Zaimplementowano także metodę, która akceptuje komparator. Sygnatury tych metod są następujące:

  // dla tablic byte[], short[], int[], long[], float[], double[], char[] i Object[]
public static int binarySearch(int[] a, int key)
  
public static <T> int binarySearch(T[] a,
                                   T key,
                                   Comparator<? super T> comp)