Re: A question: Is 200,000 element array worth sorting and search?

CBFalconer <cbfalconer@[EMAIL PROTECTED]
> writes:
> Richard Heathfield wrote:
>> CBFalconer said:
>> 
>> <snip>
>> 
>>> It's a poor question.  Quicksort is O(nLOGn), Linear search is
>>> O(n), and bubble sort is O(n*n), where n is the size of the array,
>>> here 200000.  However linear searching doesn't require sorting, it
>>> only requires examining each member of the original array for
>>> equality.  Since you get the linear answer quickest, and don't need
>>> the array sorted, that is the optimum answer.  The code is also the
>>> simplest:
>>>
>>>    for (i = 0; i <= 200000; i++) {
>> 
>> Rookie error...
>> 
>>>       if (a[i] == item) break;
>>>    }
>>>    if ((i <= 200000) && (a[i] == item)) return i;
>> 
>> ...repeated.
>
> You didn't think.  This was deliberate, since as I read it the
> original asked for an array that could hold a[200000].
[...]

I'm curious how you inferred that from

| Would you rather wait for the results of a quicksort, a linear
| search, or a bubble sort on a 200000 element array?

There was no implication that a[200000] had to be valid.

-- 
Keith Thompson (The_Other_Keith) <kst-u@[EMAIL PROTECTED]
>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"