Doch was ist nun ein Algorithmus?
Laut der Definition welche wir im Kurs gefunden haben beschreibt der Algorithmus folgendes:
Der Algorithmus ist ein Grundbegriff in der Informatik. Er ist eine Vorschrift zur Transformation von Zeichen oder Elementen, wobei die Vorschrift endlich und präzise sein muss. Die Transformation erfolgt dabei schrittweise, elementar und effektiv.
Algorithmen sind nicht offen für Interpretationen, deshalb kann ein Kochrezept auch kein Algorithmus sein. Der Algorithmus terminiert, d. h. er hört nach endlicher Zeit mit einem Ergebnis auf. Terminieren sollte nicht mit deterministisch verwechselt werden, denn dies bedeutet, dass innerhalb des Algorithmus der jeweilige nächste Schritt definiert ist.
Ein Beispiel eines zu findenden Algorithmus
Sortiere eine Folge von Zahlen!
17, 8, 23, 1, 17, 9
Zunächst könnte man sich die Frage stellen wonach man diese Zahlenfolge eigentlich sortieren soll, denn dies ist in der Aufgabenstellung nicht eindeutig definiert. Wahrscheinlich würde die Mehrheit von uns beginnen die Zahlen von Klein nach Groß zu sortieren.
Ein möglicher Ansatz wäre dabei:
- nimm die kleinste Zahl aus der Folge heraus und schreibe sie in einer anderen Reihe hinter die letzte Zahl
- die Folge lautet dann 17,8,23,17,9 und an einer anderen Stelle steht irgendwo die 1
- als nächstes wird die Anweisung erneut aufgerufen, nämlich: nimm die kleinste Zahl aus der Folge heraus und schreibe sie in einer anderen Reihe hinter die letzte Zahl
- die Folge lautet dann 17,23,17,9 und an einer anderen Stelle steht irgendwo die 1 und danach die 8
- dieser Schritt wird immer wieder aufgerufen bis alle Zahlen aus der ursprünglichen Reihe in die neue Reihe sortiert sind, von Klein nach Groß
Diesen sich immer wiederholenden Aufruf der gleichen Funktion nennt man REKURSION.
Ein weiterer Ansatz, etwa wie er in JAVA praktiziert wird, wäre:
- vergleiche immer zwei nebeneinander stehende Zahlen darauf, ob die Nachfolgerzahl kleiner als die vorherige ist, wenn ja, dann müssen die Plätze getauscht werden
- anschließend wird die zweite Zahl mit deren Nachfolgerzahl verglichen und wenn nötig, der Platz getauscht
- dies wird solange durchgeführt, bis keine nachfolgende Zahl mehr kleiner ist
am Beispiel sieht das dann so aus:
17 8 23 1 17 9 17 und 8 werden verglichen und getauscht
8 17 23 1 17 9 17 und 23 werden verglichen und nicht getauscht
8 17 23 1 17 9 23 und 1 werden verglichen und getauscht
8 17 1 23 17 9 23 und 17 werden verglichen und getauscht
8 17 1 17 23 9 23 und 9 werden verglichen und getauscht
nun ist die Reihe einmal durchgetauscht, der Prozess beginnt von vorn
8 17 1 17 23 9 8 und 17 werden verglichen und nicht getauscht
8 17 1 17 23 9 17 und 1 werden verglichen und getauscht
8 1 17 17 23 9 17 und 17 werden verglichen und nicht getauscht
Aha, ich sehe jetzt, nachdem ich zwei Kommentare zu den vorher stehenden Bemerkungen geschrieben hatte, dass Du hier fortlaufend und mit Erkenntnis-Fortschritt, Deine Argumentation zum Algorithmus aufschreibst. Das ist im ersten Teil dieser Bemerkung auch schon recht gut gelungen. Kontrovers wäre nur die Bedingung der Termination. Denn es ist fraglos möglich, und geschieht auch, von Algorithmen zu verlangen, dass sie terminieren. Es gibt aber auch die Auffassung, dass es eine Eigenschaft im weiteren, nicht schon zur Definition gehörend, ist, ob ein Algorithmus terminiert oder nicht.
Das Sortierbeispiel hast Du liebevoll behandelt. Ich würde nur nicht die “andere Stelle” so sehr betonen. Denn die langsam augesammelte sortierte Teilfolge kann am Anfang der gegebenen Folge abgelegt werden, wodurch wir besser sehen, wie das Geschehen abläuft.
Das zweite, etwas weniger leicht zu durchschauende Sortierverfahren (Bubble sort) ist übrigens nichts, was mit Java zu tun hat. Ein algorithmisches Verfahren hat nie etwas mit einer bestimmten Programmiersprache zu tun.