Shellsort - Revision history

Aphitor: Reverted: Ciura gaps 156, 409, 995 are only optimal for N = 1000. Ciura conjectured that 132, 301, 701 will turn up optimal for larger N.

2025-05-15T21:57:29Z

Reverted: Ciura gaps 156, 409, 995 are only optimal for N = 1000. Ciura conjectured that 132, 301, 701 will turn up optimal for larger N.

← Previous revision		Revision as of 21:57, 15 May 2025
Line 112:		Line 112:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	# Sort an array a[0...n-1].		# Sort an array a[0...n-1].
	gaps = [~~995~~, ~~409~~, ~~156~~, 57, 23, 10, 4, 1] # Ciura gap sequence		gaps = [701, 301, 132, 57, 23, 10, 4, 1] # Ciura gap sequence

	# Start with the largest gap and work down to a gap of 1		# Start with the largest gap and work down to a gap of 1
Line 324:		Line 324:
	\| {{OEIS link\|A102549}}		\| {{OEIS link\|A102549}}
	\| Unknown (experimentally derived)		\| Unknown (experimentally derived)
	\| <math>1, 4, 10, 23, 57, ~~156~~, ~~409~~, ~~995~~</math>		\| <math>1, 4, 10, 23, 57, 132, 301, 701</math><!--Please don't add 1750. It doesn't belong here.-->
	\| {{unk}}		\| {{unk}}
	\| Ciura, 2001<ref name=":0">{{Cite book		\| Ciura, 2001<ref name=":0">{{Cite book

GCRhoads2: Replaced >= with greater than or equal sign.

2025-05-14T04:48:44Z

Replaced >= with greater than or equal sign.

← Previous revision		Revision as of 04:48, 14 May 2025
Line 373:		Line 373:
	\|-		\|-
	\|		\|
	\|Start at 1. Successive increments are smallest prime <math> >= 3 ~~\cdot~~ </math> previous		\|Start at 1. Successive increments are smallest prime <math> \geq 3 </math> times previous
	\|<math>1, 3, 11, 37, 113, 347, 1049, \ldots</math>		\|<math>1, 3, 11, 37, 113, 347, 1049, \ldots</math>
	\|{{unk}}		\|{{unk}}

GCRhoads2: Added my increment sequence to the table. Does better than every other sequence listed except the Ciura sequence when sorting 1000 elements

2025-05-14T04:36:19Z

Added my increment sequence to the table. Does better than every other sequence listed except the Ciura sequence when sorting 1000 elements

← Previous revision		Revision as of 04:36, 14 May 2025
Line 371:		Line 371:
	\| date = 1 Jan 2023		\| date = 1 Jan 2023
	}}</ref>		}}</ref>
			\|-
			\|
			\|Start at 1. Successive increments are smallest prime <math> >= 3 \cdot </math> previous
			\|<math>1, 3, 11, 37, 113, 347, 1049, \ldots</math>
			\|{{unk}}
			\|Glenn C. Rhoads<ref>{{Cite web \|last=Rhoads \|first=Glenn \|date=March 1, 2010 \|title=Shellsort Increment Sequences \|url=https://gcrhoads.byethost4.com/shellSort.html \|url-status=live \|access-date=May 13, 2025 \|website=The Glenn}}</ref>
	\|}		\|}
	When the binary representation of ''N'' contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(''N''<sup>2</sup>) comparisons in the worst case. For instance, this case occurs for ''N'' equal to a power of two when elements greater and smaller than the median occupy odd and even positions respectively, since they are compared only in the last pass.		When the binary representation of ''N'' contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(''N''<sup>2</sup>) comparisons in the worst case. For instance, this case occurs for ''N'' equal to a power of two when elements greater and smaller than the median occupy odd and even positions respectively, since they are compared only in the last pass.

GCRhoads2: Changed the gaps in the pseudocode to Ciura's corrected sequence

2025-05-14T04:18:37Z

Changed the gaps in the pseudocode to Ciura's corrected sequence

← Previous revision		Revision as of 04:18, 14 May 2025
Line 112:		Line 112:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	# Sort an array a[0...n-1].		# Sort an array a[0...n-1].
	gaps = [~~701~~, ~~301~~, ~~132~~, 57, 23, 10, 4, 1] # Ciura gap sequence		gaps = [995, 409, 156, 57, 23, 10, 4, 1] # Ciura gap sequence

	# Start with the largest gap and work down to a gap of 1		# Start with the largest gap and work down to a gap of 1
Line 324:		Line 324:
	\| {{OEIS link\|A102549}}		\| {{OEIS link\|A102549}}
	\| Unknown (experimentally derived)		\| Unknown (experimentally derived)
	\| <math>1, 4, 10, 23, 57, 156, 409, 995</math~~><!--Please don't add 1750. It doesn't belong here.--~~>		\| <math>1, 4, 10, 23, 57, 156, 409, 995</math>
	\| {{unk}}		\| {{unk}}
	\| Ciura, 2001<ref name=":0">{{Cite book		\| Ciura, 2001<ref name=":0">{{Cite book

GCRhoads2: Changed the Ciura sequence listed in the table to the one he actually claims has the smallest average number of comparisons among all known sequences when sorting 1000 elements. I have verified this claim for both 1000 and 5000 elements in an empirical test whose results are located at https://gcrhoads.byethost4.com/shellSort.html. Ciura conjectured that the optimal sequence for sorting large ( > 8000 elements) arrays, would start with the gaps listed in the removed sequence.

2025-05-14T03:54:05Z

Changed the Ciura sequence listed in the table to the one he actually claims has the smallest average number of comparisons among all known sequences when sorting 1000 elements. I have verified this claim for both 1000 and 5000 elements in an empirical test whose results are located at https://gcrhoads.byethost4.com/shellSort.html. Ciura *conjectured* that the optimal sequence for sorting large ( > 8000 elements) arrays, would *start* with the gaps listed in the removed sequence.

← Previous revision		Revision as of 03:54, 14 May 2025
Line 41:		Line 41:
	\|archive-url=https://web.archive.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf		\|archive-url=https://web.archive.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
	\|url-status=dead		\|url-status=dead
	}}</ref><ref>Some older textbooks and references call this the "Shell–Metzner" sort after [[Marlene Metzner Norton]], but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See {{Cite web		}}</ref><ref>Some older textbooks and references call this the "Shell–Metzner" sort after [[Marlene Metzner Norton]], but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See {{Cite web \|title=Shell sort \|url=https://xlinux.nist.gov/dads/HTML/shellsort.html \|access-date=2007-07-17 \|publisher=National Institute of Standards and Technology}}</ref>
	\|title=Shell sort
	\|publisher=National Institute of Standards and Technology
	\|url=https://xlinux.nist.gov/dads/HTML/shellsort.html
	\|access-date=2007-07-17 }}</ref>

	== Description ==		== Description ==
Line 328:		Line 324:
	\| {{OEIS link\|A102549}}		\| {{OEIS link\|A102549}}
	\| Unknown (experimentally derived)		\| Unknown (experimentally derived)
	\| <math>1, 4, 10, 23, 57, ~~132~~, ~~301~~, ~~701~~</math><!--Please don't add 1750. It doesn't belong here.-->		\| <math>1, 4, 10, 23, 57, 156, 409, 995</math><!--Please don't add 1750. It doesn't belong here.-->
	\| {{unk}}		\| {{unk}}
	\| Ciura, 2001<ref name=":0">{{Cite book		\| Ciura, 2001<ref name=":0">{{Cite book

EEng: /* top */ ce

2025-04-09T15:24:12Z

top: ce

← Previous revision		Revision as of 15:24, 9 April 2025
Line 22:		Line 22:
	}}		}}
	[[File:Shell sorting algorithm color bars.svg\|thumb\|alt=The steps of Shellsort.\|Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1]]		[[File:Shell sorting algorithm color bars.svg\|thumb\|alt=The steps of Shellsort.\|Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1]]
	'''Shellsort''', also known as '''Shell sort''' or '''Shell's method''', is an [[in-place algorithm\|in-place]] [[comparison sort]]. It can be understood as either a generalization of sorting by exchange ([[bubble sort]]) or sorting by insertion ([[insertion sort]]).<ref name="Knuth" /> The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. ~~[[Donald Shell]] published the first version of this sort in 1959.<ref name="Shell">{{Cite journal~~		'''Shellsort''', also known as '''Shell sort''' or '''Shell's method''', is an [[in-place algorithm\|in-place]] [[comparison sort]]. It can be understood as either a generalization of sorting by exchange ([[bubble sort]]) or sorting by insertion ([[insertion sort]]).<ref name="Knuth" /> The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange.
		⚫	The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their [[time complexity]] remains an [[open problem]].

			The algorithm was first published by [[Donald Shell]] in 1959, and has nothing to do with shells.<ref name="Shell">{{Cite journal
	\|url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf		\|url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
	\|last=Shell		\|last=Shell
Line 42:		Line 45:
	\|publisher=National Institute of Standards and Technology		\|publisher=National Institute of Standards and Technology
	\|url=https://xlinux.nist.gov/dads/HTML/shellsort.html		\|url=https://xlinux.nist.gov/dads/HTML/shellsort.html
			\|access-date=2007-07-17 }}</ref>
⚫	~~\|access-date=2007-07-17 }}</ref>~~ The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their [[time complexity]] remains an [[open problem]].

	== Description ==		== Description ==

Tubend at 17:14, 19 January 2025

2025-01-19T17:14:28Z

← Previous revision		Revision as of 17:14, 19 January 2025
Line 22:		Line 22:
	}}		}}
	[[File:Shell sorting algorithm color bars.svg\|thumb\|alt=The steps of Shellsort.\|Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1]]		[[File:Shell sorting algorithm color bars.svg\|thumb\|alt=The steps of Shellsort.\|Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1]]
	'''Shellsort''', also known as '''Shell sort''' or '''Shell's method''', is an [[in-place algorithm\|in-place]] [[comparison sort]]. It can be ~~seen~~ as either a generalization of sorting by exchange ([[bubble sort]]) or sorting by insertion ([[insertion sort]]).<ref name="Knuth" /> The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. [[Donald Shell]] published the first version of this sort in 1959.<ref name="Shell">{{Cite journal		'''Shellsort''', also known as '''Shell sort''' or '''Shell's method''', is an [[in-place algorithm\|in-place]] [[comparison sort]]. It can be understood as either a generalization of sorting by exchange ([[bubble sort]]) or sorting by insertion ([[insertion sort]]).<ref name="Knuth" /> The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. [[Donald Shell]] published the first version of this sort in 1959.<ref name="Shell">{{Cite journal
	\|url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf		\|url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
	\|last=Shell		\|last=Shell

Nthep: Copyvio revdel completed (RR)

2025-01-17T13:01:30Z

Copyvio revdel completed (RR)

← Previous revision		Revision as of 13:01, 17 January 2025
Line 1:		Line 1:
	{{copyvio-revdel\|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm\|start1=880469\|end1=31493178}}
	{{Short description\|Sorting algorithm which uses multiple comparison intervals}}		{{Short description\|Sorting algorithm which uses multiple comparison intervals}}
	{{Infobox Algorithm		{{Infobox Algorithm

JJPMaster: Requesting copyvio revdel (cv-revdel)

2025-01-17T04:05:38Z

Requesting copyvio revdel (cv-revdel)

← Previous revision		Revision as of 04:05, 17 January 2025
Line 1:		Line 1:
			{{copyvio-revdel\|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm\|start1=880469\|end1=31493178}}
	{{Short description\|Sorting algorithm which uses multiple comparison intervals}}		{{Short description\|Sorting algorithm which uses multiple comparison intervals}}
	{{Infobox Algorithm		{{Infobox Algorithm

JJPMaster: Reverted edit by JJPMaster (talk) to last version by Weedwhacker128

2025-01-17T04:04:40Z

Reverted edit by JJPMaster (talk) to last version by Weedwhacker128

← Previous revision		Revision as of 04:04, 17 January 2025
Line 1:		Line 1:
	{{copyvio-revdel\|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm}}
	{{Short description\|Sorting algorithm which uses multiple comparison intervals}}		{{Short description\|Sorting algorithm which uses multiple comparison intervals}}
	{{Infobox Algorithm		{{Infobox Algorithm