Algorithmen

Algorithmen, präzise Beschreibungen zur Erreichung einer bestimmten Aufgabe, stehen im Mittelpunkt der Informatik. Im Kontext der Programmierung werden Algorithmen typischerweise zunächst spezifiziert und dann durch Quellcode implementiert.

Das Konzept der Effizienz ist oft mit Algorithmen verbunden. Die Effizienz eines Programms, d. h. die schnelle Berechnung der benötigten Informationen, ist ein integraler Bestandteil eines Programms. Wenn es beispielsweise zwei Tage dauern würde, einen Algorithmus auszuführen, der die Vorhersage für das Wetter von morgen berechnen soll, wären die Ergebnisse nicht sehr nützlich! Ebenso wird eine Benutzerin oder ein Benutzer, die oder der eine TV-Programmübersicht ansieht, keinen Nutzen daraus ziehen, wenn die Informationen erst geladen werden, nachdem die Sendung bereits zu Ende ist.

Im weiteren Sinne ist das schnelle Abrufen und Anzeigen von Informationen ein wesentlicher Bestandteil der Funktionalität jeder Anwendung. Als Nächstes werfen wir einen Blick auf Algorithmen, die mit dem Abrufen und Sortieren von Informationen zu tun haben. Obwohl die folgenden Beispiele Arrays verwenden, funktionieren die gezeigten Algorithmen auch mit anderen Datenstrukturen, die zur Speicherung von Informationen verwendet werden, wie z. B. Listen.

Informationen sortieren

Wenn die einem Computer gegebenen Informationen (Daten) keiner Regel folgen und nicht sortiert sind, ist es für den Computer mühsam, diese Informationen abzurufen. Wir brauchen Ordnung!

Selection-Sort

Jede Programmiereranfängering und jeder Programmieranfänger sollte mindestens einen Sortieralgorithmus kennen (d. h. eine Methode zum Sortieren eines Arrays). Lassen Sie uns mit einem „klassischen“ Sortieralgorithmus, dem Selection-Sort, vertraut machen. Dies erfolgt durch eine Programmierübung.

Eingebaute Sortieralgorithmen in Java

Java bietet eine beträchtliche Anzahl an sofort einsatzbereiten Sortieralgorithmen. Arrays können (in ihrer natürlichen Reihenfolge) mit der Klassenmethode sort der Klasse Arrays sortiert werden. Listen können (in ihrer natürlichen Reihenfolge) mit der Klassenmethode sort der Klasse Collections sortiert werden.

int[] numbers = {8, 3, 7, 9, 1, 2, 4};
System.out.println(Arrays.toString(numbers));
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(8);
numbers.add(3);
numbers.add(7);
System.out.println(numbers);
Collections.sort(numbers);
System.out.println(numbers);

Javas eingebaute Sortieralgorithmen funktionieren mit primitiven Datentypen und einigen der eingebauten Referenztypen von Java, wie String. Damit unsere eigenen Klassen sortiert werden können, müssen wir Java einige Hinweise geben, wie dies zu tun ist, da die Klassen selbst keine Informationen darüber enthalten, wie die von ihnen erstellten Objekte sortiert werden sollen. Auf die Sortierung von Objekten, die aus selbst erstellten Klassen stammen, werden wir im Fortgeschrittenenkurs der Programmierung zurückkommen.

Informationssuche

Als nächstes betrachten wir Algorithmen, die für die Informationssuche gedacht sind.

Lineare Suche

Die lineare Suche ist ein Suchalgorithmus, der Informationen in einem Array sucht, indem er jeden Wert im Array nacheinander durchgeht. Wenn der gesuchte Wert gefunden wird, wird sein Index sofort zurückgegeben. Wenn der gesuchte Wert nicht gefunden wird, gibt die lineare Suche die Information zurück, dass der Wert nicht gefunden wurde – typischerweise bedeutet dies, dass -1 anstelle eines gültigen Index zurückgegeben wird.

public class Algorithms {

    public static int linearSearch(int[] array, int searched) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == searched) {
                return i;
            }
        }

        return -1;
    }
}

Im schlimmsten Fall, d. h. wenn der gesuchte Wert nicht gefunden wird, muss der Algorithmus so viele Vergleiche durchführen, wie es Werte im Array gibt. In einem Array mit beispielsweise 10 Millionen Werten bedeutet dies 10 Millionen Vergleiche. Wenn mehr als eine Suche durchgeführt wird, ist es sinnvoll, die Effizienz zu verbessern.

Binäre Suche (auch bekannt als "half-inbterval search" oder auch logarithmische Suche)

Wenn die gesuchten Daten sortiert sind, kann die Suche viel effizienter durchgeführt werden als bei der linearen Suche. Die Idee der binären Suche besteht darin, die Suche nach dem gesuchten Wert im mittleren Index des Arrays (oder der Liste) zu beginnen, den dort gefundenen Wert mit dem gesuchten Wert zu vergleichen und bei Bedarf (d. h. wenn der Wert dort nicht gefunden wird) die Hälfte des Suchbereichs auszuschließen. Der Algorithmus wird ausführlicher in der folgenden Präsentation vorgestellt.