Wenn Sie die Übungen der Folge 11 (Vokabelliste) erfolgreich bearbeitet haben, sind Sie dem Prinzip der linearen Suche bereits begegnet. In einer Liste deutsch/englischer Vokabeln sollte ein deutscher Begriff gesucht werden, zum Beispiel "Hund", und dann sollte die englische Übersetzung, also "dog", ausgegeben werden. Die Vokabeln waren in dem Objekt-Array Vokabelliste nicht sortiert, sondern befanden sich in der Reihenfolge in dem Array, wie sie vom Benutzer eingegeben worden sind.
public String english(String pDeutsch)
{
for (int i=0; i < anzahl; i++)
{
String d = liste[i].gibDeutsch();
if (pDeutsch.equals(d))
return liste[i].gibEnglisch();
}
return "Begriff nicht gefunden!";
}
Die lineare Suche, die Sie implementiert hatten, fing also ganz vorne im Array an zu suchen.
Das Deutsch-Attribut der jeweils nächsten Vokabel wurde mit der get-Methode gibDeutsch() sondiert und in der lokalen Variable d gespeichert. Dann wurde d mit dem Parameter pDeutsch verglichen, dazu wurde die equals()-Methode des Objektes pDeutsch verwendet. Stimmten beide Strings überein, wurde die englische Übersetzung zurück geliefert, und mit dem return-Befehl wurde die gesamte Methode auch beendet.
Fand die Suche keine Übereinstimmung in dem Array, wurde der String "Begriff nicht gefunden" zurück geliefert, und die Methode wurde beendet.
Definition: Lineare Suche:
Man fängt beim ersten Element der linearen Datenstruktur an zu suchen und macht so lange weiter, bis man
- entweder die gesuchten Daten gefunden hat oder
- am Ende der Datenstruktur angekommen ist und nichts gefunden hat.
Achten Sie darauf, dass diese Definition keinerlei Implementationshinweise enthält, sondern nur den "reinen" Algorithmus beschreibt, der dann in jeder beliebigen Programmiersprache implementiert werden kann.
Übungen
Ein Schüler hat einen Entwurf für eine Java-Methode erstellt, die in einem Objekt-Array CD[] nach einem bestimmten Begriff sucht. Falls die gesuchte CD gefunden wurde, soll der Titel der CD ausgegeben werden. Wurde die CD nicht gefunden, soll ein entsprechender Hinweis ausgegeben werden.
Hier das Flussdiagramm des Schülers für den linearen Suchalgorithmus:
Ein Flussdiagramm für eine lineare Suche
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Analysieren Sie diesen Entwurf und beurteilen Sie, ob er funktionieren könnte. Falls Sie Fehler finden, verbessern Sie den Entwurf.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Kleine Denkaufgabe
Kommen wir noch einmal auf die Vokabelliste der Folge 11 zurück. Eine Schülerin hat die Methode englisch() programmiert, welche die Übersetzung für einen deutschen Begriff zurück liefern soll:
public void englisch(String deutsch)
{
String d,e;
for (int vok=0; vok < anzahl; vok++)
{
d = liste[vok].gibDeutsch();
e = liste[vok].gibEnglisch();
if (deutsch.equals(d))
return e;
else
return "Wort nicht enthalten";
}
}
Dummerweise sind der Schülerin bei der Implementation zwei gravierende Fehler unterlaufen. Finden und korrigieren Sie diese Fehler!
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Systematische Untersuchung der linearen Suche
Bei der Analyse der verschiedenen Suchverfahren wäre es recht umständlich, wenn wir ständig in riesigen Bücher-, Zeitschriften- oder CD-Sammlungen wühlen müssten. Daher konstruieren wir uns ein sehr einfaches Modellsystem, das aus einem Array von lediglich 32 ganzen Zahlen besteht.
Vorgehen
Die lineare Suche demonstriert man aber am besten mit Hilfe eines unsortierten Arrays aus int-Zahlen.
Lineare Suche in einem Array aus 32 int-Zahlen
Autor: Ulrich Helmich 2016, Lizenz: siehe Seitenende.
Die Abbildung zeigt eine Liste von 32 Zufallszahlen mit Werten zwischen 1 und 32. Jede Zahl kommt genau ein Mal vor. Um die lineare Suche zu simulieren, suchen wir uns fünf beliebige (vorhandene) Zahlen aus, zum Beispiel 17, 28, 24, 16 und 11. Dann wird nachgeschaut, an welcher Position diese Zahlen in der Liste vorkommen. Die 17 kommt an der Position 20 vor, also benötigt der lineare Algorithmus 20 Suchschritte, um diese Zahl zu finden. Ähnlich wird mit den anderen vier Zahlen verfahren.
Ergebnisse
Rechnet man die Suchschritte für alle fünf Zahlen zusammen und dividiert anschließend durch 5, so erhält man für unser Beispiel den Durchschnittswert 14,8. Da der Array 32 Zahlen umfasst, liegt die Vermutung nahe, dass man bei N Zahlen wohl ungefähr N/2 Suchschritte zum Finden einer beliebigen Zahl benötigt. Der Suchaufwand kann also durch die Funktion O(N) = N charakterisiert werden.
Wieso heißt es dann nicht O(N) = N/2 ?
Bei dieser O-Notation ist es üblich, "Kleinigkeiten" wie Faktoren, Konstanten etc. zu vernachlässigen. Für einen linearen Algorithmus ist es egal, ob der Zeitaufwand N, N/2 , N/2 + 17 oder N/4 ist, man sagt allgemein, der Zeitaufwand lässt sich durch eine Funktion O(N) = N charakterisieren.
Wäre der Zeitaufwand dagegen quadratisch von N abhängig, wie dies z.B. beim Bubblesort der Fall ist (wegen der zwei for-Schleifen), würde man sagen, der Zeitaufwand lässt sich durch eine Funktion O(N) = N2 charakterisieren. Allgemein spricht man hier von der O-Notation, die häufig eingesetzt wird, um das Zeitverhalten von Algorithmen zu beschreiben (für Experten: Siehe Landau-Symbole in der Wikipedia).
Im günstigsten Fall (best case) befindet sich die gesuchte Zahl ganz vorne in der Liste und man braucht nur 1 Suchschritt. Im ungünstigsten Fall (worst case) befindet sich die gesuchte Zahl an der letzten Stelle des Arrays und man benötigt N Suchschritte. Wenn die Zahl gar nicht in der Liste vorhanden ist, braucht man ebenfalls N Suchschritte. Dieser Fall, dass die Zahl nicht vorhanden ist, wurde in unserem einfachen Modellsystem mit den 32 int-Zahlen allerdings noch nicht berücksichtigt, insofern ist das Modellsystem noch nicht perfekt.
Diese Suche ist noch nicht ganz realistisch, weil sie davon ausgeht, dass die gesuchte Zahl auch tatsächlich in der Liste vorhanden ist. Oft sucht man aber auch nach Sachen, die eben nicht in den Daten vorkommen. Dieser Fall wurde hier noch nicht berücksichtigt.
Berechnen Sie die durchschnittliche Suchzeit in dem Array aus Abb. 2, wenn folgende Zahlen gesucht werden:
5, 18, 19, 29, 33, 35, 38 und 41.
Beurteilen Sie dann,
a) ob sich die Suchzeit wesentlich verlangsamt hat und ob man
b) die Formel O(N) = N immer noch anwenden kann.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Schreiben Sie ein Java-Programm, das einen Array mit 100 zufällig ausgewählten int-Zahlen im Bereich zwischen 1 und 1000 erzeugt und in der Konsole anzeigt.
Zusatzpunkte gibt es, wenn die Konsolenausgabe besonders übersichtlich gestaltet wurde, zum Beispiel mit Hilfe von Tabulatoren "\t" zwischen den einzelnen Zahlen und genau 10 Zahlen pro Zeile.
Weitere Zusatzpunkte gibt es, wenn jede Zufallszahl nur einmal in dem Array vorkommt.
Weitere Zusatzpunkte Punkte gibt es für den Rest der Aufgabe: Statten Sie Ihr Programm mit einer Methode aus, die eine Suchzahl als int-Parameter annimmt und als int-Suchergebnis den Index der Zahl im Array ausgibt. So könnte die Signatur (der Kopf) dieser sondierenden Methode aussehen:
public int gibIndex(int suchzahl)
Sollte die Suchzahl nicht im Array vorkommen, soll der Wert 100 ausgegeben werden, da ja auch 100 Vergleiche benötigt wurden, um festzustellen, dass die Zahl nicht im Array vorhanden ist.
Lösungsvorschlag auf den Seiten für Lehrer(innen)
Übung 12.1-5 (PC, 3 Punkte)
Erweitern Sie das Programm aus Übung 12.1-4 folgendermaßen:
Es sollen die Suchzeiten für 100 zufällige Suchzahlen ermittelt werden. Aus diesen 100 Suchzeiten soll dann die durchschnittliche Suchzeit berechnet werden. Die Suchzahlen sollen im Bereich zwischen 1 und 1000 liegen, also im gleichen Wertebereich wie die Zahlen des Arrays.
Lösungsvorschlag auf den Seiten für Lehrer(innen)
Heben Sie den Quelltext gut auf, den Sie zum Lösen der Übung 12.1-5 erstellt haben. Sie können Teile des Quelltextes für die Übungen der Folge 12.2 gut gebrauchen!
Seitenanfang -
Weiter mit der binären Suche...