Shellsort - Versionsgeschichte

Z thomas: seltsame platzhalterweiterleitung nach wd entfernt

2025-05-26T07:16:32Z

seltsame platzhalterweiterleitung nach wd entfernt

← Nächstältere Version		Version vom 26. Mai 2025, 09:16 Uhr
Zeile 147:		Zeile 147:
	== Variationen ==		== Variationen ==
	[[Combsort]] arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit ''einem'' Durchlauf von [[Bubblesort]] sortiert, bevor die Spaltenanzahl verringert wird.		[[Combsort]] arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit ''einem'' Durchlauf von [[Bubblesort]] sortiert, bevor die Spaltenanzahl verringert wird.

	{{Wikidata-Weiterleitung\|QXXXX}}
	== Literatur ==		== Literatur ==
	* [[Donald L. Shell]]: ''A High-Speed Sorting Procedure.'' In: ''Timon N.'' ''Commun. ACM'', 2(7), 1959, S. 30–32.		* [[Donald L. Shell]]: ''A High-Speed Sorting Procedure.'' In: ''Timon N.'' ''Commun. ACM'', 2(7), 1959, S. 30–32.

Trustable: Kleinigkeiten verbessert

2025-05-14T17:18:17Z

Kleinigkeiten verbessert

← Nächstältere Version		Version vom 14. Mai 2025, 19:18 Uhr
Zeile 8:		Zeile 8:
	Der Algorithmus von Shellsort setzt diese Idee um, indem er die unsortierte Folge in mehrere Teilfolgen aufteilt und danach die Einträge innerhalb jeder Teilfolge sortiert. Beispielsweise führt eine Aufteilung in 4 Teilfolgen zu einer Teilfolge mit den Indizes 0, 4, 8, … einer anderen mit den Indizes 1, 5, 9, … und so weiter. Nach einem solchen Sortierschritt nennt man die Folge 4-sortiert.		Der Algorithmus von Shellsort setzt diese Idee um, indem er die unsortierte Folge in mehrere Teilfolgen aufteilt und danach die Einträge innerhalb jeder Teilfolge sortiert. Beispielsweise führt eine Aufteilung in 4 Teilfolgen zu einer Teilfolge mit den Indizes 0, 4, 8, … einer anderen mit den Indizes 1, 5, 9, … und so weiter. Nach einem solchen Sortierschritt nennt man die Folge 4-sortiert.

	Shellsort wiederholt mehrere Sortierschritte. Der erste Sortierschritt erzeugt die meisten Teilfolgen, also auch den größten Abstand zwischen den Indizes einer Teilfolge. Der Abstand wird mit jedem Schritt kleiner. Wenn z. B. Shellsort mit Abstand 4 anfängt, dann wird die Folge erst 4-sortiert, dann 2-sortiert, und zuletzt mit normalem Insertionsort sozusagen 1-sortiert.		Shellsort wiederholt mehrere Sortierschritte. Der erste Sortierschritt erzeugt die meisten Teilfolgen, also auch den größten Abstand zwischen den Indizes einer Teilfolge. Der Abstand wird mit jedem Schritt kleiner. Wenn z. B. Shellsort mit Abstand 4 anfängt, dann wird die Folge erst 4-sortiert, dann 2-sortiert, und zuletzt mit normalem Insertionsort sozusagen 1-sortiert.

	Anschaulich wäre dies anhand von Hilfsmatrizen darzustellen (siehe Beispiel):		Anschaulich wäre dies anhand von Hilfsmatrizen darzustellen (siehe Beispiel):
Zeile 18:		Zeile 18:
	Eine a*b-sortierte Sequenz ist nicht auch automatisch a-sortiert oder b-sortiert. Zum Beweis betrachten wir eine Sequenz aus den Zahlen 1 bis 12. Diese ist 6-sortiert, wenn wir auf eine beliebige [[Permutation]] der Zahlen 1, 2, 3, 4, 5, 6 eine ebenfalls beliebige Permutation der Zahlen 7, 8, 8, 10, 11, 12 folgen lassen. Die Permutation 6, 5, 4, 3, 2, 1 ist aber keinesfalls 2- oder 3-sortiert. 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12 ist 6-sortiert, aber nicht 2- und auch nicht 3-sortiert.		Eine a*b-sortierte Sequenz ist nicht auch automatisch a-sortiert oder b-sortiert. Zum Beweis betrachten wir eine Sequenz aus den Zahlen 1 bis 12. Diese ist 6-sortiert, wenn wir auf eine beliebige [[Permutation]] der Zahlen 1, 2, 3, 4, 5, 6 eine ebenfalls beliebige Permutation der Zahlen 7, 8, 8, 10, 11, 12 folgen lassen. Die Permutation 6, 5, 4, 3, 2, 1 ist aber keinesfalls 2- oder 3-sortiert. 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12 ist 6-sortiert, aber nicht 2- und auch nicht 3-sortiert.

	Shellsort arbeitet [[In-~~Place~~-Algorithmus\|in-place]], gehört jedoch nicht zu den [[Stabilität (Sortierverfahren)\|stabilen]] [[Sortierverfahren\|Sortieralgorithmen]]. Aufgrund der Sortierung über Distanz verliert die Sortiermethode ihre Eigenschaft „stabil“. Zwei benachbarte und sortierte Elemente landen in verschiedenen Untersequenzen und werden möglicherweise so umsortiert, dass ihre Reihenfolge vertauscht wird.		Shellsort arbeitet [[In-place-Algorithmus\|in-place]], gehört jedoch nicht zu den [[Stabilität (Sortierverfahren)\|stabilen]] [[Sortierverfahren\|Sortieralgorithmen]]. Aufgrund der Sortierung über Distanz verliert die Sortiermethode ihre Eigenschaft „stabil“. Zwei benachbarte und sortierte Elemente landen in verschiedenen Untersequenzen und werden möglicherweise so umsortiert, dass ihre Reihenfolge vertauscht wird.

	== Beispiel ==		== Beispiel ==
Zeile 147:		Zeile 147:
	== Variationen ==		== Variationen ==
	[[Combsort]] arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit ''einem'' Durchlauf von [[Bubblesort]] sortiert, bevor die Spaltenanzahl verringert wird.		[[Combsort]] arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit ''einem'' Durchlauf von [[Bubblesort]] sortiert, bevor die Spaltenanzahl verringert wird.
			{{Wikidata-Weiterleitung\|QXXXX}}
		⚫	== Literatur ==
		⚫	* [[Donald L. Shell]]: ''A High-Speed Sorting Procedure.'' In: ''Timon N.'' ''Commun. ACM'', 2(7), 1959, S. 30–32.
		⚫	* [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]]: ''Algorithms in Java'', Part 1–4. Addison-Wesley, ISBN 0-201-36120-5.

	== Weblinks ==		== Weblinks ==
	{{Wikibooks\|Algorithmen und Datenstrukturen in C/ Shellsort\|Algorithmen und Datenstrukturen in C: Shellsort}}		{{Wikibooks\|Algorithmen und Datenstrukturen in C/ Shellsort\|Algorithmen und Datenstrukturen in C: Shellsort}}
	* [https://hwlang.de/algorithmen/sortieren/shell/shell.htm Shellsort Komplexität]		* [https://hwlang.de/algorithmen/sortieren/shell/shell.htm Shellsort Komplexität]

⚫	== Literatur ==
⚫	* [[Donald L. Shell]]: ''A High-Speed Sorting Procedure.'' In: ''Timon N.'' ''Commun. ACM'', 2(7), 1959, S. 30–32.
⚫	* [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]]: ''Algorithms in Java'', Part 1–4. Addison-Wesley, ISBN 0-201-36120-5.

	== Einzelnachweise ==		== Einzelnachweise ==

Horst Gräbner: Änderungen von 78.46.58.206 (Diskussion) auf die letzte Version von Aka zurückgesetzt

2025-01-09T10:46:32Z

Änderungen von 78.46.58.206 (Diskussion) auf die letzte Version von Aka zurückgesetzt

← Nächstältere Version		Version vom 9. Januar 2025, 12:46 Uhr
Zeile 1:		Zeile 1:
	{{Überarbeiten}}		{{Überarbeiten}}
	[[Datei:Shell sorting algorithm color bars.svg\|mini\|Shell sort, Algorithmus: Farbbalken]]		[[Datei:Shell sorting algorithm color bars.svg\|mini\|Shell sort, Algorithmus: Farbbalken]]
	'''~~=JK;LOShellsort~~''' ist ein von [[Donald L. Shell]] im Jahr 1959 entwickeltes [[Sortierverfahren]], das auf dem Sortierverfahren des direkten Einfügens ([[Insertionsort]])basiert.		'''Shellsort''' ist ein von [[Donald L. Shell]] im Jahr 1959 entwickeltes [[Sortierverfahren]], das auf dem Sortierverfahren des direkten Einfügens ([[Insertionsort]]) basiert.

	== Prinzip ==		== Prinzip ==

78.46.58.206 am 9. Januar 2025 um 10:45 Uhr

2025-01-09T10:45:56Z

← Nächstältere Version		Version vom 9. Januar 2025, 12:45 Uhr
Zeile 1:		Zeile 1:
	{{Überarbeiten}}		{{Überarbeiten}}
	[[Datei:Shell sorting algorithm color bars.svg\|mini\|Shell sort, Algorithmus: Farbbalken]]		[[Datei:Shell sorting algorithm color bars.svg\|mini\|Shell sort, Algorithmus: Farbbalken]]
	'''~~Shellsort~~''' ist ein von [[Donald L. Shell]] im Jahr 1959 entwickeltes [[Sortierverfahren]], das auf dem Sortierverfahren des direkten Einfügens ([[Insertionsort]]) basiert.		'''=JK;LOShellsort''' ist ein von [[Donald L. Shell]] im Jahr 1959 entwickeltes [[Sortierverfahren]], das auf dem Sortierverfahren des direkten Einfügens ([[Insertionsort]])basiert.

	== Prinzip ==		== Prinzip ==

Aka: /* Beispiel */ Leerzeichen vor Zahl eingefügt

2024-12-17T17:36:41Z

Beispiel: Leerzeichen vor Zahl eingefügt

← Nächstältere Version		Version vom 17. Dezember 2024, 19:36 Uhr
Zeile 42:		Zeile 42:
	1 2 2 3 3 4 3 4 3 5 5 9 → 1 2 2 3 3 3 3 4 4 5 5 9		1 2 2 3 3 4 3 4 3 5 5 9 → 1 2 2 3 3 3 3 4 4 5 5 9

	Die hier verwendete Schrittfolge <math>1,2,4,8,16,...,2^n</math> (wie es 1959 original von Shell vorgeschlagen wurde) erweist sich in der Praxis allerdings als nicht zweckmäßig, da nur gerade Stellen sortiert werden und ungerade Stellen der Sequenz nur im letzten Schritt angefasst werden. Als zweckmäßiger hat sich 1,4,13,40 … erwiesen (Wert<sub>n</sub> = 3×Wert<sub>n-1</sub>+1).		Die hier verwendete Schrittfolge <math>1,2,4,8,16,...,2^n</math> (wie es 1959 original von Shell vorgeschlagen wurde) erweist sich in der Praxis allerdings als nicht zweckmäßig, da nur gerade Stellen sortiert werden und ungerade Stellen der Sequenz nur im letzten Schritt angefasst werden. Als zweckmäßiger hat sich 1, 4, 13, 40 … erwiesen (Wert<sub>n</sub> = 3×Wert<sub>n-1</sub>+1).

	== Implementierung ==		== Implementierung ==

Skranon am 7. Dezember 2024 um 23:31 Uhr

2024-12-07T23:31:19Z

← Nächstältere Version		Version vom 8. Dezember 2024, 01:31 Uhr
Zeile 18:		Zeile 18:
	Eine a*b-sortierte Sequenz ist nicht auch automatisch a-sortiert oder b-sortiert. Zum Beweis betrachten wir eine Sequenz aus den Zahlen 1 bis 12. Diese ist 6-sortiert, wenn wir auf eine beliebige [[Permutation]] der Zahlen 1, 2, 3, 4, 5, 6 eine ebenfalls beliebige Permutation der Zahlen 7, 8, 8, 10, 11, 12 folgen lassen. Die Permutation 6, 5, 4, 3, 2, 1 ist aber keinesfalls 2- oder 3-sortiert. 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12 ist 6-sortiert, aber nicht 2- und auch nicht 3-sortiert.		Eine a*b-sortierte Sequenz ist nicht auch automatisch a-sortiert oder b-sortiert. Zum Beweis betrachten wir eine Sequenz aus den Zahlen 1 bis 12. Diese ist 6-sortiert, wenn wir auf eine beliebige [[Permutation]] der Zahlen 1, 2, 3, 4, 5, 6 eine ebenfalls beliebige Permutation der Zahlen 7, 8, 8, 10, 11, 12 folgen lassen. Die Permutation 6, 5, 4, 3, 2, 1 ist aber keinesfalls 2- oder 3-sortiert. 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12 ist 6-sortiert, aber nicht 2- und auch nicht 3-sortiert.

	Shellsort arbeitet [[in-place]], gehört jedoch nicht zu den [[Stabilität (Sortierverfahren)\|stabilen]] [[~~Sortieralgorithmus~~\|Sortieralgorithmen]]. Aufgrund der Sortierung über Distanz verliert die Sortiermethode ihre Eigenschaft „stabil“. Zwei benachbarte und sortierte Elemente landen in verschiedenen Untersequenzen und werden möglicherweise so umsortiert, dass ihre Reihenfolge vertauscht wird.		Shellsort arbeitet [[In-Place-Algorithmus\|in-place]], gehört jedoch nicht zu den [[Stabilität (Sortierverfahren)\|stabilen]] [[Sortierverfahren\|Sortieralgorithmen]]. Aufgrund der Sortierung über Distanz verliert die Sortiermethode ihre Eigenschaft „stabil“. Zwei benachbarte und sortierte Elemente landen in verschiedenen Untersequenzen und werden möglicherweise so umsortiert, dass ihre Reihenfolge vertauscht wird.

	== Beispiel ==		== Beispiel ==

	Zu sortieren sind die Zahlen 2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3 mittels der Folge <math>2^n,...,4,2,1</math>		Zu sortieren sind die Zahlen 2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3 mittels der Folge <math>2^n,...,4,2,1</math>

Zeile 47:		Zeile 46:
	== Implementierung ==		== Implementierung ==
	=== Java 5 ===		=== Java 5 ===

	Shellsort ist eine Verbesserung des Algorithmus straight insertion. Dort wandern nämlich die Elemente in Einzelschritten auf ihren Platz: Nach dem Finden des kleinsten Elements werden die dazwischenliegenden einzeln hochgeschoben und nur das kleinste „springt“. Die meisten (d. h. n) Elemente werden von ihrem ursprünglichen Platz in durchschnittlich n/3 Schritten zu ihrem endgültigen Platz geschoben.		Shellsort ist eine Verbesserung des Algorithmus straight insertion. Dort wandern nämlich die Elemente in Einzelschritten auf ihren Platz: Nach dem Finden des kleinsten Elements werden die dazwischenliegenden einzeln hochgeschoben und nur das kleinste „springt“. Die meisten (d. h. n) Elemente werden von ihrem ursprünglichen Platz in durchschnittlich n/3 Schritten zu ihrem endgültigen Platz geschoben.

Zeile 111:		Zeile 109:
	Ursprünglich schlug Donald Shell die Folge 1, 2, 4, 8, 16, 32 …, 2<sup>k</sup> vor. Die Performance ist allerdings sehr schlecht, weil erst im allerletzten Schritt die Elemente auf ungeraden Positionen sortiert werden. Die Komplexität ist mit <math> \Theta(n^{2}) </math> sehr hoch.		Ursprünglich schlug Donald Shell die Folge 1, 2, 4, 8, 16, 32 …, 2<sup>k</sup> vor. Die Performance ist allerdings sehr schlecht, weil erst im allerletzten Schritt die Elemente auf ungeraden Positionen sortiert werden. Die Komplexität ist mit <math> \Theta(n^{2}) </math> sehr hoch.

	Mit der Folge 1, 3, 7, 15, 31, 63 …, 2<sup>k</sup> - 1 von Hibbard wird eine Komplexität von		Mit der Folge 1, 3, 7, 15, 31, 63 …, 2<sup>k</sup> - 1 von Hibbard wird eine Komplexität von <math> \mathcal{O}(n^{1,5}) </math> erreicht.
	<math> \mathcal{O}(n^{1,5}) </math> erreicht.

	Mit der Folge 1, 2, 3, 4, 6, 8, 9, 12, 16 …, 2<sup>p</sup>3<sup>q</sup> von Pratt beträgt die Komplexität <math> \mathcal{O}(n \cdot \log (n)^2) </math>.		Mit der Folge 1, 2, 3, 4, 6, 8, 9, 12, 16 …, 2<sup>p</sup>3<sup>q</sup> von Pratt beträgt die Komplexität <math> \mathcal{O}(n \cdot \log (n)^2) </math>.
Zeile 119:		Zeile 116:

	Einige gute Folgen stammen von [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]].		Einige gute Folgen stammen von [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]].

	Die Folge 1, 8, 23, 77, 281, 1073, 4193, 16577 …, 4<sup>k+1</sup> + 3*2<sup>k</sup> + 1 hat Komplexität von <math> \mathcal{O}(n^{4/3}) </math> erreicht.		Die Folge 1, 8, 23, 77, 281, 1073, 4193, 16577 …, 4<sup>k+1</sup> + 3*2<sup>k</sup> + 1 hat Komplexität von <math> \mathcal{O}(n^{4/3}) </math> erreicht.
	Eine wesentlich bessere Folge ist folgende: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001 …, 92<sup>k</sup> - 92<sup>k/2</sup> + 1 (k gerade) bzw. 82<sup>k</sup> - 62<sup>(k+1)/2</sup> + 1 (k ungerade).		Eine wesentlich bessere Folge ist folgende: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001 …, 92<sup>k</sup> - 92<sup>k/2</sup> + 1 (k gerade) bzw. 82<sup>k</sup> - 62<sup>(k+1)/2</sup> + 1 (k ungerade).

	Betrachtet man rein geometrische Folgen, so liegt ein Minimum in der größeren Umgebung von Faktor 2,3, d. h. die Folgeglieder haben das Verhältnis von ungefähr 2,3. Eine der theoretisch besten Folgen (d. h. Zahl der Vergleiche), die experimentell ermittelt wurde von Marcin Ciura, ist 1, 4, 10, 23, 57, 132, 301, 701, 1750 und basiert auf diesem Faktor. Basierend auf dem Faktor 1750/701, wird die Reihe wie folgt fortgesetzt: Sei g das letzte Glied, dann ist das nächste durch 1+floor(2,5*g) gegeben, also 701, 1753, 4383, 10958, 27396, 68491, 171228 …		Betrachtet man rein geometrische Folgen, so liegt ein Minimum in der größeren Umgebung von Faktor 2,3, d. h. die Folgeglieder haben das Verhältnis von ungefähr 2,3. Eine der theoretisch besten Folgen (d. h. Zahl der Vergleiche), die experimentell ermittelt wurde von Marcin Ciura, ist 1, 4, 10, 23, 57, 132, 301, 701, 1750 und basiert auf diesem Faktor. Basierend auf dem Faktor 1750/701, wird die Reihe wie folgt fortgesetzt: Sei g das letzte Glied, dann ist das nächste durch 1+floor(2,5*g) gegeben, also 701, 1753, 4383, 10958, 27396, 68491, 171228 …

	Eine Folge von Gonnet und Baeza-Yates basiert auf dem Faktor 2,2, die sehr gute Ergebnisse liefert.		Eine Folge von Gonnet und Baeza-Yates basiert auf dem Faktor 2,2, die sehr gute Ergebnisse liefert.

	Erstaunlicherweise sind in der Praxis bessere Folgen als die von Marcin Ciura bekannt, die sich rekursiv berechnen. Die Laufzeit des Shellsort ist kürzer, obwohl die Zahl der Vergleiche höher ist (zu sortierende Elemente sind Ganzzahlen in Registerbreite). Rekursive Folgen berechnen sich aus Ganzzahlen, und das Verhältnis der Folgeglieder konvergiert gegen einen bestimmten Wert, bei den Fibonaccizahlen ist es der [[Goldener Schnitt\|Goldene Schnitt]].		Erstaunlicherweise sind in der Praxis bessere Folgen als die von Marcin Ciura bekannt, die sich rekursiv berechnen. Die Laufzeit des Shellsort ist kürzer, obwohl die Zahl der Vergleiche höher ist (zu sortierende Elemente sind Ganzzahlen in Registerbreite). Rekursive Folgen berechnen sich aus Ganzzahlen, und das Verhältnis der Folgeglieder konvergiert gegen einen bestimmten Wert, bei den Fibonaccizahlen ist es der [[Goldener Schnitt\|Goldene Schnitt]].

	Eine solche Folge basiert auf den [[Fibonaccizahlen]]. Eine der beiden 1er am Anfang wird weggelassen und jede Zahl der Folge mit dem Doppelten des [[Goldener Schnitt\|Goldenen Schnitts]] (ca. 3,236) potenziert, was dann zu dieser Distanzfolge führt: 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035 …		Eine solche Folge basiert auf den [[Fibonacci-Folge\|Fibonaccizahlen]]. Eine der beiden 1er am Anfang wird weggelassen und jede Zahl der Folge mit dem Doppelten des [[Goldener Schnitt\|Goldenen Schnitts]] (ca. 3,236) potenziert, was dann zu dieser Distanzfolge führt: 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035 …

	Eine andere rekursive Folge wurde von Matthias Fuchs gefunden. Die Folge 1, 4, 13, 40, 124, 385, 1195, 3709, 11512, 35731 … hat als Konvergenzwert ungefähr 3.103803402. Die Berechnungsvorschrift ist f<sub>k+1</sub> = 3*f<sub>k</sub> + f<sub>k-2</sub>, wobei die Folge initial mit 1, 1, 1 startet und für den Shellsort die ersten beiden 1er weggelassen werden.		Eine andere rekursive Folge wurde von Matthias Fuchs gefunden. Die Folge 1, 4, 13, 40, 124, 385, 1195, 3709, 11512, 35731 … hat als Konvergenzwert ungefähr 3.103803402. Die Berechnungsvorschrift ist f<sub>k+1</sub> = 3*f<sub>k</sub> + f<sub>k-2</sub>, wobei die Folge initial mit 1, 1, 1 startet und für den Shellsort die ersten beiden 1er weggelassen werden.
Zeile 149:		Zeile 148:
	[[Combsort]] arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit ''einem'' Durchlauf von [[Bubblesort]] sortiert, bevor die Spaltenanzahl verringert wird.		[[Combsort]] arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit ''einem'' Durchlauf von [[Bubblesort]] sortiert, bevor die Spaltenanzahl verringert wird.

	== ~~Einzelnachweise~~ ==		== Weblinks ==
		⚫	{{Wikibooks\|Algorithmen und Datenstrukturen in C/ Shellsort\|Algorithmen und Datenstrukturen in C: Shellsort}}
⚫	<references />
		⚫	* [https://hwlang.de/algorithmen/sortieren/shell/shell.htm Shellsort Komplexität]

	== Literatur ==		== Literatur ==
Zeile 156:		Zeile 156:
	* [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]]: ''Algorithms in Java'', Part 1–4. Addison-Wesley, ISBN 0-201-36120-5.		* [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]]: ''Algorithms in Java'', Part 1–4. Addison-Wesley, ISBN 0-201-36120-5.

	== ~~Weblinks~~ ==		== Einzelnachweise ==
		⚫	<references />
⚫	{{Wikibooks\|Algorithmen und Datenstrukturen in C/ Shellsort\|Algorithmen und Datenstrukturen in C: Shellsort}}
⚫	* [https://hwlang.de/algorithmen/sortieren/shell/shell.htm Shellsort Komplexität]

	[[Kategorie:Sortieralgorithmus]]		[[Kategorie:Sortieralgorithmus]]

Invisigoth67: typo

2024-11-05T13:54:40Z

typo

← Nächstältere Version		Version vom 5. November 2024, 15:54 Uhr
Zeile 120:		Zeile 120:
	Einige gute Folgen stammen von [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]].		Einige gute Folgen stammen von [[Robert Sedgewick (Informatiker)\|Robert Sedgewick]].
	Die Folge 1, 8, 23, 77, 281, 1073, 4193, 16577 …, 4<sup>k+1</sup> + 3*2<sup>k</sup> + 1 hat Komplexität von <math> \mathcal{O}(n^{4/3}) </math> erreicht.		Die Folge 1, 8, 23, 77, 281, 1073, 4193, 16577 …, 4<sup>k+1</sup> + 3*2<sup>k</sup> + 1 hat Komplexität von <math> \mathcal{O}(n^{4/3}) </math> erreicht.
	Eine wesentlich bessere Folge ist folgende: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001 …, 92<sup>k</sup> - 92<sup>k/2</sup> + 1 (k gerade) bzw. 82<sup>k</sup> - 62<sup>(k+1)/2</sup> + 1 (k ungerade)		Eine wesentlich bessere Folge ist folgende: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001 …, 92<sup>k</sup> - 92<sup>k/2</sup> + 1 (k gerade) bzw. 82<sup>k</sup> - 62<sup>(k+1)/2</sup> + 1 (k ungerade).

	Betrachtet man rein geometrische Folgen, so liegt ein Minimum in der größeren Umgebung von Faktor 2,3, d. h. die Folgeglieder haben das Verhältnis von ungefähr 2,3. Eine der theoretisch besten Folgen (d. h. Zahl der Vergleiche), die experimentell ermittelt wurde von Marcin Ciura, ist 1, 4, 10, 23, 57, 132, 301, 701, 1750 und basiert auf diesem Faktor. Basierend auf dem Faktor 1750/701, wird die Reihe wie folgt fortgesetzt: Sei g das letzte Glied, dann ist das nächste durch 1+floor(2,5*g) gegeben, also 701, 1753, 4383, 10958, 27396, 68491, 171228 …		Betrachtet man rein geometrische Folgen, so liegt ein Minimum in der größeren Umgebung von Faktor 2,3, d. h. die Folgeglieder haben das Verhältnis von ungefähr 2,3. Eine der theoretisch besten Folgen (d. h. Zahl der Vergleiche), die experimentell ermittelt wurde von Marcin Ciura, ist 1, 4, 10, 23, 57, 132, 301, 701, 1750 und basiert auf diesem Faktor. Basierend auf dem Faktor 1750/701, wird die Reihe wie folgt fortgesetzt: Sei g das letzte Glied, dann ist das nächste durch 1+floor(2,5*g) gegeben, also 701, 1753, 4383, 10958, 27396, 68491, 171228 …

Siegbert v2: Änderung 248686639 von Gerolsteiner flasche rückgängig gemacht; absolute Verschlechterung des Artikels. Sämtliche Grundprinzipien zur Artikelgestaltung werden über den Haufen geworfen (Gliederung, ref-Tags, Formatierung, geschützte LZ wurden entfernt, zerstörte mathematische Ausdrücke etc. pp.) => Bitte nicht so weitermachen, sondern erst das Mentorenprogramm durchlaufen und/oder die Hilfe lesen, so ist das eine Katastrophe

2024-10-04T06:01:01Z

Änderung 248686639 von Gerolsteiner flasche rückgängig gemacht; absolute Verschlechterung des Artikels. Sämtliche Grundprinzipien zur Artikelgestaltung werden über den Haufen geworfen (Gliederung, ref-Tags, Formatierung, geschützte LZ wurden entfernt, zerstörte mathematische Ausdrücke etc. pp.) => Bitte nicht so weitermachen, sondern erst das Mentorenprogramm durchlaufen und/oder die Hilfe lesen, so ist das eine Katastrophe

Änderungen zeigen

Gerolsteiner flasche am 17. September 2024 um 19:29 Uhr

2024-09-17T19:29:10Z

Änderungen zeigen

Aka: /* Weblinks */ https | viele Tippfehler in anderen Artikeln – Helfer gesucht

2023-12-05T19:58:44Z

Weblinks: https | viele Tippfehler in anderen Artikeln – Helfer gesucht

← Nächstältere Version		Version vom 5. Dezember 2023, 21:58 Uhr
Zeile 158:		Zeile 158:
	== Weblinks ==		== Weblinks ==
	{{Wikibooks\|Algorithmen und Datenstrukturen in C/ Shellsort\|Algorithmen und Datenstrukturen in C: Shellsort}}		{{Wikibooks\|Algorithmen und Datenstrukturen in C/ Shellsort\|Algorithmen und Datenstrukturen in C: Shellsort}}
	* [~~http~~://hwlang.de/algorithmen/sortieren/shell/shell.htm Shellsort Komplexität]		* [https://hwlang.de/algorithmen/sortieren/shell/shell.htm Shellsort Komplexität]

	[[Kategorie:Sortieralgorithmus]]		[[Kategorie:Sortieralgorithmus]]