# Counting the out-of-order elements of an array

Is there any way to write is C function better so the procedure could spend less time to calculate the results?

Assume that the array size is 1.000.000 and all the numbers are greater than 0.

The function read the array backwards, saves the first number to maximum, then check the next number, a, and if it's greater than the maximum, it adds +1 to total. Then the maxinum takes the value of a and procide to next one until the end of array.

static int total = 1;

int chck_high( int *my_array, int *endp) {
// this function should only be called if there is at least one value in the array
int maximum = *(--endp);

while ( endp > my_array ) {
int a = *(--endp);

if ( a > maximum ) {
total++;
maximum = a;
}
}

return maximum;
}


I tried to use unsigned ints, but I don't know if it's worth it. Can someone please tell me if there is a better way to write that code?

Previous version of the code:

int process( int *my_array, int *endp) {
int a, b;
//static int total = 1;
if ( my_array == 0 ) return 0;
if ( my_array == endp ) return INT_MIN;
else a = *my_array++;
if ( (b= process( my_array, endp )) == INT_MIN ) return a;
if ( a > b )
{total++; return printf( "%d > %d and total now is %d\n", a, b, total ), a; }
return b;
}


The two functions called with the following code:

chck_high(my_array, my_array + count);


where my_array is my array with nums and count is the number that says the size of the array.

Avoid static variables as much as possible. Instead of static total, you could pass in a pointer to total and make the function modify the value it's pointing to.

The names are not great:

• Instead of my_array, start would be better
• Instead of endp, end would be better
• Instead of chck_high, ... I don't know what would be better, because I don't really see the general logic this function represents. It counts the number of times a new local maximum is found going backwards from the end of the range, and sets the value of total. I'm wondering if this logic is really necessary in this form, or perhaps the overall logic of your program could be redesigned to simpler elements.

Instead of a comment like this:

// this function should only be called if there is at least one value in the array


It would be better to use an assertion:

assert(start < end);


Note that this requires to #include <assert.h>

This maybe a matter of taste, but I would find a for loop would be more natural for this instead of while. Using a for loop, in C99 and above, you could declare the loop variable inside the for, which would have extra benefits:

• It would help you limit variables in the smallest scope necessary (inside the loop)
• It would force you to use a new local variable for looping, instead of reusing the function parameter, which is a good thing

Putting it together, the function would become:

int chck_high(int *start, int *end, int *total) {
assert(start < end);

int maximum = *--end;

for (int * pos = end; pos > start; --pos) {
int a = *pos;
if ( a > maximum ) {
++*total;
maximum = a;
}
}

return maximum;
}


To enable C99 mode when compiling with gcc, use the -std=c99 flag.

You can use the function like this, for example:

int main() {
int arr[] = {1, 2, 51, 41, 4, 5};
int total = 1;
int maximum = chck_high(&arr[0], &arr[0] + 6, &total);
printf("total=%d max=%d\n", total, maximum);
}

• thanks I will update my code with a previous version just to see what it does from another point of view Commented Nov 29, 2014 at 15:18
• ..and how do I call the function? Also how can i skip the c99 mode just to use the standar compile code : gcc o. -o out.exe Commented Nov 29, 2014 at 15:28
• how do I call the total variable? Commented Nov 29, 2014 at 15:29
• For C99 mode, pass -std=c99. Probably count would be a better name than total. As for the name of the function, I don't know, as I explained. I have a feeling the rest of the program can be probably redesigned to have more logical elements that are easy to name. Commented Nov 29, 2014 at 15:34
• do you want me to upload all the program? As for the '-std=c99' I knew what I wanted, i just ask if I can skip it changing the program Commented Nov 29, 2014 at 15:37

There is a slightly faster way to do this.

int hinum(const int *begin, const int *end, int *total) {
int hinum;
*total = 1;
--begin;
--end;
for (hinum = *end; end != begin; --end)
if (*end > hinum) {
hinum = *end;
++(*total);
}
return hinum;
}


Here's the driver program I wrote to test both routines:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int total = 1;

/* original and new routines go here */

int main(int argc, char *argv[])
{
const int arrsize = 1000000;
const int iterations = 100000;
int m = 0;
int *begin = malloc(arrsize*sizeof(int));
if (begin == NULL) {
perror("unable to allocate memory for array");
return 1;
}
/* populate the array */
int *end = begin + arrsize;
for (int *i = begin; i != end; ++i)
*i = rand();

/* run either old or new routine */
if (argc > 1 && 0 == strncmp(argv[1],"old",3)) {
printf("old routine\n");
for (int i = iterations; i; --i) {
total = 1;
m = chck_high(begin, end);
}
printf("highest number %d, total = %d\n", m, total);
} else {
printf("new routine\n");
for (int i = iterations; i; --i) {
m = hinum(begin, end, &total);
}
printf("highest number %d, total = %d\n", m, total);
}
free(begin);
}


Note, too that I've improved the interface to use const and to no longer use a global variable for total.

When I call this on my machine here's example output:

$/usr/bin/time ./hinum new new routine highest number 2147480021, total = 13 70.06user 0.00system 1:10.02elapsed 100%CPU (0avgtext+0avgdata 5156maxresident)k 0inputs+0outputs (0major+1038minor)pagefaults 0swaps$ /usr/bin/time ./hinum old
old routine
highest number 2147480021, total = 13
71.08user 0.00system 1:11.08elapsed 100%CPU (0avgtext+0avgdata 5152maxresident)k
0inputs+0outputs (0major+1038minor)pagefaults 0swaps


As you can see, the new routine is very slightly faster.

• yes but i need to print the total int in an txt file when the procidure done. And the fprinf command is in the main function. How am I supposed to use total to another function if isn't a global variable? Commented Nov 29, 2014 at 15:16
• ..and how do I call the function? Commented Nov 29, 2014 at 15:26
• @NikosKLon: I've added the driver code to my answer and expanded on the timing I measured. Commented Nov 29, 2014 at 16:19
• so is this ~ 1 sec? What is your computer specs? Commented Nov 29, 2014 at 16:34
• @NikosKLon: this machine is an Intel i5 running at 2.6GHz and 64-bit Linux. Compiler is gcc and timings used -O2 optimization. But the important thing is not how fast it runs on my machine, but how fast it runs on your machine! Time it for yourself to be sure. Commented Nov 29, 2014 at 16:38

You said:

saves the first number to maximum, then check the next number, a, and if it's greater than the maximum, it adds +1 to total. Then the maxinum takes the value of a and procide to next one until the end of array.

But what do you do if your array looks like 6 7 8 9 10 0 1 2 3 4? You detect 1 element out of order.

Would sorting the array (into another one) and then comparing them element-by-element be too slow? You have $O(NlogN)$ for quicksort and then $O(N)$ when you go through the arrays one more time.