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

Discussion in 'C Programming' started by mike-yue, May 4, 2008.

  1. mike-yue

    mike-yue Guest

    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!
     
    mike-yue, May 4, 2008
    #1
    1. Advertising

  2. mike-yue

    James Harris Guest

    On 4 May, 23:27, 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?


    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.

    --
     
    James Harris, May 4, 2008
    #2
    1. Advertising

  3. 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
     
    Peter Nilsson, May 5, 2008
    #3
  4. mike-yue

    mike-yue Guest

    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, May 5, 2008
    #4
  5. >>>>> "my" == mike-yue <> 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
     
    Charlton Wilbur, May 5, 2008
    #5
  6. mike-yue <> writes:
    > 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?
    | 1> Quicksort
    | 2> Linear Search
    | 3> Bubble 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_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, May 5, 2008
    #6
  7. mike-yue

    Ian Collins Guest

    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.
     
    Ian Collins, May 5, 2008
    #7
  8. mike-yue

    Chris Torek Guest

    >CBFalconer said:
    >> for (i = 0; i <= 200000; i++) {


    In article <>
    Richard Heathfield <> wrote:
    >Rookie error...


    >> if (a == item) break;
    >> }
    >> if ((i <= 200000) && (a == item)) return i;


    >...repeated.


    Given the idea that the array has exactly 200000 elements, anyway.
    In reality the "occupied size" would presumably be a variable.

    In any case, this misses out on a handy trick that can be used when
    the array has enough room. When a[] is the array to be searched and
    n is "occupied size", if a[n] can be overwritten, one can use:

    a[n] = item;
    for (i = 0; a != item; i++)
    continue;

    This removes one test (i < n) from the loop, and yet is guaranteed
    to terminate the loop. Then one need only apply the "i < n" test
    afterward.

    (Also, even with the "i < n" test in the loop, there is no need to
    re-test a==item afterward.)

    In reality, the original question is not very well formed, for
    reasons that others have touched on. If the options include "sorting
    the array", one has to consider how often the searches will happen
    compared to the sort, and whether modifications to the array can
    be done in ways that maintain the sorted order. If the array *is*
    sorted, we can use binary or even interpolative searches rather
    than linear searches. (Binary search is O(log n) and interpolative
    search is O(log log n), in the mythical average case at least.)
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: gmail (figure it out) http://web.torek.net/torek/index.html
     
    Chris Torek, May 5, 2008
    #8
  9. CBFalconer <> writes:
    > 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 == item) break;
    >>> }
    >>> if ((i <= 200000) && (a == 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_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, May 5, 2008
    #9
  10. 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.
     
    Antoninus Twink, May 5, 2008
    #10
  11. mike-yue

    James Harris Guest

    On 5 May, 01:26, Keith Thompson <> wrote:
    > mike-yue <> writes:


    ....

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

    --
     
    James Harris, May 5, 2008
    #11
  12. mike-yue

    mike-yue Guest

    On May 4, 5:26 pm, Keith Thompson <> wrote:
    > mike-yue <> writes:
    > > 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?
    > | 1> Quicksort
    > | 2> Linear Search
    > | 3> Bubble 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_Keith) <>
    > Nokia
    > "We must do something.  This is something.  Therefore, we must do this.."
    >     -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    mike-yue, May 5, 2008
    #12
  13. mike-yue

    mike-yue Guest

    On May 5, 3:43 am, James Harris <> wrote:
    > On 5 May, 01:26, Keith Thompson <> wrote:
    >
    > > mike-yue <> writes:

    >
    > ...
    >
    > > > 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(excluding
    the geeks who are crazy about algorithmic).
     
    mike-yue, May 5, 2008
    #13
  14. mike-yue

    mike-yue Guest

    On May 5, 9:58 am, "rio" <> wrote:
    > "CBFalconer" <> ha scritto nel messaggionews:...>   for (i = 0; i <= 200000; i++) {
    > >      if (a == item) break;
    > >   }
    > >   if ((i <= 200000) && (a == item)) return i;
    > >   else        /* failure */            return -1;

    >
    > why not
    >
    >    if(a) for (i = 0;  i<=200000; ++i)
    >                     {if (a == 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.
     
    mike-yue, May 5, 2008
    #14
  15. mike-yue <> writes:
    > On May 4, 5:26 pm, Keith Thompson <> wrote:
    >> mike-yue <> writes:
    >> > 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?
    >> | 1> Quicksort
    >> | 2> Linear Search
    >> | 3> Bubble 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_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, May 5, 2008
    #15
  16. mike-yue

    mike-yue Guest

    On May 5, 12:50 pm, Keith Thompson <> wrote:
    > mike-yue <> writes:
    > > On May 4, 5:26 pm, Keith Thompson <> wrote:
    > >> mike-yue <> writes:
    > >> > 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?
    > >> | 1> Quicksort
    > >> | 2> Linear Search
    > >> | 3> Bubble 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_Keith) <>
    > 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.
     
    mike-yue, May 5, 2008
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jeff101

    $40 to $200 worth Free Books

    jeff101, Apr 24, 2006, in forum: ASP .Net
    Replies:
    0
    Views:
    457
    jeff101
    Apr 24, 2006
  2. rote
    Replies:
    3
    Views:
    454
    Mark Rae [MVP]
    Jan 24, 2008
  3. lector

    storing 1,000,000 records

    lector, Apr 6, 2008, in forum: C Programming
    Replies:
    19
    Views:
    497
    Barry Schwarz
    Apr 8, 2008
  4. Replies:
    1
    Views:
    488
  5. Rich
    Replies:
    30
    Views:
    503
    Ray at
    Dec 11, 2003
Loading...

Share This Page