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?

Thanks you guys!

On 4 May, 23:27, mike-yue <needpass...@gmail.com> 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?

Well, it's a poor question: asking what /you/ would prefer to do; but
presuming you want to wait as little time as possible wouldn't option
2 finish soonest? The fact that sorting and searching accomplish
different things also seems to be there to confuse.

You might be better asking questions on programming (i.e. not on C) in
comp.programming.

--

On Sun, 4 May 2008 15:27:30 -0700 (PDT), mike-yue
<needpassion@gmail.com> 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?

This isn't a C question; it is a general programming question -
comp.programming would be a better newsgroup. That said, the
answer to your question is that sorting is more expensive than
linear searching because in a linear search you only have to
visit each element once, whereas when you sort an array you have
to visit each element several times in order to determine its
placement in the sorted array. In particular:

Quicksort is an O(N*log N) algorithm.
Linear search is an O(N) algorithm.
Bubble sort is an O(N*N) algorithm.

If you do not know what the big O function is, find out. It is
fundamental knowedge that you need if you are going to program.



Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

mike-yue said:

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

The question is testing your knowledge of algorithmic complexity.

As the number of data items rises (especially past the limit where you can
reasonably think of all numbers as being basically the same size), you can
begin to ignore minor factors like the cost of overheads (e.g. opening a
file) and even, to some extent, the machine speed! All that matters, for
large N, is how this N affects the algorithm.

Quicksort is O(N * log N). Linear search is O(N). Bubble sort is O(N * N).

To understand, plot the graphs.

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

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?

Given that 1 and 3 are sorts, and 2 is a search, and given that it's
far from clear what 'result' you're supposedly waiting for, I'd say
you have misunderstood, or you've mis-remembered it.

In any case, this is a general programming question, not a question
on the C language.

--
Peter

All very good answers. many thanks for you guys,
In a word, the Liner Search is the cheapest method to search. the
other two are complicated and expensive.

I know it is about algorithmic complexity, but I totally forget the
defination of the O, even the Log. University time seems a century ago
I almost forget everything.

I think it is useless for 99% programmer jobs, unfortunately it's
always been asked. Once a interviewer asked me to explain the
algorithmic complexity of quick sort!


Thanks again

mike-yue said:

> All very good answers. many thanks for you guys,
> In a word, the Liner Search is the cheapest method to search. the
> other two are complicated and expensive.

Whilst your claim is true, it is meaningless. Linear search is a search
technique. The other two are sorting techniques. It's tempting to say that
you're comparing apples with oranges, but it's more like comparing apples
with October.

> I know it is about algorithmic complexity, but I totally forget the
> defination of the O, even the Log. University time seems a century ago
> I almost forget everything.
>
> I think it is useless for 99% programmer jobs,

That's only true because 99% of programming jobs don't actually require
very much programming skill.

> unfortunately it's
> always been asked. Once a interviewer asked me to explain the
> algorithmic complexity of quick sort!

Well, that's a reasonable question, isn't it? And hardly difficult.

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

>>>>> "my" == mike-yue <needpassion@gmail.com> writes:

my> The topic comes from a question: Would you rather wait for the
my> results of a quicksort, a linear search, or a bubble sort on a
my> 200000 element array?

I myself would rather wait for the results of a bubble sort; this
means I have much more chance of my tea being ready before the result
set is.

Charlton



--
Charlton Wilbur
cwilbur@chromatico.net