Triedenie

<< Modifikátory viditeľnosti | Obsah | Java Collections Framework >>

Triedenie (sorting) je typickým príkladom problému, s ktorým sa i normálny človek bežne stretáva, a ktorý je predmetom dlhoročného stále trvajúceho výskumu. Triedenie je potrebné na usporiadanie mien v telefónnom zozname, manažér potrebuje zotriedené údaje na to, aby zistil finačný zisk za jednotlivé divízie, a používateľ Windowsu chce mať utriedené súbory, aby v nich vedel rýchlo vyhľadávať.

V súčasnosti existuje množstvo triediacich algoritmov rozličnej zložitosti a implementačnej náročnosti. Niektorým z nich sa budete venovať v budúcom semestri. V tomto kurze sa naučíme len základné techniky triedenia a spôsoby, ktorými je ho možné dosiahnuť.

Keďže bežný vývojár nepotrebuje vlastnú implementáciu triediacich algoritmov, v Jave existuje viacero zabudovaných spôsobov, ktorými možno triediť nielen bežné ,,utriediteľné" veci (čísla, reťazce), ale aj akékoľvek vlastné objekty.

Triedenie čísiel

Najtypickejším príkladom je triedenie čísiel, ktoré sú uložené v poli, čo je možné dosiahnuť prostými dvoma riadkami.

int[] platy = new int[] { 2400, 1000, 3700, 1800};
Arrays.sort(platy);
// pole <platy> je teraz utriedené
[$[Get Code]]

Zavolaním statickej metódy Arrays.sort(pole) vieme zotriediť ľubovoľné pole čísiel podľa veľkosti.

Metóda sort() je preťažená pre mnoho základných typov. Vieme triediť pole shortov, longov, či doubleov alebo floatov.

Triedenie reťazcov

Triedenie reťazcov je úplne analogické k triedeniu čísiel. Reťazce budú usporiadané v lexikografickom usporiadaní (t.j. normálne utriedenie podľa abecedy ako v telefónnom zozname):

Reťazec a_1 a_2 ... a_n je v usporiadaní pred reťazcom b_1 b_2 ... b_n, ak

  • buď a_1 < b_1
  • alebo existuje k z intervalu [1,n] také, že pre každé i < k je a_i = b_i a a_k < b_k

V prípade, že sú reťazce nerovnakej dĺžky, kratší reťazec sa vyplní medzerami na dĺžku dlhšieho, a predpokladá sa, že znak medzery je menší ako akýkoľvek iný znak.

Podľa definície je

  • PES < VELRYBA, lebo P < V. V skutočnosti však porovnávame PES.... < VELRYBA
  • PERO < PES, lebo porovnávame PERO < PES. a existuje k = 3, kde prefixy reťazcov sa rovnajú (PE == PE) a R < S.

Kód pre utriedenie:

String[] mená = new String[] { "Zuzana", "Adam", "Cyril", "Boris"};
Arrays.sort(mená);
// pole <mená> je teraz utriedené
[$[Get Code]]

Triedenie objektov

V Jave však existuje možnosť triediť ľubovoľné objekty, a nie iba čísla či reťazce. V tomto prípade však musíme poznať kritérium, na základe ktorého vieme povedať, že jeden objekt je v usporiadaní pred nejakým iným.

  • Kedy je číslo v usporiadaní pred iným? Ak je menšie ako to druhé.
  • Kedy je reťazec v usporiadaní pred iným? Ak je v lexikografickom usporiadaní pred druhým reťazcom.

V týchto prípadoch sú kritériá jasné. Čísla a reťazce majú svoje prirodzené usporiadanie (natural ordering). Čo však s objektami? Kedy je film v usporiadaní pred iným? Musíme sa rozhodnúť a dohodnúť. Môžeme napríklad povedať, že film je v usporiadaní pred iným filmom, ak je jeho názov v lexikografickom usporiadaní pred názvom druhého filmu. (Potom bude Casablanca pred The Matrix).

Rozhodnutie vieme zaviesť do ľubovoľnej triedy pomocou interfejsu java.lang.Comparable. Ak trieda implementuje tento interfejs (a teda prekrýva jeho jedinú metódu compareTo(), vie plniť rolu objektu, ktorý sa vie porovnať s iným. Táto metóda nasledovnú hlavičku:

int compareTo(TypObjektu druhýObjekt)
[$[Get Code]]

a od implementátora sa očakáva, že táto metóda vráti

  • záporné číslo ak je objekt, ktorého metódu sme volali, v usporiadaní pred objektom druhýObjekt, teda je "menší" ako druhýObjekt
  • 0, ak sú objekty v usporiadaní rovnaké
  • kladné číslo, ak je objekt, ktorého metódu sme volali, v usporiadaní za objektom druhýObjekt, teda je "väčší" ako druhýObjekt

Príklad triedy pre triedu Film je nasledovný:

import java.lang.Comparable;

public class Film implements Comparable<Film> {
  private String nazovFilmu;

  public int compareTo(Film inyFilm) {
    // zistíme, či nazovFilmu je v usporadaní pred inyFilm.getNazovFilmu()
  }
}
[$[Get Code]]

Pri uvádzaní interfejsu Comparable nás čaká drobný syntaktický zádrheľ: do lomených zátvoriek musíme uviesť dátový typ, ktorý bude použitý v porovnávaní. Keďže v tomto prípade porovnávame Film, v deklarácii implements musíme uviesť Comparable<Film>.

Ako zistíme, či je názov aktuálneho filmu v usporiadaní pred iným? Jednoducho: reťazec String má metódu compareTo(), ktorá presne vráti záporné číslo, nulu alebo kladné číslo, v závislosti od toho, či je reťazec pred, rovnako, alebo za druhým reťazcom. Táto metóda sa používa pri normálnom triedení Stringov.

public int compareTo(Film inyFilm) {
  return this.nazovFilmu.compareTo(inyFilm.getNazovFilmu());
}
[$[Get Code]]

Ak vieme porovnať dve inštancie Filmov, nič nám nebráni triediť pole filmov:

FilmNaDvd matrix = new FilmNaDvd();
// ... nastavime vsetky atributy

FilmNaPaske shawshank = new FilmNaPaske();
// ... nastavíme všetky atribúty

FilmVPocitaci fontana = new FilmVPocitaci();
// ... nastavíme všetky atribúty

Film[] filmy = new Film[] { matrix, shawshank, fontana };
Arrays.sort(filmy);

// pole <filmy> je teraz zotriedené podľa názvu
[$[Get Code]]

Triedenie rovnakých objektov rôzne

Triedenie filmov s využitím interfejsu Comparable má jednu nevýhodu: kým čísla a reťazce majú jasne definované prirodzené usporiadanie, v prípade filmov jestvuje viacero kritérií, podľa ktorých ich môžeme triediť. Čo ak chceme usporiadavať filmy podľa hodnotenia? Alebo podľa počtu hercov? Metódou copareTo() však vieme nastaviť iba jednu možnosť usporiadania.

Na porovnávanie objektov sa môžeme pozerať dvojako, presnejšie, z dvoch perspektív. Z prvej perspektívy môžeme povedať ja sa viem porovnať s iným objektom." Druhá perspektíva hovorí ja viem porovnať dva objekty." Prvej perspektíve zodpovedá metóda compareTo() uvedené priamo v triede, ktorej objekty porovnávame (u nás vo Filme).

Druhej perspektíve zodpovedá interfejs java.util.Comparator a metóda int compare(TypObjektu o1, TypObjektu o2). Trieda, ktorá implementuje Comparator, dokáže porovnať dva objekty a povedať, či je prvý v usporiadaní pred druhým.

public class FilmPodľaMenaComparator implements Comparator<Film> {
  public int compare(Film film1, Film film2) {
    return film1.getNazovFilmu().compareTo(film2.getNazovFilmu());
  }
}
[$[Get Code]]

V príklade sme urobili triedu implementujúcu Comparator filmov (opäť použijeme trik z lomenými zátvorkami), ktorý porovná dva filmy a určí kritérium ich porovnania -- v tomto prípade porovná názvy filmov.

Implementovať komparátor podľa hodnotenia je potom ľahké:

import java.util.Comparator;

public class FilmPodľaHodnoteniaComparator implements Comparator<Film> {
        public int compare(Film film1, Film film2) {
                return film1.getHodnotenie() - film2.getHodnotenie();
        }
}
[$[Get Code]]

A ako zotriedime samotné objekty? Metóda sort() má preťaženú metódu s dvoma parametrami: prvý je pole, ktoré chceme triediť, a druhý inštancia typu Comparator. Stačí teda vytvoriť inštanciu niektorého z vyššieuvedených komparátorov a budeme vedieť triediť ľubovoľné objekty podľa ľubovoľného kritéria.

FilmNaDvd matrix = new FilmNaDvd();
// ... nastavime vsetky atributy
FilmNaPaske shawshank = new FilmNaPaske();
// ... nastavíme všetky atribúty
FilmVPocitaci fontana = new FilmVPocitaci();
// ... nastavíme všetky atribúty

Film[] filmy = new Film[] { matrix, shawshank, fontana };

Comparator<Film> kritérium = new FilmPodľaHodnoteniaComparator();
Arrays.sort(filmy, kritérium);

// pole <filmy> je teraz zotriedené
[$[Get Code]]

Pole filmy sa teraz zotriedilo podľa hodnotenia. Ak chceme zmeniť kritérium na triedenie, stačí zmeniť jediný riadok:

Comparator<Film> kritérium = new FilmPodľaMenaComparator();
[$[Get Code]]

Výmenou jediného riadku sme zmenili správanie algoritmu, a to vďaka polymorfizmu, kvôli ktorému sa premenná typu Comparator správa raz tak, raz onak -- a to v závislosti od skutočného typu premennej.

Ak by sme niekedy potrebovali triediť v opačnom poradí nie je potrebné písať nový komparátor s obrátenou logikou. Stačí nám na to zavolať "otáčač komparátorov" a použiť ho namiesto pôvodného koparátora

Comparator<Film> porovnavac = FilmPodlaHodnoteniaComparator();

Arrays.sort(zoznamFilmov, Collections.reverseOrder(porovnavac));
// pole je utriedené podľa hodnotenia zostupne
[$[Get Code]]

V praxi sa ešte často stretneme s tým, že potrebujeme triediť reťazce nie lexikograficky ale tak ako to určuje slovenská abeceda. V štandardnom lexikografickom usporiadaní napríklad platí, že Z < Á alebo CH < D. V slovenčine však platia opačné znamienka. Na vyriešenie tohto problému stačí poučiť komparátor, ktorý už za nás naprogramovali autori Javy a ktorý rieši triedenie podľa národných zvyklostí.

import java.text.Collator;
import java.util.Arrays;
import java.util.Locale;

public class Skuska {

        public static void main(String[] args) {
                String[] mená = new String[]{"Adam", "Cecília", "Cháron","Ábel","Daniel"};

                Collator skPorovnavac = Collator.getInstance(new Locale("sk"));

                Arrays.sort(mená, skPorovnavac);
                System.out.println(Arrays.toString(mená));  //Vypíše sa [Ábel, Adam, Cecília, Daniel, Cháron]
        }
}
[$[Get Code]]