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: mr*@tusur.ru 14  2480 
On 2005-06-17 21:53:36 -0400, "Roman Mashak" <mr*@tusur.ru> 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 cl*******@gmail.com
On Sat, 18 Jun 2005 10:53:36 +0900, "Roman Mashak" <mr*@tusur.ru>
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: mr*@tusur.ru
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
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
but do remember that you should scan the whole array, any how.. ;>
eager to know possible further optimizations..
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?"
"Roman Mashak" <mr*@tusur.ru> 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.
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
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 ---
Le 18/06/2005 17:01, dans x4********************@comcast.com, «*Joe Wright*»
<jo********@comcast.net> 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.
Le 18/06/2005 17:04, dans BE******************************@laposte.net,
«*Jean-Claude Arbaut*» <je****************@laposte.net> a écrit*:
Le 18/06/2005 17:01, dans x4********************@comcast.com, «*Joe Wright*»
<jo********@comcast.net> 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 :-)
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: mr*@tusur.ru
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
In article <BE******************************@laposte.net>,
Jean-Claude Arbaut <je****************@laposte.net> wrote: Le 18/06/2005 17:01, dans x4********************@comcast.com, «*Joe Wright*»
<jo********@comcast.net> 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.
Jean-Claude Arbaut wrote:
Le 18/06/2005 17:04, dans BE******************************@laposte.net,
« Jean-Claude Arbaut » <je****************@laposte.net> a écrit :
Le 18/06/2005 17:01, dans x4********************@comcast.com, « Joe Wright »
<jo********@comcast.net> 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 ---
# >>> 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[i];
will check for strictly increasing. For increasing, use X[i-1]<=X[i].
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[i];
if (cc<0) {
for (; i<N && monotonic; i++) monotonic = X[i-1]< /*<=*/ X[i];
}else if (cc>0) {
for (; i<N && monotonic; i++) monotonic = X[i-1]> /*>=*/ X[i];
}
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. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Alex Hopson |
last post by:
Hi,
I've got a multidimensional array and I can loop through it fine but I can't
get the values of first parts of the array - ie:
foreach ($a as $v1) {
foreach ($v1 as $v2) {
echo "$v2\n";...
|
by: Jason |
last post by:
I have a number of arrays that are populated with database values. I
need to determine which array has the highest ubound out of all the
arrays. The array size will always change based on the...
|
by: JT |
last post by:
how do i determine how many items are in an array? the following code
creates an array of values each time a space is found in a name field. the
problem is that sometimes names have middle...
|
by: hello smith |
last post by:
Hello,
I have an unsigned char array. I want to determine if each char's ascii
value is less than 127. Is there a faster way than looping through the
characters and checking if each is less than...
|
by: yancheng.cheok |
last post by:
hello, may i know how i can determine whether a pointer is pointing to
an array or a single item during runtime?
this is because in certain situation, i need to determine whether to
use delete...
|
by: alvinwoon |
last post by:
URL: http://events.unl.edu/
Description: i coded a quick and dirty key navigation for the calendar.
if you press left arrow on your keyboard, it will navigate to the
previous date and fire an...
|
by: Anthony2oo5 |
last post by:
Hello people, just a quick question I have here.
My array looks like this:
Array (
=> Array (
=> 15
=> example.com
=> examplecom
=> NshKsi23
|
by: John B |
last post by:
Hi all,
Say I have the int 123456789
What would be the quickest/best way to convert it to
int{1,2,3,4,5,6,7,8,9}
What I came up with was to determine the largest factor of 10 (100M)
divide by...
|
by: raylopez99 |
last post by:
I would like to know if there's a quick "Linq" way to find the index
of an array having a particular value. I can do this the long way by
sequential iteration, but would like to know if there's a...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
| |
