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

CBFalconer said:

> Keith Thompson wrote:
>> 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.
> 
> I don't remember.

You don't have to. He quoted the original for you.

> The original is long gone from here.

He quoted it for you. And here's the message ID:

<d0d74e60-6e0c-4572-a1af-4fab4188e757@[EMAIL PROTECTED]
>

And just to make it completely obvious, here's the thread subject line:

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

> The point
> is that the code I published was self-consistent.

No, the point is that the code you published was *wrong*.


> If a[200000] in inaccessible the coding is simpler.

Which is why everyone is so puzzled that you got it wrong.

Well, we all make mistakes - but when people point out your mistake, it's 
not wise to start firing off accusations at them, such as "you didn't 
think". It is true that someone wasn't thinking, but that someone isn't 
the someone you thought it was.

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www.
+rjh@[EMAIL PROTECTED]
 users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999