Kurs Java Podstawy - rozszerzony

Sortowanie kolekcji, interfejsy Comparator i Comparable

Hej! Chciałbym przyjrzeć się bliżej tematowi sortowania w Javie. Temat banalny, ale warty uwagi. Sławek pisał już wcześniej na podobny temat, oczywiście polecam lekturę jego artykułu.

Jak zwykle przedstawię wszystko na przykładzie. Kod do tego artykułu jest dostępny do pobrania na końcu artykułu.

 

Załóżmy, że mamy prostą klasę Człowiek posiadającą podstawowe atrybuty: imię, nazwisko oraz płeć.

 

public class Czlowiek {

	private char plec;
	private String imie;
	private String nazwisko;

	public Czlowiek(char plec, String imie, String nazwisko) {
		this.plec = plec;
		this.imie = imie;
		this.nazwisko = nazwisko;
	}

	@Override
	public String toString() {
		return nazwisko + " " + imie+" (" + plec +")" ;
	}

}

 

W programie tworzymy sobie listę osób.

import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) {

		List<Czlowiek> ludzie = new ArrayList<Czlowiek>();
		ludzie.add(new Czlowiek('K', "Asia", "Wczorajsza"));
		ludzie.add(new Czlowiek('M', "Marcin", "Nikczemny"));
		ludzie.add(new Czlowiek('M', "Slawek", "Abacki"));
		ludzie.add(new Czlowiek('K', "Kasia", "Borowik"));
		ludzie.add(new Czlowiek('K', "Dorota", "Borowik"));
		ludzie.add(new Czlowiek('M', "Tomek", "Daszek"));
		ludzie.add(new Czlowiek('K', "Ania", "Daszek"));

		for(Czlowiek czlowiek : ludzie) {
			System.out.println(czlowiek);
		}
	}

}

 

Na razie mamy nieposortowaną listę osób.

Wczorajsza Asia (K)
Nikczemny Marcin (M)
Abacki Slawek (M)
Borowik Kasia (K)
Borowik Dorota (K)
Daszek Tomek (M)
Daszek Ania (K)

 

Naszym celem jest posortowanie listy ludzi po nazwisku, a jeśli jest takie same, to po imieniu.

Oczywiście moglibyśmy napisać sortowanie sami, ale nie po to korzystamy z Javy :)

 

Jednym z podejść jest zaimplementowanie interfejsu Comparable w klasie którą którą chcemy sortować. W tym wypadku sprawdzi się coś takiego:

public class Czlowiek implements Comparable<Czlowiek>{

	private char plec;
	private String imie;
	private String nazwisko;

	public Czlowiek(char plec, String imie, String nazwisko) {
		this.plec = plec;
		this.imie = imie;
		this.nazwisko = nazwisko;
	}

	@Override
	public String toString() {
		return nazwisko + " " + imie+" (" + plec +")" ;
	}

	@Override
	public int compareTo(Czlowiek o) {
		int porownaneNazwiska = nazwisko.compareTo(o.nazwisko);

		if(porownaneNazwiska == 0) {
			return imie.compareTo(o.imie);
		}
		else {
			return porownaneNazwiska;
		}
	}

}

Zmiany których dokonałem to dopisanie implements Comparable<Czlowiek>. Interfejs ten wymusza zaimplementowanie metody compareTo.

Metoda compareTo zwraca liczbę całkowitą. Jeśli obiekt dla którego wywołujemy metodę ma wartość mniejszą od tego podanego w parametrze zwracana jest wartość mniejsza od 0, jeśli wyższą to większa od 0, natomiast jeśli są równe to zwracane jest 0.

Jako typ podajemy klasę do której chcemy porównywać nasz obiekt. W tym wypadku będzie to ta sama klasa. W tym momencie nie jestem w stanie wymyślić przykładu kiedy byłaby to inna klasa, może macie jakieś pomysły? 

Do porównywania korzystam z metody compareTo dla Stringa i porównuję najpierw nazwiska. Jeśli są takie same (wartość zwracana to 0), wtedy porównuję imiona.

Zwróćcie uwagę, że użyłem tutaj bloków if(){}else{}, pomimo, że są one właściwie niepotrzebne i można by zapisać to bez użycia klamerek. Jest to kwestia dobrych nawyków i utrzymywania czystości kodu. Sam dopiero od niedawna się do tego przekonuję, ale ułatwia to czytanie kodu w przyszłości.

 

W celu posortowania listy skorzystamy z statycznej metody sort() w klasie Collections.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

	public static void main(String[] args) {

		List<Czlowiek> ludzie = new ArrayList<Czlowiek>();
		ludzie.add(new Czlowiek('K', "Asia", "Wczorajsza"));
		ludzie.add(new Czlowiek('M', "Marcin", "Nikczemny"));
		ludzie.add(new Czlowiek('M', "Slawek", "Abacki"));
		ludzie.add(new Czlowiek('K', "Kasia", "Borowik"));
		ludzie.add(new Czlowiek('K', "Dorota", "Borowik"));
		ludzie.add(new Czlowiek('M', "Tomek", "Daszek"));
		ludzie.add(new Czlowiek('K', "Ania", "Daszek"));

		System.out.println("Nieposortowanie: ");
		for(Czlowiek czlowiek : ludzie) {
			System.out.println(czlowiek);
		}

		Collections.sort(ludzie);

		System.out.println("\nPosortowane: ");
		for(Czlowiek czlowiek : ludzie) {
			System.out.println(czlowiek);
		}
	}

}

 

Wynik jest taki jak oczekiwany:

Nieposortowanie: 
Wczorajsza Asia (K)
Nikczemny Marcin (M)
Abacki Slawek (M)
Borowik Kasia (K)
Borowik Dorota (K)
Daszek Tomek (M)
Daszek Ania (K)

Posortowane: 
Abacki Slawek (M)
Borowik Dorota (K)
Borowik Kasia (K)
Daszek Ania (K)
Daszek Tomek (M)
Nikczemny Marcin (M)
Wczorajsza Asia (K)

 

Cel osiągnięty! :)

 

No ale w życiu nie jest tak łatwo, bo dajmy na to, że zgłosił się do nas klient i chciałby także mieć możliwość sortowania ludzi najpierw po płci, a następnie po nazwisku i imieniu. Co w takim przypadku? Jeśli zmienimy compareTo w klasie Czlowiek stracimy możliwość aktualnego sortowania.

Tym razem skorzystamy znowu z metody Collections.sort, ale teraz tej przyjmującej 2 parametry sort(List<T>, Comparator<? super T>)

Musimy zaimplementować klasę implementującą interfejs Comparator<T>. Ponieważ porównujemy obiekty klasy Czlowiek, to typem <T> jest <Czlowiek>. Ten interfejs wymaga zaimplementowania metody compare(), która jest bardzo podobna do poprzedniej compareTo().

Tutaj przeniosłem program do osobnej metody, ze względu na to, że w statycznej metodzie main() nie można tworzyć obiektu klasy prywatnej bez stworzenia instancji, więc postanowiłem to w ten sposób zapisać, żeby było czytelniej.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.program();
	}

	private void program() {
		List<Czlowiek> ludzie = new ArrayList<Czlowiek>();
		ludzie.add(new Czlowiek('K', "Asia", "Wczorajsza"));
		ludzie.add(new Czlowiek('M', "Marcin", "Nikczemny"));
		ludzie.add(new Czlowiek('M', "Slawek", "Abacki"));
		ludzie.add(new Czlowiek('K', "Kasia", "Borowik"));
		ludzie.add(new Czlowiek('K', "Dorota", "Borowik"));
		ludzie.add(new Czlowiek('M', "Tomek", "Daszek"));
		ludzie.add(new Czlowiek('K', "Ania", "Daszek"));

		System.out.println("Nieposortowanie: ");
		for(Czlowiek czlowiek : ludzie) {
			System.out.println(czlowiek);
		}

		Collections.sort(ludzie);

		System.out.println("\nPosortowane: ");
		for(Czlowiek czlowiek : ludzie) {
			System.out.println(czlowiek);
		}

		Collections.sort(ludzie, new KomparatorPlec());

		System.out.println("\nPosortowane po plci: ");
		for(Czlowiek czlowiek : ludzie) {
			System.out.println(czlowiek);
		}
	}

	private class KomparatorPlec implements Comparator<Czlowiek> {

		@Override
		public int compare(Czlowiek o1, Czlowiek o2) {
			int plec =  o1.getPlec() - o2.getPlec();
			if(plec == 0) {
				return o1.compareTo(o2);
			}
			return plec;
		}

	}

}

Tutaj korzystamy z własności typów prostych w Javie. Możemy zastosować operator odejmowania dla literek. Zostaną one wcześniej przekonwertowane na ich wartość w kodzie ASCII. K ma wartość 75, a M 77. Podobnie jak w poprzednim przypadku jeśli otrzymamy tą samą wartość, to porównujemy dalej, z tym, że korzystamy już z wcześniej zaimplementowanej metody compareTo() dla klasy Czlowiek.

W klasie Czlowiek musiałem dopisać getter dla płci, ze względu na to, że została ona zadeklarowane jako pole prywatne.

public class Czlowiek implements Comparable<Czlowiek>{

	private char plec;
	private String imie;
	private String nazwisko;

	public Czlowiek(char plec, String imie, String nazwisko) {
		this.plec = plec;
		this.imie = imie;
		this.nazwisko = nazwisko;
	}

	@Override
	public String toString() {
		return nazwisko + " " + imie+" (" + plec +")" ;
	}

	@Override
	public int compareTo(Czlowiek o) {
		int porownaneNazwiska = nazwisko.compareTo(o.nazwisko);

		if(porownaneNazwiska == 0) {
			return imie.compareTo(o.imie);
		}
		else {
			return porownaneNazwiska;
		}
	}

	public char getPlec() {
		return plec;
	}

}

 

Mam nadzieję, że jest to chociaż w pewny stopniu zrozumiałe. Jak zwykle dzięki za uwagę! Jeśli znacie jakieś inne ciekawe podejścia do sortowania, to oczywiście chętnie się o nich dowiem :)

Projekt do pobrania tutaj.

Komentarze

Jędrzej

"K ma wartość 75, a K 77." Wut?

Marcin Kunert

Oczywiście chodziło o M z wartością 77.
Poprawiłem, dzięki! :)

Radek

Warto odnotować, że takie napisanie komparatora nie gwarantuje poprawnej obsługi polskich nazwisk, imion. Przykład: Żurek, Żółty.

Mr

Właśnie takiego artykułu potrzebowałem do pełnego zrozumienia tematu. Dzięki.

Tomasz Waszczyk

Fajny artykuł, warto dodać że jeśli wybieramy z bazy jakieś dane to dużo lepiej skorzystać z ORDER BY w zapytaniu i pracę obliczeniową pozostawić bazie niż przerzucać ją na JVM.

Marcin Kunert

Dzięki! :)
Słuszna uwaga z sortowaniem korzystając z silnika bazy danych, z pewnością zyskamy na wydajności.