Block swap algorithms - Revision history

Nyq: lc common nouns, wikiformatting

2024-10-31T17:41:26Z

lc common nouns, wikiformatting

← Previous revision		Revision as of 17:41, 31 October 2024
Line 1:		Line 1:
	{{Context\|date=July 2019}}		{{Context\|date=July 2019}}

	In computer [[algorithm]]s, '''~~Block~~ swap algorithms''' swap two regions of elements of an [[Array data structure\|array]]. It is simple to swap two non-overlapping regions of an [[array data structure\|array]] of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes (such swapping is equivalent to '''~~Array~~ ~~Rotation~~'''). Three algorithms are known to accomplish this: Bentley's ~~Juggling~~ (also known as ''~~Dolphin~~ ~~Algorithm~~'' <ref>D. Gries, H. Mills (1981), [https://hdl.handle.net/1813/6292 Swapping Sections]</ref>), Gries-Mills, and ~~Reversal~~.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|		In computer [[algorithm]]s, '''block swap algorithms''' swap two regions of elements of an [[Array data structure\|array]]. It is simple to swap two non-overlapping regions of an [[array data structure\|array]] of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes (such swapping is equivalent to '''array rotation'''). Three algorithms are known to accomplish this: ''Bentley's juggling'' (also known as ''dolphin algorithm'' <ref>D. Gries, H. Mills (1981), [https://hdl.handle.net/1813/6292 Swapping Sections]</ref>), ''Gries-Mills'', and ''reversal algorithm''.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|
	O(n)]], (see [[Time complexity]]).		O(n)]], (see [[Time complexity]]).

Line 10:		Line 10:
	* Rotate region AB		* Rotate region AB

	Gries-Mills and ~~Reversal~~ algorithms perform better than Bentley's ~~Juggling~~, because of their [[Cache (computing)\|cache]]-friendly [[memory access pattern]] behavior.		Gries-Mills and reversal algorithms perform better than Bentley's juggling, because of their [[Cache (computing)\|cache]]-friendly [[memory access pattern]] behavior.

	The ~~Reversal~~ algorithm [[Parallel computing\|parallelizes]] well, because rotations can be split into sub-regions, which can be rotated independently of others.		The reversal algorithm [[Parallel computing\|parallelizes]] well, because rotations can be split into sub-regions, which can be rotated independently of others.

	==References==		==References==

Tagishsimon: rm cat improve

2022-07-19T01:55:57Z

rm cat improve

← Previous revision		Revision as of 01:55, 19 July 2022
Line 16:		Line 16:
	==References==		==References==
	{{reflist}}		{{reflist}}

	{{Improve categories\|date=July 2019}}

	[[Category:Algorithms]]		[[Category:Algorithms]]

SamanthaNguyen: /* Reversal algorithm */ improve phrasing

2022-06-10T21:41:03Z

Reversal algorithm: improve phrasing

← Previous revision		Revision as of 21:41, 10 June 2022
Line 5:		Line 5:

	==Reversal algorithm==		==Reversal algorithm==
	The reversal algorithm is the simplest to explain, using rotations. A rotation is an in-place reversal of array elements. This method swaps two elements of an array from outside in within a range. The rotation works for an even ~~number of elements~~ or an odd number of array elements. The reversal algorithm uses three in-place rotations to accomplish an in-place block swap:		The reversal algorithm is the simplest to explain, using rotations. A rotation is an in-place reversal of array elements. This method swaps two elements of an array from outside in within a range. The rotation works for an even or odd number of array elements. The reversal algorithm uses three in-place rotations to accomplish an in-place block swap:
	* Rotate region A		* Rotate region A
	* Rotate region B		* Rotate region B

117.205.26.6 at 13:37, 5 November 2021

2021-11-05T13:37:34Z

← Previous revision		Revision as of 13:37, 5 November 2021
Line 1:		Line 1:
	{{Context\|date=July 2019}}		{{Context\|date=July 2019}}

	In computer [[algorithm]]s, '''Block swap algorithms''' swap two regions of elements of an [[Array data structure\|array]]. It is simple to swap two non-overlapping regions of an [[array data structure\|array]] of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling (also known as ''Dolphin Algorithm'' <ref>D. Gries, H. Mills (1981), [https://hdl.handle.net/1813/6292 Swapping Sections]</ref>), Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|		In computer [[algorithm]]s, '''Block swap algorithms''' swap two regions of elements of an [[Array data structure\|array]]. It is simple to swap two non-overlapping regions of an [[array data structure\|array]] of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes (such swapping is equivalent to '''Array Rotation'''). Three algorithms are known to accomplish this: Bentley's Juggling (also known as ''Dolphin Algorithm'' <ref>D. Gries, H. Mills (1981), [https://hdl.handle.net/1813/6292 Swapping Sections]</ref>), Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|
	O(n)]], (see [[Time complexity]]).		O(n)]], (see [[Time complexity]]).

117.205.26.6 at 13:31, 5 November 2021

2021-11-05T13:31:13Z

← Previous revision		Revision as of 13:31, 5 November 2021
Line 1:		Line 1:
	{{Context\|date=July 2019}}		{{Context\|date=July 2019}}

	'''Block swap algorithms''' swap two elements of an [[Array data structure\|array]] ~~in computer [[algorithm]]s~~. It is simple to swap two non-overlapping regions of an [[array data structure\|array]] of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling, Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|		In computer [[algorithm]]s, '''Block swap algorithms''' swap two regions of elements of an [[Array data structure\|array]]. It is simple to swap two non-overlapping regions of an [[array data structure\|array]] of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling (also known as ''Dolphin Algorithm'' <ref>D. Gries, H. Mills (1981), [https://hdl.handle.net/1813/6292 Swapping Sections]</ref>), Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|
	O(n)]], (see [[Time complexity]]).		O(n)]], (see [[Time complexity]]).

Elinruby: Wl

2020-08-23T22:40:16Z

← Previous revision		Revision as of 22:40, 23 August 2020
Line 1:		Line 1:
	{{Context\|date=July 2019}}		{{Context\|date=July 2019}}

	'''Block swap algorithms''' swap two elements of an [[Array data structure\|array]] in computer [[algorithm]]s. It is simple to swap two non-overlapping regions of an array of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling, Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|		'''Block swap algorithms''' swap two elements of an [[Array data structure\|array]] in computer [[algorithm]]s. It is simple to swap two non-overlapping regions of an [[array data structure\|array]] of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling, Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|
	O(n)]], (see [[Time complexity]]).		O(n)]], (see [[Time complexity]]).

Elinruby: added Category:Sorting algorithms using HotCat

2020-08-05T11:37:20Z

added Category:Sorting algorithms using HotCat

← Previous revision		Revision as of 11:37, 5 August 2020
Line 21:		Line 21:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	[[Category:Arrays]]		[[Category:Arrays]]
			[[Category:Sorting algorithms]]

Elinruby: added Category:Arrays using HotCat

2020-08-05T11:36:59Z

added Category:Arrays using HotCat

← Previous revision		Revision as of 11:36, 5 August 2020
Line 20:		Line 20:

	[[Category:Algorithms]]		[[Category:Algorithms]]
			[[Category:Arrays]]

Elinruby: Wl

2020-08-05T11:34:02Z

← Previous revision		Revision as of 11:34, 5 August 2020
Line 1:		Line 1:
	{{Context\|date=July 2019}}		{{Context\|date=July 2019}}

	'''Block swap algorithms''' ~~is the simple art of~~ ~~swapping~~ two elements of an [[Array data structure\|array]] in computer [[algorithm]]s. It is ~~also~~ simple to swap two non-overlapping regions of an array of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling, Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|		'''Block swap algorithms''' swap two elements of an [[Array data structure\|array]] in computer [[algorithm]]s. It is simple to swap two non-overlapping regions of an array of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes. Three algorithms are known to accomplish this: Bentley's Juggling, Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation\|
	O(n)]], (see [[Time complexity]]).		O(n)]], (see [[Time complexity]]).

Elinruby: /* Reversal algorithm */ wl

2020-08-05T11:32:36Z

Reversal algorithm: wl

← Previous revision		Revision as of 11:32, 5 August 2020
Line 10:		Line 10:
	* Rotate region AB		* Rotate region AB

	Gries-Mills and Reversal algorithms perform better than Bentley's Juggling, because of their [[Cache (computing)\|cache]]-friendly memory access pattern behavior.		Gries-Mills and Reversal algorithms perform better than Bentley's Juggling, because of their [[Cache (computing)\|cache]]-friendly [[memory access pattern]] behavior.

	The Reversal algorithm [[Parallel computing\|parallelizes]] well, because rotations can be split into sub-regions, which can be rotated independently of others.		The Reversal algorithm [[Parallel computing\|parallelizes]] well, because rotations can be split into sub-regions, which can be rotated independently of others.