Algorithmen

manuell ermittelt werden.

    Abbildung 1: Schrittfolge bei der Entwicklung eines Algorithmus
    Pseudocode
    Bei der Pseudocodenotation handelt sich um eine Mischung aus natürlicher Sprache und einer höheren Programmiersprache. Die Beschreibung des Algorithmus gelingt exakter als bei ausschließlicher Verwendung einer natürlichen Sprache, jedoch ist man nicht an alle Zwänge der endgültigen Programmiersprache gebunden. Die technischen Facetten rücken in den Hintergrund. Der Fokus liegt auf dem Fachkonzept. Pseudocode stellt auch ein Mittel der Kommunikation zwischen dem Fachexperten und dem Programmierer dar. Ebenfalls bietet sich die Möglichkeit, den Übergang von der natürlichen Sprache zum (reinen) Programmcode schrittweise auszugestalten, was insbesondere bei einer hohen Komplexität hilfreich ist. Der Pseudocode sollte selbsterklärend und auch ohne exakte Kenntnis der Programmiersprache verstanden werden. Anderseits sollte es leicht möglich sein, anhand des Pseudocodes direkt die Implementierung vorzunehmen. Damit kann Pseudocode als die eigentliche „Sprache“ für die Entwicklung (mathematischer) Algorithmen angesehen werden. Bei der Verwendung bedient man sich bekannter Schlüsselwörter und Konzepte, die Bestandteil einer jeden modernen Programmiersprache sind, z. B.:
Modulelemente wie Programmnamen und Klassennamen
Fallunterscheidungen, wie IF…THEN…ELSE oder SWITCH…CASE
Funktionsaufrufe
Schleifen, wie WIEDERHOLE…SOLANGE/ BIS oder REPEAT…UNTIL oder WHILE…DO
Kommentare
    Zu beachten ist, dass eine eindeutige Vorgabe zur Symbolik nicht existiert. Meist orientiert man sich an der Zielsprache, was jedoch zu Lasten der allgemeinen Verständlichkeit gehen kann.

1.3Basisalgorithmen: Sortieren und Suchen
    Als typische Vertreter von Algorithmen haben wir entschieden, Sortier- und Suchverfahren etwas näher zu betrachten. Dank moderner Klassenbibliotheken und Frameworks kann das Sortieren von Datenbeständen und/oder die Suche in diesen relativ problemlos erfolgen, ohne dass man über genaue Kenntnisse der internen Vorgänge dieser Algorithmen verfügen muss. Dennoch: grundlegende Kenntnisse über die Funktionsweisen dieser Algorithmen können nützlich, gelegentlich auch notwendig sein. Das Sortieren umfangreicher Datenbestände ist ein zeitaufwändiger Vorgang. Spielt der Faktor Zeit eine Rolle – z. B. in Echtzeitanwendungen – kann es von Vorteil sein, nach Optimierungsmöglichkeiten Ausschau zu halten und das implementierte Suchverfahren der Klassenbibliothek gegen eine effizientere Variante auszutauschen. Hierfür sind gute Kenntnisse über die Funktionsweise dieser Algorithmen eine Voraussetzung. Die Konzepte sind gewissermaßen sprachneutral. Unsere Quellcodebeispiele setzen auf C# (für die .NET-Plattform) und Delphi, gelegentlich ist auch Pseudocode dargestellt.
    Sortieren – das Wichtigste im Überblick
    Ein Sortierverfahren ist ein Algorithmus, der dazu dient Elemente einer Liste zu sortieren. Voraussetzung ist, dass zwischen den Elementen eine Ordnung möglich ist. Es müssen also Vorgänger- und Nachfolgerbeziehungen (bzw. Gleichheit) zwischen zwei zu vergleichenden Elementen bezüglich des Sortierkriteriums herstellbar sein. Typische Beispiele sind die lexikografische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. Diese Forderung wird als Trichotomie bezeichnet und sagt aus, dass für alle Elemente einer Menge bezüglich der Schlüssel a, b gilt:
a < b oder
a = b oder
a > b
    Die Transitiviät gewährleistet, dass die Sortierung widerspruchsfrei durchgeführt werden kann: Ist das Element a vor dem Element b und das Element b vor dem Element c in der Liste einzusortieren, so folgt unweigerlich, dass das Element a vor dem Element c anzuordnen ist. Wichtige Merkmale eines Sortieralgorithmus sind die Zahl der durchschnittlich benötigten Iterationen, bis die gewünschte Reihenfolge der Elemente vorliegt, und der benötigte Speicherplatzbedarf. Die Zahl der Iterationen gibt die Komplexität des Algorithmus an.
    Sortierverfahren können in interne und externe Verfahren unterteilt werden. Ist es möglich die zu sortierenden Daten komplett im Hauptspeicher (innerhalb einer Datenstruktur, z. B. ein Array) zu sortieren, so liegt ein internes Sortierverfahren vor. Bei größeren Datenbeständen ist es nicht handhabbar, sämtliche Daten innerhalb des Arbeitsspeichers zu halten. Zum Einsatz kommen dann externe Speichermedien wie Festplatten oder Streamer. Die Effizienz des