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

mike-yue wrote:
> 
> The topic comes from a question:
> 
> Would you rather wait for the results of a quicksort, a linear
> search, or a bubble sort on a 200000 element array?
> 1> Quicksort
> 2> Linear Search
> 3> Bubble Sort
> 
> The answer is 2> Linear Search
> 
> Could someone explain why Linear Search, not the other two
> options? Or I misunderstood the original question?

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++) {
      if (a[i] == item) break;
   }
   if ((i <= 200000) && (a[i] == item)) return i;
   else        /* failure */            return -1;

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


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