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

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].  For demo
purposes the idea is to use the original constant.  The code within
the loop is the only thing that affects the speed, in practice.

-- 
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: <http://cbfalconer.home.att.net>
            Try the download section.


** Posted from http://www.teranews.com
**