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

[mike-yue]

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?
1Quicksort
2Linear Search
3Bubble Sort

The answer is 2Linear Search

Could someone explain why Linear Search, not the other two options?
Or I misunderstood the original question?

Thanks you guys!

[James Harris]

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

On 4 May, 23:27, mike-yue <needpass...@gm ail.comwrote:

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?
1Quicksort
2Linear Search
3Bubble Sort
>
The answer is 2Linear 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.programmin g.

--

[Richard Heathfield]

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

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?
1Quicksort
2Linear Search
3Bubble Sort
>
The answer is 2Linear 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

[Peter Nilsson]

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?
1Quicksort
2Linear Search
3Bubble Sort
>
The answer is 2Linear 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

[mike-yue]

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

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

[Richard Heathfield]

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

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

[Keith Thompson]

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

mike-yue <needpassion@gm ail.comwrites:

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.

Please quote some context when you post a followup.

The missing context is the question in your original article:

| Would you rather wait for the results of a quicksort, a linear search,
| or a bubble sort on a 200000 element array?
| 1Quicksort
| 2Linear Search
| 3Bubble Sort

but neither Quicksort nor Bubblesort is a searching algorithm. Since
they do entirely different things, asking which one you'd rather wait
for doesn't make a whole lot of sense.

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!

And this was a problem? That's certainly something I'd expect any
good programmer to know. If you're going to be writing code that does
sorting and searching, and you don't know this stuff, there's an
excellent chance your code is going to be unacceptable slow.

(Quicksort is O(N log N) best case and average case; a straightforward
implementation is O(N**2) worst case, but it can be made O(N log N)
with a little tweaking.)

--
Keith Thompson (The_Other_Keit h) <kst-u@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Charlton Wilbur]

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

>>>>"my" == mike-yue <needpassion@gm ail.comwrites:

myThe topic comes from a question: Would you rather wait for the
myresults of a quicksort, a linear search, or a bubble sort on a
my200000 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@chromat ico.net

[Ian Collins]

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

Richard Heathfield wrote:

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

Or in my case, 99% of programming has been making hardware or web pages
tick, without a bit O in sight!

--
Ian Collins.

[CBFalconer]

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?
1Quicksort
2Linear Search
3Bubble Sort
>
The answer is 2Linear 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 **

[Richard Heathfield]

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

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.

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

[CBFalconer]

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

[Richard Heathfield]

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@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Keith Thompson]

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

CBFalconer <cbfalconer@yah oo.comwrites:

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.

--
Keith Thompson (The_Other_Keit h) <kst-u@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Antoninus Twink]

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

On 5 May 2008 at 0:13, Richard Heathfield wrote:

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 think it's pretty obvious to anyone who isn't so literal-minded that
he stops with a syntax error at the first place where most humans would
be happy to read between the lines that implicit in the question is:
would you rather linearly search a list, or first sort it and then
perform a binary search?

To which the answer depends primarily on *how many* searches you're
going to perform.