Velocity Reviews > quick way to determine the array is irdered?

# quick way to determine the array is irdered?

Roman Mashak
Guest
Posts: n/a

 06-18-2005
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: http://www.velocityreviews.com/forums/(E-Mail Removed)

Clark S. Cox III
Guest
Posts: n/a

 06-18-2005
On 2005-06-17 21:53:36 -0400, "Roman Mashak" <(E-Mail Removed)> 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
(E-Mail Removed)

Jack Klein
Guest
Posts: n/a

 06-18-2005
On Sat, 18 Jun 2005 10:53:36 +0900, "Roman Mashak" <(E-Mail Removed)>
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: (E-Mail Removed)

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/~a...FAQ-acllc.html

r.devaraj@gmail.com
Guest
Posts: n/a

 06-18-2005
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

r.devaraj@gmail.com
Guest
Posts: n/a

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

eager to know possible further optimizations..

Emmanuel Delahaye
Guest
Posts: n/a

 06-18-2005
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?"

Malcolm
Guest
Posts: n/a

 06-18-2005

"Roman Mashak" <(E-Mail Removed)> 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.

Lawrence Kirby
Guest
Posts: n/a

 06-18-2005
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

Joe Wright
Guest
Posts: n/a

 06-18-2005
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 ---

Jean-Claude Arbaut
Guest
Posts: n/a

 06-18-2005

Le 18/06/2005 17:01, dans (E-Mail Removed), «*Joe Wright*»
<(E-Mail Removed)> 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.