22:
201:
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
236:
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
134:
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
138:"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.
166:
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
179:. 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
256:
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
171:, 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
280:
202:
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.
213:, which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a
270:
245:, which divide the data into separate subsets, sort the subsets, and then combine the subsets into totally sorted data; examples include
113:
43:
237:
the distributor, combining trivial results (a one-element data set from each processor). A basic example of these algorithms are
94:
66:
47:
159:
155:
73:
80:
196:
275:
32:
62:
51:
36:
261:, the Map and Reduce step solve different problems, and are combined to solve a different, third problem.
233:
163:
295:
151:
238:
226:
168:
87:
242:
147:
183:, which combines merge sort, insertion sort, together with additional logic (including
289:
184:
246:
222:
210:
21:
150:, hybrid algorithms are very common in optimized real-world implementations of
172:
258:
250:
218:
214:
206:
176:
131:
221:
if quicksort is not progressing well; analogously introselect begins with
180:
205:
Another example of hybrid algorithms for performance reasons are
190:
A general procedure for a simple hybrid recursive algorithm is
15:
281:
Hybrid input output (HIO) algorithm for phase retrieval
8:
50:. Unsourced material may be challenged and
271:Hybrid algorithm (constraint satisfaction)
114:Learn how and when to remove this message
229:if quickselect is not progressing well.
7:
48:adding citations to reliable sources
14:
20:
192:short-circuiting the base case,
1:
135:the individual components.
312:
276:Hybrid genetic algorithm
241:, particularly used for
187:) in the merging logic.
234:distributed algorithms
197:arm's-length recursion
217:, but switches to a
164:decrease-and-conquer
152:recursive algorithms
44:improve this article
239:distribution sorts
225:, but switches to
169:sorting algorithms
160:divide-and-conquer
63:"Hybrid algorithm"
227:median of medians
124:
123:
116:
98:
303:
243:external sorting
148:computer science
128:hybrid algorithm
119:
112:
108:
105:
99:
97:
56:
24:
16:
311:
310:
306:
305:
304:
302:
301:
300:
286:
285:
267:
156:implementations
154:, particularly
144:
120:
109:
103:
100:
57:
55:
41:
25:
12:
11:
5:
309:
307:
299:
298:
288:
287:
284:
283:
278:
273:
266:
263:
194:also known as
143:
140:
122:
121:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
308:
297:
294:
293:
291:
282:
279:
277:
274:
272:
269:
268:
264:
262:
260:
254:
252:
248:
244:
240:
235:
230:
228:
224:
220:
216:
212:
208:
203:
200:
198:
193:
188:
186:
185:binary search
182:
178:
174:
170:
165:
161:
157:
153:
149:
141:
139:
136:
133:
129:
118:
115:
107:
96:
93:
89:
86:
82:
79:
75:
72:
68:
65: –
64:
60:
59:Find sources:
53:
49:
45:
39:
38:
34:
29:This article
27:
23:
18:
17:
255:
232:Centralized
231:
204:
195:
191:
189:
145:
137:
127:
125:
110:
101:
91:
84:
77:
70:
58:
42:Please help
30:
247:bucket sort
223:quickselect
211:introselect
296:Algorithms
173:merge sort
74:newspapers
259:MapReduce
251:flashsort
219:heap sort
215:quicksort
207:introsort
177:quicksort
132:algorithm
31:does not
290:Category
265:See also
142:Examples
104:May 2014
181:Timsort
88:scholar
52:removed
37:sources
130:is an
90:
83:
76:
69:
61:
95:JSTOR
81:books
249:and
209:and
158:of
67:news
35:any
33:cite
175:or
162:or
146:In
46:by
292::
253:.
126:A
199:.
117:)
111:(
106:)
102:(
92:·
85:·
78:·
71:·
54:.
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
