Lektion 52:shell sortWie wir gesehen haben, haben bubble sort und insertion sort Probleme, die Werte über größere Entfernungen zu transportieren. Für kleinere Arrays sind diese Verfahren sehr gut, aber sobald die Arrays größer werden, werden sie sehr langsam. Um das zu vermeiden, müßte man vor dem eigentlichen Sortieren eine Vorsortierung machen, die schon mal ungefähr dafür sorgt, daß die großen Werte nach hinten kommen und die kleinen nach vorne. Das würde dann das weitere Sortieren erheblich beschleunigen. Weil straight insertion sort recht gut mit vorsortierten Arrays zurechtkommt, wird dieses Verfahren gewählt, um die eigentliche Arbeit zu machen. Mit einem kleinen Trick, kann dasselbe Verfahren auch für die Vorsortierung verwendet werden. Eine sehr elegante Möglichkeit, das zu bewerkstelligen ist, sich nur jedes 10. Element zu betrachten. Angenommen, wir hätten ein Array mit 100 Elementen. Davon würden wir nur die Elemente 0, 10, 20, ... ,100 betrachten. Die zu sortieren geht noch recht schnell mit straight insertion sort. Danach werden die Elemente 1, 11, 21, ... ,91 sortiert. Dann die Elemente 2, 12, 22, ... und zuletzt die Elemente 9, 19, ... ,99. Das ergibt eine recht nette Vorsortierung, und es ist zu erwarten, daß jetzt straight insertion sort auf das ganze Array angewendet noch recht schnell bleibt. Die Funktion
wird so abgewandelt, daß die Nachbarelemente nicht mehr um eine Position links oder rechts stehen, sondern gleich step (z.B. 10) weit weg sind. Außerdem wird des Beginn des Arrays von 0 nach start (zwischen 0 und 9) verschoben.
Da start von 0 bis step laufen soll, ergibt sich
Dieser Code müßte dann einmal mit step==10 durchlaufen werden für die Vorsortierung und dann noch einmal mit step==1 für die endgültige Sortierung. Noch bessere Ergebnisse bekommt man, wenn in mehreren Stufen von 100 bis 1 sortiert wird. Zum Beispiel könnten wir mit step=50 anfangen, und dann step so lange halbieren, bis step==1.
Übung:Die Sortierung wird noch schneller, wenn Sie folgende Sequenz für die step-Werte verwenden: ... 1093, 364, 121, 40, 13, 4, 1. Dabei ist jeder vorhergehende Wert das Dreifache plus 1 des folgenden Wertes. Setzen Sie vor die do-Schleife eine Schleife, die den kleinsten Wert in dieser Sequenz findet, der größer als size ist. Statt durch 2 zu teilen wird dann noch durch 3 geteilt, und fertig ist ein recht schnelles Sortierverfahren. Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern. [aktuelle Version] [inhalt] [index] [Fehlerkorrektur, Verbesserungsvorschlag] © Volkard Henkel <volkard@normannia.de>, last update: 08/25/00 |