Diskussion:Shellsort

verständlicher schreiben

kann nicht mal jemand, der sich damit auskennt einen verständlichen artikle schreiben?

Stimme Dir voll und ganz zu. Ich studiere Informatik und kann nur sagen, dass der Artikel der Shell-Sort nicht gerecht wird. Fehlende Punkte: Vorsortierung, Aufwand, beste Folge an Spalten, etc. --Mike@experimentelles.org 15:34, 3. Jun 2006 (CEST)

Ich hab da mal noch ein wenig was dazugeschrieben, ich hoffe, dass das ein wenig zum Verständnis beiträgt. -- lg 15:02 6. Sept 2006

Im Java-Beispiel: Das Array "spalten" enthält 23 Elemente, die Array-Indizes gehen also von 0 bis 22. Dementsprechend müsste die for-Schleife for (k=0; k<23; k++); anstatt for (k=0; k<24; k++); lauten. Ich hab's im Artikel korrigiert aber nicht getestet, wäre toll wenn jemand die Korrektur überprüfen könnte.

Das Delphi-Beispiel habe ich gerade getestet, es funktioniert nicht. Auch hier ist es ein Index-Fehler. Das erste Element mit dem Index 0 bleibt unsortiert, dafür wird auf das nicht existente Element n zugegriffen. Ich habe den Quelltext nicht korrigiert.

Der Artikel ist gut, nur nicht sehr hilfreich. Ich habe den C-Code geändert, ist allerdings ohne Vorsortierung. Macht doch einen link zu InsertSort, wenns das gibt...

Das C-Beispiel ist fehlerhaft. Compilerfehler.

Ausserdem wird ein aus zwei Elementen bestehendes Feld überhaupt nicht sortiert, der Abbruch aus der Schleife erfolgt zu früh. --80.156.47.202 12:42, 25. Mai 2009 (CEST)

Der Signatur der Methode "sort" fehlt ein Parameter (was das Komma vermuten ließe) oder im Aufruf ist einer zuviel:

sort(int *array,int size, )

Der Aufruf findet dann so statt: sort(x, 0, 29);

Die '29' steht für die länge der Eingabe (auch wenn die Länge der zweite Parameter sein muss, nicht der letzte) aber was soll da die '0'?

Autsch das tut weh!!! Die Funktion "tausche(int *a, int *b)" Im C-Code verwendet einen uralten Trick um 2 REGISTER mit XOR zu tauschen, ohne eine temporäre Variable. Aber bitte doch nicht, wenn beide Werte im Speicher liegen!!! Es sei denn, der Compiler erkennt, dass sich die Zielwerte nicht ändern und lädt sie in Register. Trotztdem ist es schlechter Code, der wahrscheinlich nicht performanter ist und in einem Lexikon nur für Verwirrung sorgt.

Kann es sein, dass im Zahlenbeispiel nicht streng nach einem Algorithmus vorgegangen wird ? Die zweite Matrix, die sich ergibt erscheint mir unlogisch. 2 5 3 4 3 9 3 2 5 4 1 3 ergibt ja als 4er-Matrix 2 5 3 4 | 3 9 3 2 | 5 4 1 3 -> sortiert 2 4 1 2 | 3 5 3 3 | 5 9 3 4 => Folge: 2 4 1 2 3 5 3 3 5 9 3 4 (die nun als 2er-Matrix): 2 4 | 1 2 | 3 5 | 3 3 | 5 9 | 3 4 und somit nicht wie im Beispiel, oder ?

Implementierungen und Komplexität

Die Implementierungen und ihre Komplexität sind sehr missverständlich. Die Implementierungen in C und Python nutzen den originalen Ansatz, bei dem der Teiler bei N/2 startet und jeweils halbiert wird. Damit hat der Algorithmus aber eine Komplexität von O(n²). Leider wird diese als mögliche Laufzeit im entsprechenden Kapitel nie erwähnt. Im englischen Wiki wird darauf sehr deutlich hingewiesen, vielleicht lohnt sich mal eine Übersetzung. --80.156.47.201 10:42, 24. Mär. 2009 (CET)

Startwert für Distanzfolge

Ich hab mir das Sortierverfahren eben zum erstenmal angeguckt und mir fehlte für das Verständnis mit welcher Distanzfolge ich überhaupt beginne. Habe jetzt auf einer anderen Seite gelsesen, dass man immer mit der Größten, welche die Arraylänge nicht überschreitet beginnt. Wäre schön, wenn das auch noch jemand hinzufügen könnte.

Prinzip

Shellsort kann als Erweiterung von Insertionsort betrachtet werden. Dabei versucht es den Nachteil auszugleichen, dass hier Elemente in der Sequenz oft über weite Strecken verschoben werden müssen, was bei langen Strecken hohe Kosten beim Einfügen verursacht. Shellsort verfolgt den Ansatz, die bestehende Sequenz in eine k-spaltige Matrix zu schreiben (Das k ist hier entsprechend hoch zu wählen). (siehe Beispiel, erster Schritt) Nun wird Insertionsort auf die einzelnen Spalten angewendet. Nach der Sortierung jeder Spalte, wird die Anzahl der Spalten um den Faktor 2 verringert bis am Ende nur noch eine Spalte übrig ist.

Dabei gilt folgendes:

• Anzahl der Spalten: 2n, ..., 4, 2, 1
• Verringerung: 2n -> n -> n/2 -> ... -> 4 -> 2 -> 1.

Daraus resultiert eine grobe Sortierung. Dieser Vorgang wird mehrmals wiederholt, wobei jeweils die Breite der Matrix verringert wird, bis die Matrix nur noch aus einer einzigen vollständig sortierten Spalte besteht.

Ein Vorteil dieses Vorgehens liegt darin, dass die Strecke beim Verschieben von Elementen verringert wird und somit Insertionsort nun auch auf langen Listen eingesetzt werden kann.

Shellsort arbeitet in-place, gehört jedoch nicht zu den stabilen Sortieralgorithmen.

a*b sortiert

Sorry, ich habe im März fast unreflektiert die Angabe aus dem ursprünglichen Text "Dabei gilt es bei der Wahl einer Folge zu vermeiden, dass sie gemeinsame Teiler haben, da eine a*b-sortierte Folge auch a-sortiert und b-sortiert ist, sodass es dann zu unnützen Sortierschritt käme." fast unverändert übernommen (abgewandelt auf benachbarte Folgenglieder). Bei genauerer Betrachtung meiner gestrigen Überarbeitung ist mir das sehr sauer aufgestossen und ich habe nun unter Prinzip erklärt, warum das gar nicht sein kann. Die Erklärung würde ich drin lassen, ist für das Verständnis sicher hilfreich. Würde das gelten, könnte man einen extrem performanten Sortieralgorithmus unter Ausnützung der Primzahlfakultät schreiben. (nicht signierter Beitrag von Rechenelf (Diskussion | Beiträge) 12:13, 14. Dez. 2011 (CET))

Zeitkomplexität nach Knuth

Unter Implementierung Java 5 heißt es:

Für die Schrittweiten (1, 3, 7, 15, 31, … ) wurde nachgewiesen (s. Donald E. Knuth: The Art of Computer Programming), dass die Zeitkomplexität des Algorithmus n^1,2 beträgt, was deutlich besser ist,...

Unter Komplexität und Distanzfolgen heißt es:

Mit der Folge 1, 3, 7, 15, 31, 63, ..., 2k - 1 von Hibbard wird eine Komplexität von O(n^1,5) erreicht.

Nur eine der beiden Aussagen kann richtig sein. --Rat (Diskussion) 22:08, 11. Feb. 2014 (CET)

Knuth: The Art of Computer Programming, Volume 3, 2nd Edition, Seite 91 ist die genaue Stelle. O(n^1,5) ist richtig. Die falsche Angabe wurde mit dieser Änderung vor 4 1/2 Jahren eingeführt. --Rat (Diskussion) 22:21, 11. Feb. 2014 (CET)

Woher kommt die Folge im Beispiel?

"Witzig" finde ich, dass im Artikel zahlreiche Spalten-Folgen aufgeführt werden, im Java-Beispiel wird aber eine Folge verwendet, die nirgendwo beschrieben ist: 1, 4, 13, 41, 111, 271, 815, ... Woher kommt diese Folge und welche Komplexität hat sie? 87.140.195.0 14:27, 13. Jun. 2017 (CEST)

Shellsort ist ein Hybrid-Algorithmus

Frage: Müsste man bei Shellsort nicht eigentlich von einem Hybrid-Algorithmus sprechen? Der Code von Herrn Shell ist schließlich kein Sortierverfahren, denn sein Code unterteilt das Array in Streifen, legt diese "gedacht" untereinander und lässt die Spalten dann von Insertionsort sortieren. Wir haben es hier also mit einem Algorithmus zu tun, der sich einen anderen Algorithmus einverleibt hat und diesen dann die eigentlichen Sortierungen durchführen lässt. --77.21.186.2 13:04, 20. Aug. 2021 (CEST)