Sortieren und Suchen

Sortieren

Das haben wir die letzten Wochen gemacht. Wir haben gemeinsam Selectionsort, Quicksort und Bubblesort implementiert. Der Code für eine abstrakte Sort Klasse, Quicksort und Selectionsort ist hier in diesem Repository.

Suchen

Lineare Suche

Für den Einstieg habe ich hier eine abstrake Klasse Search erstellt, die festlegt, wie die Suchfunktion aller Suchverfahren aussieht, damit wir diese im Code einfach austauschen können. Außerdem gibt es die Klasse LinearSearch, diese sucht einfach nur vom ersten Element, alle nacheinander durch, bis das Ziel gefunden wird, oder das Array zu Ende ist. Dafür muss das Array streng genommen nicht sortiert sein, aber für die anderen Verfahren dann schon.

Binäre Suche

Eventuell erinnert ihr euch aus vorherigen Kursen noch an das Zahlenraten Spiel. Der Computer generiert eine Zahl zwischen null und 100 und es muss versucht werden die Zahlt mit so wenigen Schritten wie möglich zu finden. Das gleiche Vorgehen kann man auch zum Suchen in einem sortierten Array verwenden. Dazu einfach das Element in der Mitte des Arrays prüfen und dann schauen, ob man im Array weiter vorn, oder hinten suchen muss. Um dieses Verfahren (und viele andere Suchverfahren) anwenden zu können, muss das Array (oder auch die Liste, oder Baum) sortiert sein.

Aufgaben:

1. Binäre Suche implementieren, als neue Klasse, wie bei der linearen Suche
2. eine Klasse Auto erstellen (oder irgend etwas anderes)
   • ein Auto könnte beispielhaft eine Anzahl PS, Farbe, Anzahl Türen/Sitze haben.
   • danach muss im Such und Sortierverfahren einmal die Vergleuchsoperation so angepasst werden, dass Autos zb nach Ps sortiert werden.
   • bei einem echten Programm hätte man meistens auch so eine Art Datentyp, aber warscheinlich mit einer Art ID, nach der sortiert wird, das könnt ihr auch gerne machen.
   • dann erstellt ihr in der main am Ende ein Array vom Typ Auto, generiert da welche rein und lasst eure angepasste funktion darüber laufen.

Wikipedia Erklärung

Git Hinweise