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

CBFalconer said:

> 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.

I didn't have to think very hard to see that the code is wrong. Given the 
size of the array, the code is broken.

> This was deliberate, since as I read it the
> original asked for an array that could hold a[200000].

As you /wrote/ it, however, "n is the size of the array, here 200000". For

such an array, evaluating a[200000] is an error. I am not a mind-reader. I

can only go on what you write.

-- 
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