Algorithmen

Aufgabenstellung

Beantworten Sie die folgenden Fragen mit eigenen Worten:

• Was ist ein Algorithmus?

• Was ist der Unterschied eines Algorithmus zu einem Computerprogramm?

• Was ist ein Flussdiagramm und wofür ist es gut?

• Was ist der worst case beim Bubblesortalgorithmus?

• Gibt es eine Liste, bei der Selectionsort weniger Schleifendurchgänge als Bubblesort hat?

• Wieso kann Selectionsort in bestimmten Situationen trotzdem effizienter sein als Bubblesort? Betrachten Sie hierzu die Anzahl der vertauschten Elemente.

Lösungsvorschlag

• Ein Algorithmus ist eine Kette eindeutiger Anweisungen, die ein Problem oder eine Gruppe von Problemen lösen.

• Ein Algortithmus hat erstmal nichts mit Programmieren zu tun sondern beschreibt formal den Lösungsweg zum Lösen eines Problems. Ein Programm ist jedoch, in der Regel, eine für den Computer lesbare Implementierung eines oder mehrer Algorithmen.

• Ein Flussdiagramm ist eine graphische Darstellung eines Algorithmus oder eines Programmflusses. Je komplexer Algorithmen werden, desto schwieriger und unübersichtlicher wird es, diese nur mit Worten zu definieren. Ein Flussdiagramm bietet die Möglichkeit einer formalen, übersichtlichen Beschreibung.

• Der worst case ist der Fall, bei dem ein Algorithmus die maximale Anzahl an Wiederholungen durchläuft, bevor er terminiert. Im Fall von Bubblesort ist dies eine absteigend sortierte Liste, da die zusätzliche Abbruchbedingung, dass keine Vertauschungen in der letzten Iteration der inneren Schleife durchgeführt wurden, nie erreicht wird.

• Selectionsort hat immer mehr oder, im worst case, gleich viele Schleifendurchläufe wie Bubblesort.

• Bubblesort hat weniger Wiederholungen, weil neben dem finden des größten Elementes in der Regel auch der Rest der Liste etwas weiter sortiert wird. Dies führt jedoch dazu, dass bei jedem Durchlauf der inneren Schleife im Durchschnitt mehr Anweisungen ausgeführt werden als bei Selectionsort. Gerade im worst case ist Bubblesort signifikant langsamer, weil in jeder Wiederholung nicht nur zwei Elemente verglichen, sondern auch getauscht werden, während bei Selectionsort nur ein Mal pro Durchlauf der äußeren Schleife getauscht wird. Und auch wenn die zu sortierenden Listen unsortiert sind, kann Selectionsort effizienter sein, wenn die Sortierung auf einem System ausgeführt wird, auf dem das Speichern von Daten wesentlich länger dauert als das Lesen.