Beispiel

Im folgenden soll eine bildliche Darstellung der Vorgehenweise des ShellSort auf einer Datenmenge bestehend aus N Elementen gezeigt werden. Dabei wird zuerst der Snapshot nur eine Stufe gezeigt, bei dem h schon relativ klein ist.

$\begin{picture}(9,3) \psset{dimen=inner} \psset{linewidth=.01} % psframe(0,0)... ...\psframe(8.4,0) (8.6,2.8) % 28 \psframe(8.7,0) (8.9,0.4) % 29 \par\end{picture}$

Die ausgefüllten Elemente bilden zusammen ein Menge und werden über ein h = 3 indiziert. Diese Menge wird mit dem InsertionSort geordnet.

$\begin{picture}(9,3) \psset{dimen=inner} \psset{linewidth=.01} % psframe(0,0)... ...\psframe(8.4,0) (8.6,2.8) % 28 \psframe(8.7,0) (8.9,0.4) % 29 \par\end{picture}$

Nun wird die gleiche Maske (der Indezes) um ein Element verschoben, womit sich eine neue Menge bildet. Das heisst der Abstand zwischen den Elementen bleibt gleich, da sich der Wert von h nicht ändert. Die so entstandene neue Menge wird wie vorhin mit dem InsertionSort sortiert.

$\begin{picture}(9,3) \psset{dimen=inner} \psset{linewidth=.01} % psframe(0,0)... ...r=black](8.4,0) (8.6,2.8) % 28 \psframe(8.7,0) (8.9,0.4) % 29 \par\end{picture}$

Nach der Sortierung sieht die Gesammtmenge wie folgt aus:

$\begin{picture}(9,3) \psset{dimen=inner} \psset{linewidth=.01} % psframe(0,0)... ...r=black](8.4,0) (8.6,2.8) % 28 \psframe(8.7,0) (8.9,0.4) % 29 \par\end{picture}$

Nun wird ein letztes mal die Maske verschoben. Würde die Maske danach nochmal verschoben werden, würde man eine Menge in Betracht ziehen, welchen schon durch eine frühere Sortierung erledigt wurde.

$\begin{picture}(9,3) \psset{dimen=inner} \psset{linewidth=.01} % psframe(0,0)... ...psframe[fillstyle=solid,fillcolor=black](8.7,0) (8.9,0.4) % 29 \par\end{picture}$

Nach der Sortierung:

$\begin{picture}(9,3) \psset{dimen=inner} \psset{linewidth=.01} % psframe(0,0)... ... \psframe[fillstyle=solid,fillcolor=black](8.7,0) (8.9,3) % 29 \par\end{picture}$

Wie zu erkennen ist, kristallisiert sich in der gesammten Menge eine gewissen grobe Ordnung heraus, da das Sortieren ``in-place'' geschieht. Weiter zu beachten ist auch, daß kleine Werte über eine größere Distanz hinweg mit wenigen Tauschoperationen eingereiht wurden, da die Aufteilung in Teilmengen nicht zusammenhängend geschieht. Dies ist die Effizienz beim ShellSort gegenüber dem InsertionSort.

Im nächten Schritt wird der Wert für h neu berechnet (verkleinert) und das Schema beginnt von vorne. In hiesigen Beispiel würde h den Wert von 1 erreichen und so eine Menge von der Größe der Originalmenge bilden, diese mit dem InsertionSort sortieren und terminieren, da es keine weiteren Teilmengen gibt.

$\begin{picture}(9,3) \psset{dimen=inner} \psset{linewidth=.01} % psframe(0,0)... ...1,0) (8.3,2.8) \psframe(8.4,0) (8.6,2.8) \psframe(8.7,0) (8.9,3) \end{picture}$

Nochmal zu betonen ist, daß die Effizienz des ShellSort darin besteht, Elemente über größere Distanzen mit weniger Tauschoperationen einzureihen.

Nächste Seite Aufwärts Vorherige Seite Inhalt

Nächste Seite: Laufzeitkomplexität Aufwärts: Arbeitsweise Vorherige Seite: Abstrakt Inhalt

2002-05-09