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

**James Harris** · Jun 27 '08, 07:35 PM

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

On 5 May, 01:26, Keith Thompson <ks...@mib.orgw rote:

mike-yue <needpass...@gm ail.comwrites:

....

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

It's not difficult to /state/ the complexity of quicksort (assuming
one remembers it) but it is another thing to /explain/ it.

--

**rio** · Jun 27 '08, 07:35 PM

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

"CBFalconer " <cbfalconer@yah oo.comha scritto nel messaggio
news:481E5A93.9 0259CC4@yahoo.c om...

for (i = 0; i <= 200000; i++) {
if (a[i] == item) break;
}
if ((i <= 200000) && (a[i] == item)) return i;
else /* failure */ return -1;

why not

if(a) for (i = 0; i<=200000; ++i)
{if (a[i] == item) return i;}
else return -1;

**mike-yue** · Jun 27 '08, 07:35 PM

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

On May 4, 5:26 pm, Keith Thompson <ks...@mib.orgw rote:

mike-yue <needpass...@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
>

There is no missing context. The question is exactly the original
question, no more no less.

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.

Seems I need pick up my old textbook again

>
(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) <ks...@mib.or g>
Nokia
"We must do something. This is something. Therefore, we must do this.."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

**mike-yue** · Jun 27 '08, 07:35 PM

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

On May 5, 3:43 am, James Harris <james.harri... @googlemail.com wrote:

On 5 May, 01:26, Keith Thompson <ks...@mib.orgw rote:
>

mike-yue <needpass...@gm ail.comwrites:

>
...
>

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

>
It's not difficult to /state/ the complexity of quicksort (assuming
one remembers it) but it is another thing to /explain/ it.
>
--

agree with you. it is more difficult to explain if you learned the
theory in other language, e.g. in Chinese.
I was wondering if it is a easy thing to explain algorithmic
complexity for a programmer whose mother language is English(excludi ng
the geeks who are crazy about algorithmic).

**mike-yue** · Jun 27 '08, 07:35 PM

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

On May 5, 9:58 am, "rio" <a...@b.cwrot e:

"CBFalconer " <cbfalco...@yah oo.comha scritto nel messaggionews:4 81E5A93.90259CC 4@yahoo.com... for (i = 0; i <= 200000; i++) {

if (a[i] == item) break;
}
if ((i <= 200000) && (a[i] == item)) return i;
else /* failure */ return -1;

>
why not
>
if(a) for (i = 0; i<=200000; ++i)
{if (a[i] == item) return i;}
else return -1;

Don't you think:
for (i = 0; i<200000; ++i)
if the condition i<=200000, the array will overflow.

**Keith Thompson** · Jun 27 '08, 07:35 PM

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

mike-yue <needpassion@gm ail.comwrites:

On May 4, 5:26 pm, Keith Thompson <ks...@mib.orgw rote:

>mike-yue <needpass...@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
>>

>
There is no missing context. The question is exactly the original
question, no more no less.

Yes, and since you didn't quote it in your followup *that's* the
missing context.

Since you use Google Groups, you need to be aware that most of us
don't use a web-based interface to read Usenet. The article to which
you're replying may not be readily visible to someone reading your
followup; it might not be available at all. Because of this, you need
to provide enough context so that your followup makes sense on its
own. (But it's rarely necessary or appropriate to quote the *entire*
article.)

Once upon a time, Google Groups had a serious bug that made it
difficult to provide any context when posting a followup. Chris
F.A. Johnson put together a web page explaining how and why to work
around this bug. The bug was fixed some time ago, but the web page
and the ones it links to are still useful, particularly the links
under "Quoting".

<http://cfaj.freeshell. org/google/>

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

**mike-yue** · Jun 27 '08, 07:35 PM

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

On May 5, 12:50 pm, Keith Thompson <ks...@mib.orgw rote:

mike-yue <needpass...@gm ail.comwrites:

On May 4, 5:26 pm, Keith Thompson <ks...@mib.orgw rote:

mike-yue <needpass...@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:

>

>

There is no missing context. The question is exactly the original
question, no more no less.

>
Yes, and since you didn't quote it in your followup *that's* the
missing context.
>
Since you use Google Groups, you need to be aware that most of us
don't use a web-based interface to read Usenet. The article to which
you're replying may not be readily visible to someone reading your
followup; it might not be available at all. Because of this, you need
to provide enough context so that your followup makes sense on its
own. (But it's rarely necessary or appropriate to quote the *entire*
article.)
>
Once upon a time, Google Groups had a serious bug that made it
difficult to provide any context when posting a followup. Chris
F.A. Johnson put together a web page explaining how and why to work
around this bug. The bug was fixed some time ago, but the web page
and the ones it links to are still useful, particularly the links
under "Quoting".
>
<http://cfaj.freeshell. org/google/>
>
--
Keith Thompson (The_Other_Keit h) <ks...@mib.or g>
Nokia
"We must do something. This is something. Therefore, we must do this.."
-- Antony Jay and Jonathan Lynn, "Yes Minister"- Hide quoted text -
>
- Show quoted text -

glad to know the correct method to use google group.
I don't use google group very often, so sorry for that.

**CBFalconer** · Jun 27 '08, 07:35 PM

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

Keith Thompson wrote:

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.

I don't remember. The original is long gone from here. The point
is that the code I published was self-consistent. If a[200000] in
inaccessible the coding is simpler.

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

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

**CBFalconer** · Jun 27 '08, 07:35 PM

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

James Harris wrote:

Keith Thompson <ks...@mib.orgw rote:

mike-yue <needpass...@gm ail.comwrites:

>
...
>

>>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
>implementati on is O(N**2) worst case, but it can be made O(N log N)
>with a little tweaking.)

>
It's not difficult to /state/ the complexity of quicksort (assuming
one remembers it) but it is another thing to /explain/ it.

Why? It is basically the same process for any algorithm based on
chop in half and solve the halves.

--
[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** · Jun 27 '08, 07:35 PM

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

CBFalconer said:

Keith Thompson wrote:

>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;
>>>>
>>>...repeate d.
>>>
>>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.

>
I don't remember.

You don't have to. He quoted the original for you.

The original is long gone from here.

He quoted it for you. And here's the message ID:

<d0d74e60-6e0c-4572-a1af-4fab4188e757@q2 4g2000prf.googl egroups.com>

And just to make it completely obvious, here's the thread subject line:

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

The point
is that the code I published was self-consistent.

No, the point is that the code you published was *wrong*.

If a[200000] in inaccessible the coding is simpler.

Which is why everyone is so puzzled that you got it wrong.

Well, we all make mistakes - but when people point out your mistake, it's
not wise to start firing off accusations at them, such as "you didn't
think". It is true that someone wasn't thinking, but that someone isn't
the someone you thought it was.

--
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** · Jun 27 '08, 07:35 PM

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

Richard Heathfield wrote:

CBFalconer said:

Keith Thompson wrote:

CBFalconer <cbfalconer@yah oo.comwrites:
>Richard Heathfield wrote:
>>CBFalconer said:
>>>

.... snip ...

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

.... snip ...

>
No, the point is that the code you published was *wrong*.
>

If a[200000] in inaccessible the coding is simpler.

>
Which is why everyone is so puzzled that you got it wrong.
>
Well, we all make mistakes - but when people point out your mistake, it's
not wise to start firing off accusations at them, such as "you didn't
think". It is true that someone wasn't thinking, but that someone isn't
the someone you thought it was.

What's the error? My code handles an array whose last member is
indexed by 200000. The finalize stuff allows for the same max.
Yes, the code can be simpler, so what? The point was the O(n)
operation of the simple loop.

I have no objection to admitting errors. This is not one.

--
[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** · Jun 27 '08, 07:35 PM

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

CBFalconer said:

Richard Heathfield wrote:

>CBFalconer said:

<snip>

If a[200000] in inaccessible the coding is simpler.

>>
>Which is why everyone is so puzzled that you got it wrong.
>>
>Well, we all make mistakes - but when people point out your mistake,
>it's not wise to start firing off accusations at them, such as "you
>didn't think". It is true that someone wasn't thinking, but that someone
>isn't the someone you thought it was.

>
What's the error?

Referencing an object that doesn't exist.

My code handles an array whose last member is indexed by 200000.

The array under discussion (see subject line and OP's text) is a
200000-element array, so there is no member in the array for which an
index of 200000 is legal.

The finalize stuff allows for the same max.
Yes, the code can be simpler, so what? The point was the O(n)
operation of the simple loop.
>
I have no objection to admitting errors. This is not one.

It has become *two* errors - the original error, and the rather graver
error of not recognising when one is in error.

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

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

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment