Sortowanie – interfejs Comparator i Comparable – Java

Sortowanie java

Sortowanie  – interfejs Comparator i Comparable

Zdarza się tak poczas tworzenia aplikacji, że jesteś zmuszony do posortowania danych przed operacją na nich. Czasami dane są sortowane rosnąco na podstawie liczby np. ID, alfabetycznie na podstawie np. imienia i nazwiska, nawet może się zdarzyć sytuacja, gdy będzie potrzeba posortować punkty układu kartezjańskiego. Te wszystkie sortowania mogą zostać bez problemu wykonane implementując interfejs Comparable lub Comparator.

Do sortowania danych w kolekcji można wykorzystać metodę statyczną sort z klasy Collections – właśnie z niej skorzystamy.

Collections.sort

Interfejs collections

Przykładowe metody statyczne z klasy Collections

Na początek trzeba poznać mechanizm, który będzie odpowiedzialny w ogóle za sortowanie naszych kolekcji. Jest to metoda sort z klasy Collections.

Sortuje ona obiekty, jeżeli:

  • Obiekt implementuje interfejs Comparable
  • Do metody sort jest przekazany obiekt pełniący funkcję Comparatora
  • Comparator jest zdefiniowany przy użyciu wyrażenia lambda bezpośrednio w wywołaniu metody

Aby metoda sort potrafiła posortować kolekcję musimy jej zapewnić co najmniej jeden z wyżej wymienionych punktów. Gdy tak się nie stanie to kod po prostu się nie skompiluje.

Do pokazania działania metody można wykorzystać już wbudowane obiekty w Javie np. String, Integer.

Obiekty tego typu mogą posłużyć nam za przykład, ponieważ implementują one już interfejs Comparable.

String

Czas na pierwszy przykład sortowania kolekcji, zacznijmy od Stringa.

Sortowanie stringów

Niech w kolekcji będą przechowywane imiona i nazwiska osób biorące udział w darmowym kursie Java.

package pl.maniaq;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        List<String> patients = new LinkedList<>();
        patients.add("Johny Bravo");
        patients.add("Pablo Escabo");
        patients.add("Anna Kowalska");

        for (String patient:patients
             ) {
            System.out.println(patient);
        }


    }
}

Organizator kursu chciałby mieć zachowany porządek w swojej aplikacji, więc wymaga posortowania tych danych.

Programista wywołuję tylko jedną metodę:

Collections.sort(participans);

I voilà, organizator kursu zadowolony.

package pl.maniaq;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        List<String> patients = new LinkedList<>();
        patients.add("Johny Bravo");
        patients.add("Pablo Escabo");
        patients.add("Anna Kowalska");

        Collections.sort(patients);

        for (String patient:patients
             ) {
            System.out.println(patient);
        }


    }
}

 

Było to naprawdę proste, nie uważasz?

Float

Kolej teraz na sortowanie liczb, wybrałem typ zmiennoprzecinkowy, aby móc zasymulować kolekcję kursu walut.

Sortowanie floatówPonownie stwórzmy kolekcję przechowującą obiekty – w tym przypadku będą to liczby.

package pl.maniaq;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        List<Float> exchangeRates = new LinkedList<>();
        exchangeRates.add(3.56f);
        exchangeRates.add(2.3f);
        exchangeRates.add(3.15f);

        System.out.println(exchangeRates);
   

    }
}

Ze względu, że ktoś miał ochotę zobaczyć dane posortowane to wystarczy znowu wywołać jedną metodę:

Collections.sort(kursy);

Cały kod wygląda tak:

package pl.maniaq;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        List<Float> exchangeRates = new LinkedList<>();
        exchangeRates.add(3.56f);
        exchangeRates.add(2.3f);
        exchangeRates.add(3.15f);

        Collections.sort(exchangeRates);

        System.out.println(exchangeRates);
   

    }
}

 

Proste, prawda?

Klasa na potrzeby wpisu…

Na potrzeby przetestowania interfersju Comparable Comparator potrzebujemy napisać prostą klasę, na podstawie której będzie można tworzyć obiekty i wstawiać je do kolekcji.

Klasa będzie podstawowe dane jednego pacjenta, nie będę się zagłębiał w pisanie klas, ponieważ to temat na inny wpis.

 

 

 

package pl.maniaq;

import java.util.Objects;

public class Patient {

    private String name;
    private String lastName;
    private Integer age;
    private Boolean isMale;

    public Patient(String name, String lastName, Integer age, Boolean isMale){
        this.name = name;
        this.lastName = lastName;
        this.age = age;
        this.isMale = isMale;
    }

    public String getName() {
        return name;
    }

    public String getLastName() {
        return lastName;
    }

    public Integer getAge() {
        return age;
    }

    public Boolean getMale() {
        return isMale;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Patient patient = (Patient) o;
        return Objects.equals(name, patient.name) &&
                Objects.equals(lastName, patient.lastName) &&
                Objects.equals(age, patient.age) &&
                Objects.equals(isMale, patient.isMale);
    }

    @Override
    public int hashCode() {

        return Objects.hash(name, lastName, age, isMale);
    }

    @Override
    public String toString() {
        return "Patient{" +
                "name='" + name + '\'' +
                ", lastName='" + lastName + '\'' +
                ", age=" + age +
                ", isMale=" + isMale +
                '}';
    }
}

Jeżeli nie rozumiesz jeszcze metod: equals oraz hashCode i kontraktu między nimi to koniecznie przeczytaj ten wpis.

Comparable

Zacznijmy od pokazania sposobu wykorzystania interfejsu Comparable do posortowania danych. Jak możliwe już wiesz po zaimplementowaniu interfejsu w Javie jesteśmy zmuszeni do zaimplementowania wszystkich metod z interfejsu – oprócz tych, które są oznaczone jako default (od Javy 8).

W przypadku implementacji Comparable jesteśmy zmuszeni do zaimplementowania metody compareTo.

CompareTo odpowiada za logikę porównywania obiektów, w których jest zdefiniowania. Logika właśnie tej metody jest wykorzystywana do sortowania obiektów w kolekcji (jeżeli nie wiesz czym są kolekcje lub nie zbyt dobrze znasz to zagadnienie to zajrzyj do wpisu na temat kolekcji, aby móc w pełni zrozumieć ten wpis).

Zaglądając do dokumentacji interfejsu Comparable łatwo zauważyć, że metoda compareTo zwraca liczbę całkowitą, a nie wartość bool (true/false).

Dzieje się tak, ponieważ podczas porównywania obiektów możemy wyróżnić trzy stany:

  • Obiekt pierwszy jest większy
  • Obiekt pierwszy jest mniejszy
  • Obiekty są równe

Po prostu zmienna typu bool nie jest w stanie nam zapewnić trzech stanów, które musimy obsłużyć.

W tej sytuacji przychodzi nam typ całkowity, gdzie jej wartość jest utożsamiana z danym stanem:

  • -1 (ujemna) – Obiekt pierwszy jest mniejszy
  • 1 (dodatnia) – Obiekt pierwszy jest większy
  • – Obiekty są równe

Mówiąc o „obiekcie pierwszym” mam na myśli obiekt, na którym jest wykonywana metoda compareTo

Comparable w praktyce…

Dosyć tej teorii czas przejść do praktyki, czyli pokazać jak można posortować obiekty przy użyciu interfejsu Comparable.

Mając klasę Patient, musimy w niej zaimplementować interfejs Comparable.

public class Patient implements Comparable<Patient>

Teraz musimy zaimplementować również metodę toCompare:

@Override
public int compareTo(Patient o) {
    return 0;
}

Jak widać metoda póki co zwraca ciągle 0 – czyli obiekty zawsze będą równe. Czas to zmienić.

Niech funkcja sortuje kolejkę pacjentów według płci, niech kobiety mają pierwszeństwo w kolejce do lekarza. Zrobimy to w ten sposób:

@Override
public int compareTo(Patient o) {
    if(isMale) return 1;
    if(o.isMale) return -1;
    return 0;
}

Czyli jeżeli pierwszy pacjent jest kobietą to znaczy, że „jest większy”, jeżeli zaś drugi to drugi jest większy. Jeżeli są to panowie to zwróć 0 – obiekty równe.

Można to zapisać również przy pomocy operator trójargumentowego w ten sposób:

@Override
public int compareTo(Patient o) {
    return isMale ? 1 : o.isMale ? -1 : 0;
}

Mając już zdefiniowaną naszą klasę czas ją przetestować w main.

Na początek stwórzmy kilku pacjentów

Patient johny = new Patient("Johny", "Bravo", 23, true);
Patient anna = new Patient("Anna", "Kowalska", 21, false);
Patient pablo = new Patient("Pablo", "Escabo", 32, true);
Patient grazyna = new Patient("Grazyna", "Grazka", 38, false);

Następnie dodajmy ich do listy pacjentów

List<Patient> patients = new LinkedList<>();
patients.add(johny);
patients.add(anna);
patients.add(pablo);
patients.add(grazyna);

Na koniec wyświetlmy listę pacjentów

for (Patient patient :patients
     ) {
    System.out.println(patient.toString());
}

Aktualnie nasz kod prezentuje się tak

package pl.maniaq;

import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        Patient johny = new Patient("Johny", "Bravo", 23, true);
        Patient anna = new Patient("Anna", "Kowalska", 21, false);
        Patient pablo = new Patient("Pablo", "Escabo", 32, true);
        Patient grazyna = new Patient("Grazyna", "Grazka", 38, false);

        List<Patient> patients = new LinkedList<>();
        patients.add(johny);
        patients.add(anna);
        patients.add(pablo);
        patients.add(grazyna);

        for (Patient patient :patients
             ) {
            System.out.println(patient.toString());
        }



    }
}

Po wykonaniu programu uzyskujemy taki rezultat w konsoli:

Patient{name='Johny', lastName='Bravo', age=23, isMale=true}
Patient{name='Anna', lastName='Kowalska', age=21, isMale=false}
Patient{name='Pablo', lastName='Escabo', age=32, isMale=true}
Patient{name='Grazyna', lastName='Grazka', age=38, isMale=false}

Czyli kolejność dodawania została zachowana.

W sytuacji, gdy ktoś będzie chciał posortować pacjentów względem płci to wystarczy, że użyje metody sort w ten sposób:

Collections.sort(patients);

Dodajmy również wyświetlanie listy po przesortowaniu. Nasz kod wygląda teraz tak:

package pl.maniaq;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        Patient johny = new Patient("Johny", "Bravo", 23, true);
        Patient anna = new Patient("Anna", "Kowalska", 21, false);
        Patient pablo = new Patient("Pablo", "Escabo", 32, true);
        Patient grazyna = new Patient("Grazyna", "Grazka", 38, false);

        List<Patient> patients = new LinkedList<>();
        patients.add(johny);
        patients.add(anna);
        patients.add(pablo);
        patients.add(grazyna);

        for (Patient patient :patients
             ) {
            System.out.println(patient.toString());
        }

        Collections.sort(patients);
        System.out.println("Dane po przesortowaniu: ");

        for (Patient patient :patients
                ) {
            System.out.println(patient.toString());
        }


    }
}

Zobaczmy co teraz pokaże nam konsola:

Patient{name='Johny', lastName='Bravo', age=23, isMale=true}
Patient{name='Anna', lastName='Kowalska', age=21, isMale=false}
Patient{name='Pablo', lastName='Escabo', age=32, isMale=true}
Patient{name='Grazyna', lastName='Grazka', age=38, isMale=false}
Dane po przesortowaniu: 
Patient{name='Anna', lastName='Kowalska', age=21, isMale=false}
Patient{name='Grazyna', lastName='Grazka', age=38, isMale=false}
Patient{name='Johny', lastName='Bravo', age=23, isMale=true}
Patient{name='Pablo', lastName='Escabo', age=32, isMale=true}

Jak widać panie są na początku listy.

Różne możliwości…

Modyfikując metodę compareTo można osiągnąć przeróżne efekty sortowania. Można posortować pacjentów po wieku, najpierw po płci, a następnie po wieku lub po prostu alfabetycznie po nazwiskach.

Comparator

comparator

W przypadku, gdy nie chcemy definiować jednego sposobu sortowania obiektów, możemy stworzyć kilka Comparatorów i wykorzystywać je zależnie od potrzebnej sytuacji.

Na początku wrócimy do początkowej implementacji klasy Patient:

package pl.maniaq;

import java.util.Objects;

public class Patient{

    private String name;
    private String lastName;
    private Integer age;
    private Boolean isMale;

    public Patient(String name, String lastName, Integer age, Boolean isMale){
        this.name = name;
        this.lastName = lastName;
        this.age = age;
        this.isMale = isMale;
    }

    public String getName() {
        return name;
    }

    public String getLastName() {
        return lastName;
    }

    public Integer getAge() {
        return age;
    }

    public Boolean getMale() {
        return isMale;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Patient patient = (Patient) o;
        return Objects.equals(name, patient.name) &&
                Objects.equals(lastName, patient.lastName) &&
                Objects.equals(age, patient.age) &&
                Objects.equals(isMale, patient.isMale);
    }

    @Override
    public int hashCode() {

        return Objects.hash(name, lastName, age, isMale);
    }

    @Override
    public String toString() {
        return "Patient{" +
                "name='" + name + '\'' +
                ", lastName='" + lastName + '\'' +
                ", age=" + age +
                ", isMale=" + isMale +
                '}';
    }

}

Teraz czas na stworzenie osobnego Comparatora, który będzie odpowiedzialny za sortowanie pacjentów alfabetycznie.

package pl.maniaq;

public class PatientLastNameComparator {
}

Czas na implementację interfejsu Comparator

public class PatientLastNameComparator implements Comparator<Patient>

I ponownie musimy zaimplementować metodę, tym razem jest to compare:

@Override
public int compare(Patient o1, Patient o2) {
    return 0;
}

Jak widać metoda porównuję dwa obiekty, które są przekazane jako argumenty. W metodzie compareTo metoda była zadeklarowana w klasie, dlatego był przekazywany tylko jeden argument.

Posortujmy, więc naszych pacjentów alfabetycznie po nazwisku. Do tego celu możemy wykorzystać już zdefiniowaną przez autorów metodę compareTo z klasy String.

Wystarczy ją wywołać, nie musimy sami tworzyć Comparatora dla ciągów znaku.

@Override
public int compare(Patient o1, Patient o2) {
    return o1.getLastName().compareTo(o2.getLastName());
}

Ponownie wróćmy do maina, zatrzymajmy się na etapie listy – czyli tej linii kodu:

Collections.sort(patients);

Ta linia już nie zadziała, ponieważ metoda sort wymaga jako argumentu podania klasy implementującej interfejs Comparable. Ewentualnie możemy użyć naszego comparatora w ten sposób:

Collections.sort(patients, new PatientLastNameComparator());

Teraz dane będą już posortowane przy użyciu zewnętrznego komparatora.

Nasz kod wygląda teraz tak:

package pl.maniaq;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        Patient johny = new Patient("Johny", "Bravo", 23, true);
        Patient anna = new Patient("Anna", "Kowalska", 21, false);
        Patient pablo = new Patient("Pablo", "Escabo", 32, true);
        Patient grazyna = new Patient("Grazyna", "Grazka", 38, false);

        List<Patient> patients = new LinkedList<>();
        patients.add(johny);
        patients.add(anna);
        patients.add(pablo);
        patients.add(grazyna);

        for (Patient patient :patients
             ) {
            System.out.println(patient.toString());
        }

        Collections.sort(patients, new PatientLastNameComparator());
        System.out.println("Dane po przesortowaniu: ");

        for (Patient patient :patients
                ) {
            System.out.println(patient.toString());
        }


    }
}

Spójrzmy co wyświetla się w konsoli:

Patient{name='Johny', lastName='Bravo', age=23, isMale=true}
Patient{name='Anna', lastName='Kowalska', age=21, isMale=false}
Patient{name='Pablo', lastName='Escabo', age=32, isMale=true}
Patient{name='Grazyna', lastName='Grazka', age=38, isMale=false}
Dane po przesortowaniu: 
Patient{name='Johny', lastName='Bravo', age=23, isMale=true}
Patient{name='Pablo', lastName='Escabo', age=32, isMale=true}
Patient{name='Grazyna', lastName='Grazka', age=38, isMale=false}
Patient{name='Anna', lastName='Kowalska', age=21, isMale=false}

Jak widać nazwiska są posortowane alfabetycznie – czyli wszystko działa poprawnie.

Poprzez wyrażenie lambda…

Komparator można dużo szybciej przekazać do metody sort przy użyciu wyrażenia lambda – opisanie zalet i wad tego rozwiązania to temat na osobny wpis.

Poniżej jest krótki przykład jak to wygląda.

Collections.sort(patients, (p1, p2)-> {
    return p1.getLastName().compareTo(p2.getLastName());
});

Jak widać strzałka jak jest charakterystycznym znakiem wyrażeń lambda, w nawiasach są podawane argumenty, a dalej jest już ciało całej koniecznej metody.

Podałem ten przykład, abyś w przyszłości nie zdziwił się takim zapisem.

Na koniec…

Przygotowałem dla Ciebie kilka zadań, dzięki którym powtórzysz sobie podstawową wiedzę na temat interfejsów Comparable i Comparator.

  1. Dodaj 5 pacjentów do listy i posortuj pacjentów względem wieku – najstarsi mają mieć pierwszeństwo. Posortuj dane przy użyciu interfejsu Comparable.
  2. Dodaj 5 pacjentów do listy i posortuj pacjentów według płci i wieku – do sortowania wykorzystaj interfejs Comparator.

Warto również zajrzeć do dokumentacji klasy Collections, gdzie nie tylko jest zawarte sortowanie, ale wiele innych operacji na kolekcjach:

  • odwracanie kolejności elementów
  • zamiana elementów o podanych indeksach
  • wyszukiwanie min/max

I wiele, wiele więcje znajdziesz tutaj

W razie jakichkolwiek problem/pytań zachęcam do komentowania.