Sławomir Czerwiński

Chciałbym wykorzystać utworzony wcześniej interfejs Tree<T> do zaimplementowania algorytmu QuickSort. Algorytm ten opiera się o podział elementów na dwie grupy – mniejsze oraz większe od wybranego. Operację powtarza się aż do uzyskania jednoelementowych grup.

Algorytm może działać w oparciu o strukturę drzewiastą – dla danego węzła każdy element dodawany jest do poddrzewa elementów mniejszych albo większych. Przekazywanie elementów do kolejnego poddrzewa trwa do momentu utworzenia nowego liścia.

Zacznę od utworzenia klasy:

import java.util.List;

public class SortingTree<T extends Comparable<? super T>>
extends AbstractTree<T> {
}

Klasa dziedziczy z AbstractTree<T> – do tego momentu wszystko jest jasne. Ale co oznacza SortingTree<T extends Comparable<? super T>>? Po kolei:

Comparable

Interfejs generyczny zawierający metodę int compareTo(T), gdzie T jest typem obiektów, do których można porównać dany obiekt.

? super T

Dowolny typ, z którego dziedziczy T.

Comparable<? super T>

Interfejs do klasy obiektów, które mogą być porównane z obiektami dowolnie określonej klasy, z której dziedziczy T. Na przykład:

• java.util.Date implements Comparable<java.util.Date>
• java.sql.Date extends java.util.Date implements Comparable<java.util.Date>
• java.sql.Time extends java.util.Date implements Comparable<java.util.Date>
• java.sql.Timestamp extends java.util.Date implements Comparable<java.util.Date>

T extends Comparable<? super T>

Dowolnie określony typ dziedziczący z Comparable<? super T>.

SortingTree<T extends Comparable<? super T>>

Drzewo, którego elementami są dowolne obiekty, jakie można porównać do obiektów ich dowolnie określonego nadtypu.

Czyli T może być dowolnym z wymienionych wcześniej typów (java.util.Date, java.sql.Date, java.sql.Time, java.sql.Timestamp) ale też np. java.lang.Integer czy java.lang.Double.

Pora przejść do pól… element zawarty w węźle oraz poddrzewa elementów mniejszych (before) i większych (after) od tego elementu:

private T element;

private SortingTree<T> before;
private SortingTree<T> after;

Wszystkie pola inicjowane są w konstruktorze jako null:

public SortingTree() {
    super();

    this.element = null;
    this.before = null;
    this.after = null;
}

Do tej pory pozostała jeszcze jedna niezaimplementowana metoda – get. Pobiera ona element zawarty w danym węźle drzewa:

public T get() {
    return this.element;
}

Co prawda drzewo posiada już metodę addChild, lecz nie może ona zostać użyta do sortowania elementów. Utworzona została dodatkowa metoda add, która pozwala umieścić nowy element we właściwej gałęzi (2–7). Jeżeli dany węzeł nie posiada jeszcze elementu, nowy element zostaje do niego przypisany (9–15):

public synchronized void add(T element) {
    if (this.element != null) {
        if (element.compareTo(this.element) < 0) {
            this.before.add(element);
        } else {
            this.after.add(element);
        }

    } else {
        this.element = element;
        this.before = new SortingTree<T>();
        this.after = new SortingTree<T>();
        super.addChild(this.before);
        super.addChild(this.after);
    }
}

Dodałem też dwie metody pozwalające na dodanie od razu całej tablicy lub kolekcji elementów dziedziczących z T:

public synchronized void addAll(T[] elements) {
    for (T element : elements)
        this.add(element);
}

public synchronized void addAll(Iterable<? extends T> elements) {
    for (T element : elements)
        this.add(element);
}

Na samym końcu pozostaje jeszcze pobrać posortowane elementy. Aby uniknąć tworzenia nowej kolekcji, zostanie ona przekazana przez parametr. Dodawane są do niej kolejno:

• rekursywnie posortowane elementy z poddrzewa elementów mniejszych,
• element zawarty w danym węźle,
• rekursywnie posortowane elementy z poddrzewa elementów większych.

Lista, do której dodawane są elementy musi zawierać elementy dowolnie określonej klasy, z której dziedziczy klasa T.

public synchronized void addSortedItems(List<? super T> list) {
    if (this.element != null) {
        this.before.addSortedItems(list);
        list.add(this.element);
        this.after.addSortedItems(list);
    }
}

Następnym razem zajmę się testowaniem utworzonego właśnie drzewa sortującego. Jeżeli do tej pory klasy generyczne nie są niczym skomplikowanym, kolejne przykłady z pewnością to zmienią.