Talk:Selection algorithm
From Wikipedia, the free encyclopedia
"By using non-strict comparisons (<= and >=) instead, we would find the minimum element with maximum index; this approach also has some small performance benefits." What performance benefits, exactly?
- On some machines it can cause less branch instructions, and so generate less icache flushes. The loop also has to have been unrolled or have other unconditional instructions in it. This effect is so small and machine-dependent however that I'll go ahead and remove this claim. Deco 02:08, 24 November 2005 (UTC)
Contents |
[edit] quicksortOnlyFirstK not recursive?
Shouldn't the quicksortOnlyFirstK pseudocall call itsself instead of quicksort, or am I missing something obvious.--ISee 07:22, 26 April 2006 (UTC)
- Fixed that after verifying that part of the algorithm--ISee 11:10, 26 April 2006 (UTC)
[edit] Minimum or maximum
Is it necessary to say "minimum or maximum" everywhere? It adds unnecessary wordiness, and it makes the times when it's not used that much more confusing. Here's an example:
Note that there may be multiple minimum or maximum elements. Because the comparisons above are strict, these algorithms finds the minimum element with minimum index. By using non-strict comparisons (≤ and ≥) instead, we would find the minimum element with maximum index.
Two of those minimums should be changed to minimum or maximum.
What would be even better, though, would be to just generalize the whole article to be "finding the maximum" and give a note that everything can be flipped for the reverse case. --71.71.238.231 08:07, 15 June 2006 (UTC)
- I'm not sure what you're arguing. It already says "minimum or maximum" in only one place. The others are referring to something more subtle than that - the case where there are equal elements and we have to select which one is chosen. Deco 08:21, 15 June 2006 (UTC)
-
- It already says "minimum or maximum" in only one place. Search again. That exact text appears four times. Which says nothing about forms like "minimum/maximum." --71.71.238.231 02:53, 17 June 2006 (UTC)
-
-
- Oh, I was just referring to the portion you quoted above. You're right, it's a good idea to avoid the verbosity and just mention it once at the beginning. Deco 04:28, 17 June 2006 (UTC)
-
Why dont u simply sort the given list L and return the k-th element in L? -- Orz 04:25, 29 August 2006 (UTC)
- Because that takes O(n log n) time, which is dramatically slower for large n. The article discusses this. Deco 05:37, 29 August 2006 (UTC)
- It does indeed. Thanks for clearing that out, Decon
[edit] swap in partition function
is there an error in one line from the partition function? in particular, shouldn't the line:
swap a[pivotIndex] and a[right]
be replaced with the line:
swap a[pivotIndex] and a[left]
mwb
[edit] correction
or perhaps the swap line was correct, but a the end of partition you need to swap a[right] back to a position between the two subsegments...
mwb
- Yes... that line was there. Someone just removed it and introduced several other errors. I've reverted them. Deco 23:21, 11 October 2006 (UTC)
[edit] Linear minimum/maximum algorithms
I don't understand why the index of the minimum/maximum element seen so far is stored in the described algorithm. In the example pseudocode, it is not used for anything. Ahy1 12:05, 29 December 2006 (UTC)
- It's part of the result. Often you want not only the minimum/maximum value, but the index at which it occurred, for later processing. Deco 14:50, 29 December 2006 (UTC)
[edit] Remarks
A selection algorithm is not only for finding the kth smallest (or kth largest) number in a list. In Genetic algorithms they use other shemes for selection than the smallest value for example. Or in real-time/embedded systems there exists selection algorithms, that just take a msg and take an action according to the type of message. So it isn't all about finding the smallest values...
- These are just different things with the same name. I'll clarify that the term use here is specialized. Dcoetzee 00:08, 5 May 2007 (UTC)
[edit] Introselect
There is a variation of selection that David Musser refers to. Introselect has an analogous relationship to quickselect that Intrasort has to quicksort - all designed to ensure both average and worse-case performance of O(n). But Musser in his paper does not say what algorithm would be swopped to if quickselect goes bad. I think this page should to refer to Introselect.
There is also another variation of finding the kth of n elements - where the elements remain undisturbed. Naturally the overhead is considerably higher and I dont know what the average big-O performance is like. [User:Stephen Howe|Stephen Howe] 21:50, 4 May 2007 (UTC)
- Good idea, introselect ought to be mentioned. Dcoetzee 00:08, 5 May 2007 (UTC)
[edit] Error?
In the selection function, shouldn't we compare pivotNewIndex - left + 1 with k, which means selection of kth smallest number in list(left:right).
[edit] primitive algorithm to select k elements - O(n) not O(kn)
Section : Repeated application of simple selection algorithms
O(n) to select k-th element. O(n) to compare all elements to it. —Preceding unsigned comment added by 132.72.98.166 (talk) 13:03, 12 November 2007 (UTC)
- No, it's O(kn), because it can't just magically pick out the kth smallest element on the first try - it has to first identify each smaller element. Dcoetzee 13:26, 12 November 2007 (UTC)
A C# implementation of the primative Algo shows an error. Would any compSci care to comment?
public double BasicSelection(List<double> myList, int k)
{
for (int i = 0; i < k; i++)
{
int minIndex = i;
double minValue = myList[i];
for (int j = i+1; j < myList.Count; j++)
{
if (myList[j] < minValue)
{
minIndex = j;
minValue = myList[j];
}
//now swap them around
double temp1 = myList[i];
double temp2 = myList[minIndex];
myList[i] = temp2;
myList[minIndex] = temp1;
}
}
return myList[k];
}
