240:. Introsort starts with quicksort, so it achieves performance similar to quicksort if quicksort works, and falls back to heapsort (which has optimal worst-case performance) if quicksort does not progress quickly enough. Similarly, introselect combines quickselect with median of medians to achieve worst-case linear selection with performance similar to quickselect.
247:
algorithm) if it recurses too many times without making sufficient progress. The switching strategy is the main technical content of the algorithm. Simply limiting the recursion to constant depth is not good enough, since this would make the algorithm switch on all sufficiently large lists. Musser
180:
algorithms, in that they both start with the quick algorithm, which has good average performance and low overhead, but fall back to an optimal worst-case algorithm (with higher overhead) if the quick algorithm does not progress rapidly enough. Both algorithms were introduced by
243:
Introselect works by optimistically starting out with quickselect and only switching to a worst-case linear-time selection algorithm (the Blum-Floyd-Pratt-Rivest-Tarjan
298:
The paper suggested that more research on introselect was forthcoming, but the author retired in 2007 without having published any such further research.
395:
197:
that have both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.
200:
However, in most C++ Standard
Library implementations, a different "introselect" algorithm is used, which combines quickselect and
216:). The C++ draft standard, as of 2022, does not have requirements on the worst-case performance, therefore allowing such choice.
413:
127:
106:
62:
45:
307:
263:
Sum the size of all partitions generated so far. If this exceeds the list size times some small positive constant
194:
169:
which has fast average performance and optimal worst-case performance. Introselect is related to the
99:
38:
267:, switch to the worst-case linear algorithm. This sum is easy to track in a single scalar variable.
154:
244:
190:
173:
166:
391:
158:
146:
130:
109:
65:
48:
252:
Keep track of the list of sizes of the subpartitions processed so far. If at any point
256:
recursive calls have been made without halving the list size, for some small positive
407:
343:
375:
331:
327:
182:
224:
Introsort achieves practical performance comparable to quicksort while preserving
379:
162:
201:
177:
170:
396:
10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#
357:
237:
344:"35968 – nth_element fails to meet its complexity requirements"
176:: these are analogous refinements of the basic quickselect and
362:
Working Draft, Standard for
Programming Language C++, eel.is
236:) worst-case behavior by creating a hybrid of quicksort and
126:
105:
95:
85:
61:
44:
34:
24:
380:"Introspective Sorting and Selection Algorithms"
358:"27.8.3 Nth element [alg.nth.element]"
271:Both approaches limit the recursion depth to
8:
260:, switch to the worst-case linear algorithm.
80:
19:
153:(short for "introspective selection") is a
81:Introselect (Quickselect–Heapselect)
248:discusses a couple of simple approaches:
319:
204:, and has a worst-case running time of
186:
79:
18:
7:
14:
384:Software: Practice and Experience
189:), with the purpose of providing
287:) and the total running time to
1:
430:
308:Floyd–Rivest algorithm
414:Selection algorithms
195:C++ Standard Library
20:Introselect (Musser)
155:selection algorithm
90:Selection algorithm
82:
29:Selection algorithm
21:
16:Selection algorithm
328:Generic Algorithms
191:generic algorithms
245:median of medians
174:sorting algorithm
167:median of medians
143:
142:
78:
77:
421:
399:
376:Musser, David R.
366:
365:
354:
348:
347:
340:
334:
324:
147:computer science
83:
22:
429:
428:
424:
423:
422:
420:
419:
418:
404:
403:
402:
374:
370:
369:
356:
355:
351:
342:
341:
337:
325:
321:
316:
304:
222:
17:
12:
11:
5:
427:
425:
417:
416:
406:
405:
401:
400:
390:(8): 983–993.
371:
368:
367:
349:
335:
318:
317:
315:
312:
311:
310:
303:
300:
269:
268:
261:
221:
218:
141:
140:
133:
124:
123:
112:
103:
102:
97:
96:Data structure
93:
92:
87:
76:
75:
68:
59:
58:
51:
42:
41:
36:
35:Data structure
32:
31:
26:
15:
13:
10:
9:
6:
4:
3:
2:
426:
415:
412:
411:
409:
397:
393:
389:
385:
381:
377:
373:
372:
363:
359:
353:
350:
345:
339:
336:
333:
329:
323:
320:
313:
309:
306:
305:
301:
299:
296:
294:
290:
286:
282:
278:
274:
266:
262:
259:
255:
251:
250:
249:
246:
241:
239:
235:
231:
227:
219:
217:
215:
211:
207:
203:
198:
196:
192:
188:
184:
179:
175:
172:
168:
164:
160:
156:
152:
148:
138:
134:
132:
129:
125:
121:
117:
113:
111:
108:
104:
101:
98:
94:
91:
88:
84:
73:
69:
67:
64:
60:
56:
52:
50:
47:
43:
40:
37:
33:
30:
27:
23:
387:
383:
361:
352:
338:
332:David Musser
322:
297:
292:
288:
284:
280:
276:
272:
270:
264:
257:
253:
242:
233:
229:
225:
223:
213:
209:
205:
199:
183:David Musser
150:
144:
136:
119:
115:
89:
71:
54:
28:
187:Musser 1997
163:quickselect
151:introselect
131:performance
110:performance
66:performance
49:performance
314:References
220:Algorithms
202:heapselect
157:that is a
107:Worst-case
46:Worst-case
178:quicksort
171:introsort
128:Best-case
63:Best-case
408:Category
378:(1997).
302:See also
238:heapsort
193:for the
159:hybrid
283:(log
275:⌈log
100:Array
86:Class
39:Array
25:Class
279:⌉ =
232:log
212:log
185:in (
165:and
118:log
392:doi
330:",
161:of
145:In
410::
388:27
386:.
382:.
360:.
295:.
293:n)
149:,
135:O(
114:O(
70:O(
53:O(
398:.
394::
364:.
346:.
326:"
291:(
289:O
285:n
281:O
277:n
273:k
265:k
258:k
254:k
234:n
230:n
228:(
226:O
214:n
210:n
208:(
206:O
139:)
137:n
122:)
120:n
116:n
74:)
72:n
57:)
55:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.