Třídění v jazyce Java

Vložil v 1.1.2015

Sorting, resp. ordering v jazyce Java je velmi jednoduchý. Třídit se dají jak pole, tak i kolekce. Dají se třídit primitivní i komplexní typy. Třídění je součástí Java Collections Framework.

Třídění polí

Pole se dají třídit pomocí statické metody sort třídy Arrays, která má řadu možných parametrů. Pro třídění pole primitivních typů není třeba nic jiného než samotné pole, vložené jako jediný parametr.

1
2
3
4
5
6
7
8
9
public static void sortPrimitives() {
String[] values = new String[] { "x", "i", "a", "d" };
Arrays.sort(values);
for (String value : values) {
System.out.println(value);
}
}

Pole komplexních typů se třídí stejným způsobem, jen s jedním malým rozdílem.
Mějme třídu Person.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Person {
private int id;
private String name;
public int getId() {
return this.id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return this.name;
}
public void setName(String name) {
this.name = name;
}
public Person(int id , String name) {
super();
this.id = id;
this.name = name;
}
}

Zkusme setřídit pole objektů tohoto typu stejným způsobem jako v předchozím případě.

1
2
3
4
5
6
7
8
9
10
11
public static void sortArray() {
Person[] people = new Person[] { new Person(4, "Xavier"),
new Person(2, "Beata"), new Person(1, "Alois"),
new Person(3, "Cecilie") };
Arrays.sort(people);
for (Person person : people) {
System.out.println(person.getId() + ": " + person.getName());
}
}

V takovém případě vyhodí kompiler výjimku.

1
2
3
4
5
6
Exception in thread "main" java.lang.ClassCastException: Person cannot be cast to java.lang.Comparable
    at java.util.ComparableTimSort.countRunAndMakeAscending(Unknown Source)
    at java.util.ComparableTimSort.sort(Unknown Source)
    at java.util.Arrays.sort(Unknown Source)
    at Program.sortArray(Program.java:72)
    at Program.main(Program.java:14)

Důvodem je prostý fakt, že třídící algoritmus se nemá čeho chytit. Neví, podle čeho chceme to pole setřídit. Podle pole ID? Podle pole NAME? Nebo podle hash hodnoty objektu?
Aby mohl naše pole setřídit, musíme mu říci, podle čeho. To se dělá dvěma způsoby. Buď s pomocí implementace rozhraní Comparable, anebo s použitím další třídy, která implementuje rozhraní Comparator.

Třídění pole objektů s použitím implementace rozhraní Comparable

První metoda třídění pole komplexních typů počítá s implementací rozhraní Comparable<? extends T>, které definuje jedinou metodu, a to compareTo(T t). Metoda má jediný parametr, kterým je objekt stejného typu, se kterým se má daný objekt porovnat. Výstupem je celé číslo, které je buď menší než nula (-1), nula (0), anebo větší než nula (1), tedy zda je daný objekt menší, stejný či větší než objekt, předaný v parametru. Viz.
Naši třídu si tedy upravíme následujícím způsobem.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Person implements Comparable<Person> {
private int id;
private String name;
// Getters and Setters...
// Constructor...
@Override
public int compareTo(Person person) {
return this.getName().compareTo(person.getName());
}
}

Teď už bude algoritmus vědět, že chceme pole setřídit podle jména, a to vzestupně, tudíž nebude mít námitky. Výstupem metody sortArray() tedy bude seznam jmen, uvozených identifikátorem, tedy podle očekávání:

1
2
3
4
1: Alois
2: Beata
3: Cecilie
4: Xavier

Pokud chceme setřídit sestupně, stačí v metodět compareTo otočit pořadí porovnávaných objektů.

Třídění pole objektů s použitím implementace rozhraní Comparator

To je moc pěkný, řeknete si, ale co když chci třídit pokaždé jinak? Jednou vzestupně, podruhé sestupně, potřetí třeba podle identifikátoru…? I na to collection framework pamatuje. Pro tento účel bylo zavedeno rozhraní Comparator<? extends T>, které definuje metodu compare(T t0, T t1). Tato metoda má dva vstupní parametry, kterými jsou objekty, jež se mají porovnat. Výstupem je opět celé číslo. Je to tedy v podstatě stejné, jen s tím rozdílem, že porovnání se provádí v samostatném objektu, který se přikládá jako další parametr metody sort().

Mějme tedy dva comparatory. Jeden setřídí naše pole vzestupně a druhý sestupně podle jména.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Comparator;
public class PersonSortByNameAsc implements Comparator<Person> {
@Override
public int compare(Person person1, Person person2) {
return person1.getName().compareTo(person2.getName());
}
}
public class PersonSortByNameDesc implements Comparator<Person> {
@Override
public int compare(Person person1, Person person2) {
return person2.getName().compareTo(person1.getName());
}
}

Následně setřídíme dané pole pomocí těchto dvou komparátorů.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void sortArrayUsingComparator() {
Person[] people = new Person[] { new Person(4, "Xavier"),
new Person(2, "Beata"), new Person(1, "Alois"),
new Person(3, "Cecilie") };
Arrays.sort(people, new PersonSortByNameAsc());
for (Person person : people) {
System.out.println(person.getId() + ": " + person.getName());
}
System.out.println();
Arrays.sort(people, new PersonSortByNameDesc());
for (Person person : people) {
System.out.println(person.getId() + ": " + person.getName());
}
}

Výstup je v takovémto případě podle očekávání:

1
2
3
4
5
6
7
8
9
1: Alois
2: Beata
3: Cecilie
4: Xavier
4: Xavier
3: Cecilie
2: Beata
1: Alois

Jak vidíte, nic složitého v tom není. S použitím externích komparátorů není třeba, aby třída Person implementovala rozhraní Comparable.

Třídění kolekcí

Pro třídění kolekcí lze použít podobný postup jako pro třídění polí, jen se volá statická metoda sort() třídy Collections. Předchozí snippety se tedy dají snadno upravit.

Třídění kolekce Comparable objektů:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void sortCollection() {
List<Person> people = new ArrayList<Person>();
people.add(new Person(4, "Xavier"));
people.add(new Person(2, "Beata"));
people.add(new Person(1, "Alois"));
people.add(new Person(3, "Cecilie"));
Collections.sort(people);
for (Person person : people) {
System.out.println(person.getId() + ": " + person.getName());
}
}

Třídění kolekce s použitím externího Comparatoru.

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void sortCollectionUsingComparator() {
List<Person> people = new ArrayList<Person>();
people.add(new Person(4, "Xavier"));
people.add(new Person(2, "Beata"));
people.add(new Person(1, "Alois"));
people.add(new Person(3, "Cecilie"));
Collections.sort(people, new PersonSortByNameAsc());
for (Person person : people) {
System.out.println(person.getId() + ": " + person.getName());
}
}

Použité algoritmy

Arrays.sort() používá pro třídění primitivních typů vytuněný Quicksort.

The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy’s “Engineering a Sort Function”, Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

Quicksort tu byl tedy upraven tak, aby eliminoval ty stavy, které degradují výkon algoritmu. Časová složitost algoritmu je zpravidla O(n log n), a to v případě takových datových sestav, jejichž setřídění s použitím běžného quicksortu dává složitost kvadratickou, tedy O(n2), jako například při Bubblesortu.

Collections.sort() používá upravený Mergesort.

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

Arrays.sort(Object[]), tedy třídění pole objektů, pak používá taktéž Mergesort, stejně jako při třídění kolekce.

Různé typy složitostí lze vidět zde pro nižší hodnoty a zde pro vyšší hodnoty.

Možnost paralelního třídění polí

Od verze Java 8 lze pole třídit vícevláknově. Pole je při třídění rozsekáno na menší celky a každý z těchto celků je setříděn ve vlastním vlákně, načež se tyto části opět slepí dohromady. Kolekce paralelní třídění nepodporují. Od verze 8 definuje rozhraní List vlastní metodu sort, která funguje stejně jako Collection.sort(), ale pro paralelní setřídění mě napadá jen export pomocí List.toArray(), Arrays.parallelSort() a následné opětovné sestavení kolekce pomocí Arrays.asList(). Anebo si napsat vlastní implementaci paralelního třídění.

Použité zdroje

  • http://cs.wikipedia.org/wiki/Asymptotická_složitost
  • http://en.wikipedia.org/wiki/Time_complexity
  • http://www.perlmonks.org/?node_id=227909
  • http://pages.cpsc.ucalgary.ca/~eharris/past/cpsc319/w12/tut01/
  • http://ttux.net/post/java-8-new-features-release-performance-code/
Buďte sociálové a sdílejte!
Java, Vývoj, , ,

Komentování je uzavřeno.