Jelenlegi hely

21.3. Algoritmusok

Ebben a fejezetben a Java platform által kínált újra felhasználható, sokalakú algoritmusok egy részével foglalkozunk. Mindegyikük a Collections osztály statikus metódusa. Az algoritmusok széles skálája a List-eknél működik. De egy pár tetszőleges kollekciók esetében is működik.

Rendezés

A sort algoritmus újrarendezi a listát. A művelet két formája adott. Az egyszerűbb forma veszi a listát, és rendezi azt az elemek természetes (alapértelmezett) sorrendjében.

Itt egy egyszerű program, ami kiírja betűrendben a parancssori paramétereket:

import java.util.*;
public class Sort {
    public static void main(String args[]) {
        List<String> l = Arrays.asList(args);
        Collections.sort(l);
        System.out.println(l);
    }
}

Futtassuk a programot:

java Sort i walk the line

A következő kimenetet kapjuk:

[i, line, the, walk]

A program megmutatta, hogy ezt az algoritmust nagyon könnyű használni.

Tegyük fel, hogy vannak anagrammákat tartalmazó szólistáink. Szeretnénk kiíratni azokat a listák hossza szerinti csökkenő sorrendben, de csak az adott méretnél (pl. 8) nem kevesebb elemű listákat. A következő példa megmutatja, hogy hogyan érhetjük el ezt a sort metódus második formájának segítségével.

Maguk a szólisták egy m objektumban vannak tárolva. Erről leválogatjuk a megfelelő hosszúságúakat. Ezután a kód rendezi a listát, összehasonlítást végez, és végrehajtja a fordított méret szerinti rendezést. Végül a kód ismét végigfut a listán és kiírja az elemeket (a szavak csoportját):

List<List<String>> winners = new ArrayList<List<String>>();
for (List<String> l : m.values())
    if (l.size() >= minGroupSize)
        winners.add(l);
Collections.sort(winners, new Comparator<List<String>>() {
    public int compare(List<String> o1, List<String> o2) {
        return o2.size() - o1.size();
    }
});
// Szócsoportok kiírása
for (List<String> l : winners)
    System.out.println(l.size() + ": " + l);

Futtassuk a programot, a minimum anagramma csoport méretével (8) együtt a következő kimenetet kapjuk:

12: [apers, apres, asper, pares, parse, pears, prase, presa, rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter, slater, staler, stelar, talers]
10: [least, setal, slate, stale, steal, stela, taels, tales, teals, tesla]
9: [estrin, inerts, insert, inters, niters, nitres, sinter, triens, trines]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape, secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats, septal, staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas, retsina, stainer, stearin]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse, spears]
8: [enters, nester, renest, rentes, resent, tenser, ternes, treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas, searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts, recast, traces]

Keverés

A keverés algoritmusa bizonyos értelemben az ellenkezőjét teszi, mint amit a rendezés tesz. Lerombol bármilyen rendezést, ami esetleg található a listában. Ez az jelenti, hogy ez az algoritmus újrarendezi a listát úgy, hogy a véletlenszerűséget használja az összes azonos valószínűséggel bekövetkező permutációhoz, feltételezve a ténylegesesen rendszertelen forrást. Például tudjuk használni a keverést egy pakli kártya megkeveréséhez a kártya objektumainak listájában. Ezenkívül hasznos tesztesetek, helyzetek generálásához is.

Keresés

A bináris keresés algoritmus (binarySearch metódus) elemeket keres a rendezett listában. Ennek az algoritmusnak két formája van. Az első vesz egy listát és egy elemet, amit keres (egy kereső kulcsot). Ez a forma feltételezi, hogy a lista elemei rendezve vannak a természetes rendezés szerint a tárolóban. A második forma nem az alapértelmezett rendezést alkalmazza, hanem még egy Comparator paramétert is vár.

A visszatérési érték azonos mindkét formában. Ha a lista tartalmazza keresett elemet, visszatér az indexével. Ha nem, a visszatérési érték negatív, és egyben utal arra is, hogy hol kellene lennie az elemnek, ha szerepelne a listában.

A következő példa keresi egy adott elem meglétét, és beilleszti a helyére, ha még nem szerepel:

int pos = Collections.binarySearch(list, key);
    if (pos < 0)
       l.add(-pos-1);