quick way to determine the array is irdered?

Discussion in 'C Programming' started by Roman Mashak, Jun 18, 2005.

  1. Roman Mashak

    Roman Mashak Guest

    Hello, All!

    Is there an easy way to determine that array e.g. int X[N] contains ordered
    items (for example, ascending), except running loop with comparison of
    items?

    It would be good to provide me with some useful link :)

    Thanks!

    With best regards, Roman Mashak. E-mail:
     
    Roman Mashak, Jun 18, 2005
    #1
    1. Advertising

  2. On 2005-06-17 21:53:36 -0400, "Roman Mashak" <> said:

    > Hello, All!
    >
    > Is there an easy way to determine that array e.g. int X[N] contains
    > ordered items (for example, ascending), except running loop with
    > comparison of items?


    No.

    --
    Clark S. Cox, III
     
    Clark S. Cox III, Jun 18, 2005
    #2
    1. Advertising

  3. Roman Mashak

    Jack Klein Guest

    On Sat, 18 Jun 2005 10:53:36 +0900, "Roman Mashak" <>
    wrote in comp.lang.c:

    > Hello, All!
    >
    > Is there an easy way to determine that array e.g. int X[N] contains ordered
    > items (for example, ascending), except running loop with comparison of
    > items?
    >
    > It would be good to provide me with some useful link :)
    >
    > Thanks!
    >
    > With best regards, Roman Mashak. E-mail:


    There are other ways, but not likely to be quicker.

    You could use a second array of the same type and size (defined or
    allocated) and copy the first array into the second. Then you could
    sort the second with qsort() or a sort function you write yourself.

    Then you could compare the two arrays element by element and if you
    find a difference, the first array was not ordered.

    But as I said, not likely to be quicker.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Jun 18, 2005
    #3
  4. Roman Mashak

    Guest

    i guess, one simple way ( rather than going for quick sort ) of doing
    it at o(n) is,(if ur goal is just to check ascending or descending
    property)

    Check the difference between the consecutive elements, for the whole
    array.

    The array is ascending or descending, depending on the difference..

    (more blah-blah:

    if an array is in descending order, an element will be always greater
    than its successor... just check this for whole array.. and the other
    way for asceding order..)


    Regards,
    Devaraj Rangasamy
     
    , Jun 18, 2005
    #4
  5. Roman Mashak

    Guest

    but do remember that you should scan the whole array, any how.. ;>



    eager to know possible further optimizations..
     
    , Jun 18, 2005
    #5
  6. Roman Mashak wrote on 18/06/05 :
    > Is there an easy way to determine that array e.g. int X[N] contains ordered
    > items (for example, ascending), except running loop with comparison of items?


    if (X[0] == searched)
    else if X[1] == searched <...>
    else if X[2] == searched <...>
    else if X[3] == searched <...>
    <...>
    else if x[N-1] == searched <...>

    If you don't like this code, use ... a loop ... !

    In real world, the loop is more or less hidden by some lookup functions
    such as the standard qsort()/bsearch() couple or some handmade
    functions...

    --
    Emmanuel
    The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
    The C-library: http://www.dinkumware.com/refxc.html

    I once asked an expert COBOL programmer, how to
    declare local variables in COBOL, the reply was:
    "what is a local variable?"
     
    Emmanuel Delahaye, Jun 18, 2005
    #6
  7. Roman Mashak

    Malcolm Guest

    "Roman Mashak" <> wrote
    > Is there an easy way to determine that array e.g. int X[N] contains
    > ordered items (for example, ascending), except running loop with
    > comparison of items?
    >
    > It would be good to provide me with some useful link :)
    >

    No way of doing what you wnat in less than O(N) time.

    However if you know the propeties of your array you can do a "good enough"
    test by taking the start, the end, the middle, and the second and third
    quartiles. The chance of these being in order by chance is relatively low.
    (5!, or 1 in 120) In addition if the middle is very approximately the mean
    of the middle three, and you know the distribution is either unform or with
    a symmetrical central peak, then it is pretty certain that the array is
    ordered.
    What the test won't detect is slight deviations from orderedness, for
    instnace by swapping one pair of elements. These could be malicious or they
    could be because ordering is not random. However the chance of them arising
    from a random distribution is vanishingly small.
     
    Malcolm, Jun 18, 2005
    #7
  8. On Sat, 18 Jun 2005 10:53:36 +0900, Roman Mashak wrote:

    > Hello, All!
    >
    > Is there an easy way to determine that array e.g. int X[N] contains ordered
    > items (for example, ascending), except running loop with comparison of
    > items?


    Note that comp.lang.c is for discussing the C programming language itself,
    a good place to discuss algorithms is comp.programming.

    If you know nothing about the array then you probably won't do better than
    this, you clearly need to access evenry element of the array to determine
    this, any element you don't access might be out of order and your
    algorithm couldn't detect it. OTOH it might be better to deal with this
    when you build the array, e.g. build it ordered or test ordering while you
    build it. In that case the determining step becomes trivial.

    Lawrence
     
    Lawrence Kirby, Jun 18, 2005
    #8
  9. Roman Mashak

    Joe Wright Guest

    Roman Mashak wrote:
    > Hello, All!
    >
    > Is there an easy way to determine that array e.g. int X[N] contains ordered
    > items (for example, ascending), except running loop with comparison of
    > items?
    >
    > It would be good to provide me with some useful link :)
    >


    No. You have to check. What will you do if, after checking, X is not
    ordered? Will you then order it? If so, don't check at all, simply order
    the array with a simple insertion sort. If X were already ordered only
    checking takes place.

    --
    Joe Wright
    "Everything should be made as simple as possible, but not simpler."
    --- Albert Einstein ---
     
    Joe Wright, Jun 18, 2005
    #9
  10. Re : quick way to determine the array is irdered?

    Le 18/06/2005 17:01, dans , « Joe Wright »
    <> a écrit :

    > Roman Mashak wrote:
    >> Hello, All!
    >>
    >> Is there an easy way to determine that array e.g. int X[N] contains ordered
    >> items (for example, ascending), except running loop with comparison of
    >> items?
    >>
    >> It would be good to provide me with some useful link :)
    >>

    >
    > No. You have to check. What will you do if, after checking, X is not
    > ordered? Will you then order it? If so, don't check at all, simply order
    > the array with a simple insertion sort. If X were already ordered only
    > checking takes place.


    And if it was not, insertion sort is a snail, bad advice I think.
     
    Jean-Claude Arbaut, Jun 18, 2005
    #10
  11. Le 18/06/2005 17:04, dans BEDA0490.56DC%,
    « Jean-Claude Arbaut » <> a écrit :

    >
    >
    >
    > Le 18/06/2005 17:01, dans , « Joe Wright »
    > <> a écrit :
    >
    >> Roman Mashak wrote:
    >>> Hello, All!
    >>>
    >>> Is there an easy way to determine that array e.g. int X[N] contains ordered
    >>> items (for example, ascending), except running loop with comparison of
    >>> items?
    >>>
    >>> It would be good to provide me with some useful link :)
    >>>

    >>
    >> No. You have to check. What will you do if, after checking, X is not
    >> ordered? Will you then order it? If so, don't check at all, simply order
    >> the array with a simple insertion sort. If X were already ordered only
    >> checking takes place.

    >
    > And if it was not, insertion sort is a snail, bad advice I think.
    >


    BTW, doing a check and sorting with heapsort is still better
    asymptotically :)
     
    Jean-Claude Arbaut, Jun 18, 2005
    #11
  12. Roman Mashak

    Mac Guest

    On Sat, 18 Jun 2005 10:53:36 +0900, Roman Mashak wrote:

    > Hello, All!
    >
    > Is there an easy way to determine that array e.g. int X[N] contains ordered
    > items (for example, ascending), except running loop with comparison of
    > items?
    >
    > It would be good to provide me with some useful link :)
    >
    > Thanks!
    >
    > With best regards, Roman Mashak. E-mail:


    Maybe you can throw the array into a struct along with a flag indicating
    whether the array is sorted. Of course it will then be necessary to keep
    the flag up to date in all cases.

    struct data
    { int *X;
    int is_sorted;
    };

    --Mac
     
    Mac, Jun 18, 2005
    #12
  13. In article <BEDA0490.56DC%>,
    Jean-Claude Arbaut <> wrote:

    > Le 18/06/2005 17:01, dans , « Joe Wright »
    > <> a écrit :
    >
    > > Roman Mashak wrote:
    > >> Hello, All!
    > >>
    > >> Is there an easy way to determine that array e.g. int X[N] contains ordered
    > >> items (for example, ascending), except running loop with comparison of
    > >> items?
    > >>
    > >> It would be good to provide me with some useful link :)
    > >>

    > >
    > > No. You have to check. What will you do if, after checking, X is not
    > > ordered? Will you then order it? If so, don't check at all, simply order
    > > the array with a simple insertion sort. If X were already ordered only
    > > checking takes place.

    >
    > And if it was not, insertion sort is a snail, bad advice I think.


    Should run in O (k*N) if k elements in an initially sorted array of N
    elements have been changed. Kind of hard to beat for small k.
     
    Christian Bau, Jun 18, 2005
    #13
  14. Roman Mashak

    Joe Wright Guest

    Jean-Claude Arbaut wrote:
    >
    >
    > Le 18/06/2005 17:04, dans BEDA0490.56DC%,
    > « Jean-Claude Arbaut » <> a écrit :
    >
    >
    >>
    >>
    >>Le 18/06/2005 17:01, dans , « Joe Wright »
    >><> a écrit :
    >>
    >>
    >>>Roman Mashak wrote:
    >>>
    >>>>Hello, All!
    >>>>
    >>>>Is there an easy way to determine that array e.g. int X[N] contains ordered
    >>>>items (for example, ascending), except running loop with comparison of
    >>>>items?
    >>>>
    >>>>It would be good to provide me with some useful link :)
    >>>>
    >>>
    >>>No. You have to check. What will you do if, after checking, X is not
    >>>ordered? Will you then order it? If so, don't check at all, simply order
    >>>the array with a simple insertion sort. If X were already ordered only
    >>>checking takes place.

    >>
    >>And if it was not, insertion sort is a snail, bad advice I think.
    >>

    You think? I expect that 'int X[N]' is maintained in order. Calling an
    insertion sort on X when X is already ordered is fast as lightning.
    >
    >
    > BTW, doing a check and sorting with heapsort is still better
    > asymptotically :)
    >

    My point was to sort without checking, knowing the result is an ordered
    array. The choice of which sort algorithm is up to the user.

    --
    Joe Wright
    "Everything should be made as simple as possible, but not simpler."
    --- Albert Einstein ---
     
    Joe Wright, Jun 18, 2005
    #14
  15. Roman Mashak

    SM Ryan Guest

    # >>> Is there an easy way to determine that array e.g. int X[N] contains ordered
    # >>> items (for example, ascending), except running loop with comparison of
    # >>> items?

    Sheesh, the answer is there is no library function, but it's easy to code
    with one loop.
    int increasing = 1,i;
    for (i=1; i<N && increasing; i++) increasing = X[i-1]<X;
    will check for strictly increasing. For increasing, use X[i-1]<=X.
    You can use > and >= for strictly decreasing and decreasing. To
    check monotonictity
    int monotonic = 1,cc = 0,i;
    for (i=1; i<N && cc==0; i++) cc = X[i-1]-X;
    if (cc<0) {
    for (; i<N && monotonic; i++) monotonic = X[i-1]< /*<=*/ X;
    }else if (cc>0) {
    for (; i<N && monotonic; i++) monotonic = X[i-1]> /*>=*/ X;
    }
    For N=0 and N=1, X is reported as (strictly) monotonic, increasing and decreasing.

    If there are no other constraints on X besides being integers, you need N-1
    binary comparison. Picture it as a binary tree with N leaves: no matter how
    you arrange the tree, you will always have N-1 internal nodes.

    On a parallel machines you can divide the tree in halves and halves again
    recursively and thus complete it in lg N steps, but you will need N/2
    processors in parallel.

    --
    SM Ryan http://www.rawbw.com/~wyrmwif/
    The whole world's against us.
     
    SM Ryan, Jun 18, 2005
    #15
    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. JKop
    Replies:
    11
    Views:
    886
  2. Quick way to zero array

    , May 12, 2006, in forum: C Programming
    Replies:
    14
    Views:
    520
    Malcolm
    May 13, 2006
  3. 001
    Replies:
    18
    Views:
    3,371
    Mike Schilling
    Apr 5, 2007
  4. Peña, Botp
    Replies:
    1
    Views:
    241
    Robert Klemme
    Jan 24, 2004
  5. Max Williams
    Replies:
    6
    Views:
    133
    Max Williams
    Jan 21, 2008
Loading...

Share This Page