Hybrid algorithm - Revision history

CoolTomato33: Improved leading sentence and irrelevant statement about C++

2023-02-03T22:03:10Z

Improved leading sentence and irrelevant statement about C++

← Previous revision		Revision as of 22:03, 3 February 2023
Line 1:		Line 1:
	{{Unreferenced\|date=May 2014}}		{{Unreferenced\|date=May 2014}}
	A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem~~, and is mostly used in programming languages like [[C++]]~~, either choosing one ~~(depending~~ on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.		A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, either choosing one based on some characteristic of the data, or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.

	"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.		"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.

Comp.arch at 15:04, 21 May 2022

2022-05-21T15:04:17Z

← Previous revision		Revision as of 15:04, 21 May 2022
Line 5:		Line 5:

	==Examples==		==Examples==
	In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide and conquer algorithm#Implementation issues\|implementations]] of		In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide-and-conquer algorithm#Implementation issues\|implementations]] of
	[[divide and conquer algorithm\|divide and conquer]] or [[decrease and conquer]] algorithms, where the size of the data decreases as one moves deeper in the recursion. In this case, one algorithm is used for the overall approach (on large data), but deep in the recursion, it switches to a different algorithm, which is more efficient on small data. A common example is in [[sorting algorithm]]s, where the insertion sort, which is inefficient on large data, but very efficient on small data (say, five to ten elements), is used as the final step, after primarily applying another algorithm, such as [[merge sort]] or [[quicksort]]. Merge sort and quicksort are asymptotically optimal on large data, but the overhead becomes significant if applying them to small data, hence the use of a different algorithm at the end of the recursion. A highly optimized hybrid sorting algorithm is [[Timsort]], which combines merge sort, insertion sort, together with additional logic (including [[binary search]]) in the merging logic.		[[divide-and-conquer algorithm\|divide-and-conquer]] or [[decrease-and-conquer]] algorithms, where the size of the data decreases as one moves deeper in the recursion. In this case, one algorithm is used for the overall approach (on large data), but deep in the recursion, it switches to a different algorithm, which is more efficient on small data. A common example is in [[sorting algorithm]]s, where the insertion sort, which is inefficient on large data, but very efficient on small data (say, five to ten elements), is used as the final step, after primarily applying another algorithm, such as [[merge sort]] or [[quicksort]]. Merge sort and quicksort are asymptotically optimal on large data, but the overhead becomes significant if applying them to small data, hence the use of a different algorithm at the end of the recursion. A highly optimized hybrid sorting algorithm is [[Timsort]], which combines merge sort, insertion sort, together with additional logic (including [[binary search]]) in the merging logic.

	A general procedure for a simple hybrid recursive algorithm is ''short-circuiting the base case,'' also known as ''[[arm's-length recursion]].'' In this case whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking if it is null, checking null before recursing. This is useful for efficiency when the algorithm usually encounters the base case many times, as in many tree algorithms, but is otherwise considered poor style, particularly in academia, due to the added complexity.		A general procedure for a simple hybrid recursive algorithm is ''short-circuiting the base case,'' also known as ''[[arm's-length recursion]].'' In this case whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking if it is null, checking null before recursing. This is useful for efficiency when the algorithm usually encounters the base case many times, as in many tree algorithms, but is otherwise considered poor style, particularly in academia, due to the added complexity.

77.50.40.182: whitespace

2021-12-06T00:20:23Z

whitespace

← Previous revision		Revision as of 00:20, 6 December 2021
Line 1:		Line 1:
	{{Unreferenced\|date=May 2014}}		{{Unreferenced\|date=May 2014}}
	A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, and is mostly used in programming languages like [[C++]] ,either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.		A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, and is mostly used in programming languages like [[C++]], either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.

	"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.		"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.

לוכסן: capitalization

2021-09-22T03:50:07Z

capitalization

← Previous revision		Revision as of 03:50, 22 September 2021
Line 1:		Line 1:
	{{Unreferenced\|date=May 2014}}		{{Unreferenced\|date=May 2014}}
	A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, and is mostly used in programming languages like [[C~~++\|c~~++]] ,either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.		A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, and is mostly used in programming languages like [[C++]] ,either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.

	"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.		"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.

Katie writes stuff at 02:49, 25 July 2021

2021-07-25T02:49:49Z

← Previous revision		Revision as of 02:49, 25 July 2021
Line 1:		Line 1:
	{{Unreferenced\|date=May 2014}}		{{Unreferenced\|date=May 2014}}
	A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.		A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, and is mostly used in programming languages like [[C++\|c++]] ,either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.

	"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.		"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.

Serols: Reverted edits by 2001:4455:10A:3500:50D2:C392:CA50:A7F7 (talk) to last version by ClueBot NG

2020-10-19T11:45:26Z

Reverted edits by 2001:4455:10A:3500:50D2:C392:CA50:A7F7 (talk) to last version by ClueBot NG

← Previous revision		Revision as of 11:45, 19 October 2020
Line 5:		Line 5:

	==Examples==		==Examples==
			In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide and conquer algorithm#Implementation issues\|implementations]] of
			[[divide and conquer algorithm\|divide and conquer]] or [[decrease and conquer]] algorithms, where the size of the data decreases as one moves deeper in the recursion. In this case, one algorithm is used for the overall approach (on large data), but deep in the recursion, it switches to a different algorithm, which is more efficient on small data. A common example is in [[sorting algorithm]]s, where the insertion sort, which is inefficient on large data, but very efficient on small data (say, five to ten elements), is used as the final step, after primarily applying another algorithm, such as [[merge sort]] or [[quicksort]]. Merge sort and quicksort are asymptotically optimal on large data, but the overhead becomes significant if applying them to small data, hence the use of a different algorithm at the end of the recursion. A highly optimized hybrid sorting algorithm is [[Timsort]], which combines merge sort, insertion sort, together with additional logic (including [[binary search]]) in the merging logic.

			A general procedure for a simple hybrid recursive algorithm is ''short-circuiting the base case,'' also known as ''[[arm's-length recursion]].'' In this case whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking if it is null, checking null before recursing. This is useful for efficiency when the algorithm usually encounters the base case many times, as in many tree algorithms, but is otherwise considered poor style, particularly in academia, due to the added complexity.

			Another example of hybrid algorithms for performance reasons are [[introsort]] and [[introselect]], which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a [[quicksort]], but switches to a [[heap sort]] if quicksort is not progressing well; analogously introselect begins with [[quickselect]], but switches to [[median of medians]] if quickselect is not progressing well.

			Centralized [[distributed algorithm]]s can often be considered as hybrid algorithms, consisting of an individual algorithm (run on each distributed processor), and a combining algorithm (run on a centralized distributor) – these correspond respectively to running the entire algorithm on one processor, or running the entire computation on the distributor, combining trivial results (a one-element data set from each processor). A basic example of these algorithms are [[distribution sort]]s, particularly used for [[external sorting]], which divide the data into separate subsets, sort the subsets, and then combine the subsets into totally sorted data; examples include [[bucket sort]] and [[flashsort]].

			However, in general distributed algorithms need not be hybrid algorithms, as individual algorithms or combining or communication algorithms may be solving different problems. For example, in models such as [[MapReduce]], the Map and Reduce step solve different problems, and are combined to solve a different, third problem.

	== See also ==		== See also ==

2001:4455:10A:3500:50D2:C392:CA50:A7F7: /* Examples */

2020-10-19T11:45:11Z

Examples

← Previous revision		Revision as of 11:45, 19 October 2020
Line 5:		Line 5:

	==Examples==		==Examples==
	In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide and conquer algorithm#Implementation issues\|implementations]] of
	[[divide and conquer algorithm\|divide and conquer]] or [[decrease and conquer]] algorithms, where the size of the data decreases as one moves deeper in the recursion. In this case, one algorithm is used for the overall approach (on large data), but deep in the recursion, it switches to a different algorithm, which is more efficient on small data. A common example is in [[sorting algorithm]]s, where the insertion sort, which is inefficient on large data, but very efficient on small data (say, five to ten elements), is used as the final step, after primarily applying another algorithm, such as [[merge sort]] or [[quicksort]]. Merge sort and quicksort are asymptotically optimal on large data, but the overhead becomes significant if applying them to small data, hence the use of a different algorithm at the end of the recursion. A highly optimized hybrid sorting algorithm is [[Timsort]], which combines merge sort, insertion sort, together with additional logic (including [[binary search]]) in the merging logic.

	A general procedure for a simple hybrid recursive algorithm is ''short-circuiting the base case,'' also known as ''[[arm's-length recursion]].'' In this case whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking if it is null, checking null before recursing. This is useful for efficiency when the algorithm usually encounters the base case many times, as in many tree algorithms, but is otherwise considered poor style, particularly in academia, due to the added complexity.

	Another example of hybrid algorithms for performance reasons are [[introsort]] and [[introselect]], which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a [[quicksort]], but switches to a [[heap sort]] if quicksort is not progressing well; analogously introselect begins with [[quickselect]], but switches to [[median of medians]] if quickselect is not progressing well.

	Centralized [[distributed algorithm]]s can often be considered as hybrid algorithms, consisting of an individual algorithm (run on each distributed processor), and a combining algorithm (run on a centralized distributor) – these correspond respectively to running the entire algorithm on one processor, or running the entire computation on the distributor, combining trivial results (a one-element data set from each processor). A basic example of these algorithms are [[distribution sort]]s, particularly used for [[external sorting]], which divide the data into separate subsets, sort the subsets, and then combine the subsets into totally sorted data; examples include [[bucket sort]] and [[flashsort]].

	However, in general distributed algorithms need not be hybrid algorithms, as individual algorithms or combining or communication algorithms may be solving different problems. For example, in models such as [[MapReduce]], the Map and Reduce step solve different problems, and are combined to solve a different, third problem.

	== See also ==		== See also ==

ClueBot NG: Reverting possible vandalism by 2001:4455:10A:3500:50D2:C392:CA50:A7F7 to version by Abequinn14. Report False Positive? Thanks, ClueBot NG. (3801405) (Bot)

2020-10-19T11:44:28Z

Reverting possible vandalism by 2001:4455:10A:3500:50D2:C392:CA50:A7F7 to version by Abequinn14. Report False Positive? Thanks, ClueBot NG. (3801405) (Bot)

← Previous revision		Revision as of 11:44, 19 October 2020
Line 6:		Line 6:
	==Examples==		==Examples==
	In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide and conquer algorithm#Implementation issues\|implementations]] of		In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide and conquer algorithm#Implementation issues\|implementations]] of
			[[divide and conquer algorithm\|divide and conquer]] or [[decrease and conquer]] algorithms, where the size of the data decreases as one moves deeper in the recursion. In this case, one algorithm is used for the overall approach (on large data), but deep in the recursion, it switches to a different algorithm, which is more efficient on small data. A common example is in [[sorting algorithm]]s, where the insertion sort, which is inefficient on large data, but very efficient on small data (say, five to ten elements), is used as the final step, after primarily applying another algorithm, such as [[merge sort]] or [[quicksort]]. Merge sort and quicksort are asymptotically optimal on large data, but the overhead becomes significant if applying them to small data, hence the use of a different algorithm at the end of the recursion. A highly optimized hybrid sorting algorithm is [[Timsort]], which combines merge sort, insertion sort, together with additional logic (including [[binary search]]) in the merging logic.
	[[divide and conquer algorithm\|divide and conquer]] or [[decrease and conquer]] algorith

			A general procedure for a simple hybrid recursive algorithm is ''short-circuiting the base case,'' also known as ''[[arm's-length recursion]].'' In this case whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking if it is null, checking null before recursing. This is useful for efficiency when the algorithm usually encounters the base case many times, as in many tree algorithms, but is otherwise considered poor style, particularly in academia, due to the added complexity.

	Another example of hybrid algorithms for performance reasons are [[introsort]] and [[introselect]], which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a [[quicksort]], but switches to a [[heap sort]] if quicksort is not progressing well; analogously introselect begins with [[quickselect]], but switches to [[median of medians]] if quickselect is not progressing well.		Another example of hybrid algorithms for performance reasons are [[introsort]] and [[introselect]], which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a [[quicksort]], but switches to a [[heap sort]] if quicksort is not progressing well; analogously introselect begins with [[quickselect]], but switches to [[median of medians]] if quickselect is not progressing well.

2001:4455:10A:3500:50D2:C392:CA50:A7F7: /* Examples */

2020-10-19T11:44:23Z

Examples

← Previous revision		Revision as of 11:44, 19 October 2020
Line 6:		Line 6:
	==Examples==		==Examples==
	In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide and conquer algorithm#Implementation issues\|implementations]] of		In [[computer science]], hybrid algorithms are very common in optimized real-world implementations of [[recursive algorithm]]s, particularly [[Divide and conquer algorithm#Implementation issues\|implementations]] of
			[[divide and conquer algorithm\|divide and conquer]] or [[decrease and conquer]] algorith
	[[divide and conquer algorithm\|divide and conquer]] or [[decrease and conquer]] algorithms, where the size of the data decreases as one moves deeper in the recursion. In this case, one algorithm is used for the overall approach (on large data), but deep in the recursion, it switches to a different algorithm, which is more efficient on small data. A common example is in [[sorting algorithm]]s, where the insertion sort, which is inefficient on large data, but very efficient on small data (say, five to ten elements), is used as the final step, after primarily applying another algorithm, such as [[merge sort]] or [[quicksort]]. Merge sort and quicksort are asymptotically optimal on large data, but the overhead becomes significant if applying them to small data, hence the use of a different algorithm at the end of the recursion. A highly optimized hybrid sorting algorithm is [[Timsort]], which combines merge sort, insertion sort, together with additional logic (including [[binary search]]) in the merging logic.

	A general procedure for a simple hybrid recursive algorithm is ''short-circuiting the base case,'' also known as ''[[arm's-length recursion]].'' In this case whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking if it is null, checking null before recursing. This is useful for efficiency when the algorithm usually encounters the base case many times, as in many tree algorithms, but is otherwise considered poor style, particularly in academia, due to the added complexity.

	Another example of hybrid algorithms for performance reasons are [[introsort]] and [[introselect]], which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a [[quicksort]], but switches to a [[heap sort]] if quicksort is not progressing well; analogously introselect begins with [[quickselect]], but switches to [[median of medians]] if quickselect is not progressing well.		Another example of hybrid algorithms for performance reasons are [[introsort]] and [[introselect]], which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a [[quicksort]], but switches to a [[heap sort]] if quicksort is not progressing well; analogously introselect begins with [[quickselect]], but switches to [[median of medians]] if quickselect is not progressing well.

Renamed user 39825094askdfja: Reverted 1 good faith edit by 2405:204:66A7:D11B:653E:6011:52DF:BFE using STiki

2018-08-03T23:01:54Z

Reverted 1 good faith edit by 2405:204:66A7:D11B:653E:6011:52DF:BFE using STiki

← Previous revision		Revision as of 23:01, 3 August 2018
Line 2:		Line 2:
	A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.		A '''hybrid algorithm''' is an [[algorithm]] that combines two or more other algorithms that solve the same problem, either choosing one (depending on the data), or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.

	"Hybrid algorithm" ~~is also known as high definition~~ does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.		"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.

	==Examples==		==Examples==