Vektor versus Liste

In diesem Programm wird nur eine eindimensionale Datenmenge sortiert (es lassen sich auch mehrdimensionale Datenmengen sortieren), d.h., die Elemente befinden sich in einer Reihenfolge mit eben zwei Enden. Es stellt sich dabei die Frage nach der Struktur der Datenmenge. Am naheliegendsten und einfachsten existieren dafür Datenfelder („Arrays“, eindimensonal als Vektoren, zweidimensional als Matrizen, ggf. noch höherdimensional) oder Listen.

Vektoren haben den Vorteil der freien Indizierbarkeit - wie die Indizes in der Mathematik - und damit des raschen, unkomplizierten Zugriffs auf seine einzelnen Elemente. Schwieriger ist es jedoch, wenn diese Felder bzw. Vektoren in der Länge verändert oder einzelne Elemente aus ihrem Inneren entfernt oder in das Innere eingefügt werden (sollen / müssen). Dann müssen sämtliche folgenden Elemente des Vektors ebenfalls bewegt, konkret um eine Position verschoben werden, was recht aufwendig ist.

Diesen Nachteil haben Listen - vor allem ihre beiden einfachsten Varianten, nämlich die einfach und die doppelt verketteten Listen - nicht. Ihre Elemente kennen jeweils nur ihren Nachfolger und sonst niemanden, bei doppelt verketteten auch ihren jeweiligen Vorgänger. Das hat große Vorteile beim Verändern der Listenlänge oder dem Hinzufügen oder Löschen einzelner Elemente in ihrem Innern. Es müssen nur Einträge in einem bis drei Listenelementen verändert werden. Schwieriger ist es jedoch, zu den einzelnen Listenelementen zu gelangen, da wegen des Fehlens des Index' keine Zugriffsfreiheit herrscht. Es muß sich vom ersten Element vorwärts - oder, bei doppelte verketteten Listen, vom letzten Element abwärts - mühsam zum gewünschten Element „gehangelt“ werden. Ein Beispiel einer einfach verketten Liste ist übrigens das Alphabet. Da man es i.d.R. nur vorwärts mehr oder weniger auswendig lernt und man deshalb immer nur den Nachfolger jedes Buchstabens kennt, kann man es auch nur in dieser Reihenfolge (wenigstens flüssig) aufsagen.

In diesem Programm ist die zu sortierende Menge ein Vektor. Zum einen, weil es die Algorithmen einfacher gestaltet, zum anderen wegen des starken Graphik(ausgabe)bezuges. Dennoch gibt es in diesem Programm auch Sortieralgorithmen mit Listen. Zwischen dem Sortiermengenvektor und den jeweiligen Listen wird dann „in einem Rutsch“ elementweise übergeben.

Noch kompliziertere Datenstrukturen (z.B. Bäume, Skiplisten) sind möglich, doch tendenziell verkomplizieren diese naturgemäß auch die Sortieralgorithmen, die auf sie angewandt werden.

Kontaktformular