Talk:Introsort

From Wikipedia, the free encyclopedia

[edit] Implementation

Does anyone have an implementation of this to add to the article? It sounds like a simple cutoff, but I think it would help clarify what InroSort actually does.

What's a "median-of-3" and what's a "killer dataset"? --71.71.238.231 07:06, 15 June 2006 (UTC)

A median-of-3 pivot selection algorithm takes the median of the first, last, and middle element of the list. A median-of-3 killer dataset is one which is designed specifically to cause the median-of-3 pivot selection algorithm to exhibit worst-case behavior. This is all, admittedly, quite impossible to divine - I should expand the article - but you can find some additional information at quicksort. Deco 08:24, 15 June 2006 (UTC)

What is introspective about the introsort? --User:Taejo|대조 11:41, 8 February 2007 (UTC)

[edit] C++ Standard Library

What is the purpose of the last paragraph of this article? It currently reads:

"The C++ STL implementations generally significantly (several times as fast) outperform the C implementation because they are implemented to allow inlining, while the generic C equivalent must use function calls for comparisons. This advantage could be compensated for by using custom versions of the C sort function, at the cost of losing the advantage of a totally generic library function."

This is a total tangent and has absolutely nothing to do with anything. Any objections to simply deleting this part? Promit 23:40, 7 April 2007 (UTC)

On second thought, I'll delete it now, since I'm not sure how many people are active here. If someone has a problem with it, feel free to revert and take it up here. Promit 23:41, 7 April 2007 (UTC)

[edit] Introselect

There ought be a link to Musser's Introselect. Introselect is used to solve finding the kth element out of n elements without having to sort all the n elements. A variation of quicksort called quickselect is used which partitions the elements and zooms in on the partition which has the kth element. The problem is that like quicksort, it has a worse case. Quickselect has average-case of O(n) and worse-case of O(n²). Intraselect has a average and worse-case of O(n) Stephen Howe 21:30, 4 May 2007 (UTC)