Zum Hauptinhalt springen

Woche 9: Merge Sort & Verkettete Listen

Nach dieser Woche können Sie …

  • erklären, warum Algorithmen mit einer schnelleren Laufzeitklasse besser sind
  • angeben, ob Mergesort oder Insertion Sort schneller ist
  • dynamische Datenstrukturen implementieren
  • neue Operationen für einfach verkettete Listen implementieren
  • gegebene Nested Classes verwenden
  • begründen, welche Datenstruktur für einen gegebenen Einsatzzweck sinnvoll ist

Ähnlich wie beim Suchen werden wir am Montag ein Sortierverfahren kennenlernen, dass große Datenmengen schneller sortieren kann als insertion Sort. Dabei lernen wir eine in der Informatik oft verwendete Lösungsstrategie: Wir zerlegen unser Probleme so oft in kleinere Teilprobleme, bis wir sie einfach lösen können.

Wir kennen schon Arrays, um eine Menge von Objekten vom gleichen Typ zu speichern. Wir wissen aber auch, dass Arrays unflexibel sind, wenn wir später einmal die Anzahl der Elemente verändern wollen. Am Mittwoch lernen wir Listen kennen, die gewisse Einschränkungen von Arrays nicht aufweisen. Tatsächlich wird in der Praxis auch viel öfter mit Listen statt Arrays gearbeitet – die verschiedenen Arten von Listen, die in Java schon eingebaut sind, schauen wir uns später in der Vorlesung an.

Literatur

Falls Sie die Themen dieser Woche nochmal in der Literatur nachlesen wollen, können Sie sich die Abschnitte Mergesort und Linked lists in Introduction to Programming in Java ansehen.

Vorlesung​

Mergesort​

CodeFolienAufzeichnung
Freiwillige Zusatzaufgaben
  • Schreiben Sie Mergesort so um, dass es mit Sortable (aus der letzten Vorlesung) funktioniert.
  • zum Knobeln: Unseren WordCounter könnte man auch ohne Sortieren implementieren. Finden Sie ein Verfahren, das ohne eine Sortierung auskommt.

Einfach verkettete Listen​

CodeFolienAufzeichnung
Freiwillige Zusatzaufgabe
  • Erweitern Sie die Listen-Klassen um eine Methode insert(int index, int value), um value am gegebenen Index einzufügen. insert(0, 42) würde also z. B. die 42 vorne einfügen und alle anderen Elemente um eine Position nach hinten verschieben. (Im Foliensatz finden Sie Abbildungen zum Einfügen in der Mitte einer Liste.) Sie können erstmal davon ausgehen, dass index nicht größer als die Länge der Liste ist.
Berühmte Persönlichkeiten der Informatik

John von Neumann war Mathematiker und hat unter anderem das Sortierverfahren Mergesort erfunden. Außerdem hat er die Von-Neumann-Architektur entwurfen, auf der alle modernen Computer basieren: Programmbefehle und Daten liegen im selben Speicher. Mit diesem Konzept war es nun – anders als bei Lochkarten oder fest verdrahteten Programmen – schnell möglich, Programme zu ändern oder Programme sich selbst während der Laufzeit ändern zu lassen.

Foto von John von Neumann