Zum Hauptinhalt springen

Woche 8: Binäre Suche & Sortieren durch Einfügen

Zulassung

Beachten Sie, dass das Übungsblatt in dieser Woche das letzte Blatt ist, mit dem Sie Punkte für den ersten Zulassungsteil sammeln können. (siehe organisatorische Informationen)

Nach dieser Woche können Sie …

  • lineare Suche implementieren
  • erklären, warum binäre schneller als lineare Suche ist
  • die Geschwindigkeit bekannter Algorithmen unabhängig von der Hardware angeben
  • erklären, warum meistens Standardimplementierungen eigenen Implementierungen vorgezogen werden sollten
  • einen Sortieralgorithmus implementieren

Wenn Sie viele Daten in Ihrer Anwendung (z. B. tausenden Kundendatensätze) in einem Array speichern und einen bestimmten Datensatz finden wollen, gibt es verschiedene Suchstrategien. In dieser Woche lernen Sie eine Strategie kennen, die schneller ist, als alle Datensätze von vorne nach hinten durchzugehen. (Und nach Weihnachten lernen wir eine noch schnellere Möglichkeit kennen.)

Eine Voraussetzung für das schnelle Suchverfahren von dieser Woche ist, dass die Daten sortiert sind. Wie Sie selbst Ihre Daten sortieren können, schauen wir uns am Mittwoch an. Dabei nehmen wir Interfaces, die wir letzte Woche kennengelernt habe, zur Hilfe, damit unsere Sortier-Methode mit beliebigen Objekten funktioniert.

Literatur

Falls Sie die Themen dieser Woche nochmal in der Literatur nachlesen wollen, können Sie sich die Abschnitte Binary Search und Insertion Sort in Introduction to Programming in Java ansehen.

Vorlesung​

Lineare & Binäre Suche​

CodeFolienAufzeichnung
Freiwillige Zusatzaufgaben
  • Erstellen Sie eine Klasse Studi, die eine Matrikelnummer und einen Namen speichert und Methoden getMatrikelnummer und toString besitzt. Legen Sie ein Studi-Array mit Studi-Objekten an. Implementieren Sie dann eine lineare Suche nach Studi-Objekten, wobei Studi-Objekte anhand Ihrer Matrikelnummer gefunden werden. Falls kein passender Eintrag gefunden wird, soll die Methode null zurückgeben.
  • Implementieren Sie eine Such-Methode private static int[] search(int[] haystack, int needle), die ein Array mit 2 Indices zurückgibt: der ersten bzw. letzten Position, an der needle in haystack vorkommt

Sortieren durch Einfügen​

Code vorabFolienAufzeichnung
Freiwillige Zusatzaufgabe

Erzeugen Sie ein Array von Studi-Objekten (vgl. vorherige Zusatzaufgabe) und sortieren Sie diese absteigend nach Matrikelnummer. Können Sie die Sortierung auch so umsetzen, dass das Original-Array dabei nicht verändert wird, sondern eine Kopie sortiert und zurückgegeben wird?

📄️ Guter Programmierstil

Wenn unsere Programme komplexer werden, wird es immer schwieriger, einen guten Überblick über den Code zu behalten. Insbesondere wenn wir später nochmal Änderungen am Code vernehmen müssen, ist es hilfreich, wenn er übersichtlich und nachvollziehbar geschrieben ist. In der Vorlesung haben wir zwischendurch immer mal wieder angemerkt, wie ordentlicher und strukturierter Java-Code aussehen soll, damit man selbst und andere ihn gut lesen können. Folgende Regeln sollten Sie kennen:

Berühmte Persönlichkeiten der Informatik

Der schweizer Informatiker Niklaus Wirth hat mehrere Programmiersprachen (u. a. Pascal) entwickelt und dafür die sognannte Erweiterte Backus-Naur-Form, eine Möglichkeit, die Syntax von Programmierpsrachen formal aufzuschreiben, erfunden. Für die Entwicklung innovativer Programmiersprachen erhielt er 1984 den Turing-Award. Wirth ist außerdem bekannt für seine guten Lehrbücher, under anderem Algorithms + Data Structures = Programs (≈ Rezepte + Zutaten = Kuchen). Nach ihm ist Wirth’s Law benannt:

Software is getting slower more rapidly than hardware becomes faster.

Video über Wirth von Prof. Harmeling (Login in Mediathek erforderlich)

Foto von Niklaus Wirth