How do we find which one among the given ints is the largest?

[madmaxsantana]

Hi there guys!
I am using C to write a program for an embedded system.
I have come to a point where I need to find which of the provided numbers is the largest...
I have a logic in my mind, a for loop through which I compare first first digit with the 2nd, if 2nd is greater, discard 1st and compare 2nd with the 3rd and so on. It is called bubble-sorting, I think...

But the thing is, the microcontroller is operating at a very low frequncy (the frequency is mere 4MHz)... Bubble sorting would take a lot of time and since the input/output in real time, the output on graphic LCD will appear lagging...

Is there a faster technique? Please let me know if you can think of a better logic... If there is some built in function (in standard libraries of course) for the mentioned purpose, that'd be great to know.

Praying for a quick answer. :)

[RedX]

int max=MIN_INT; //smallest int available
for(int i = 0; i < numberCount; ++i){
  if( numbers[i] > max){
    max = numbers[i];
  }
}

This is exactly your idea but in code... what is wrong with it? Or do you need to sort the numbers?

[Albatross]

Ah, I remember when 300 Mhz was top-of-the-line...

Here's a potential algorithm for you to use. It's completely linear in all scenarios.
http://en.wikipedia.org/wiki/Counting_sort

EDIT: Oops. Wrong problem.

-Albatross

[madmaxsantana]

This is exactly your idea but in code... what is wrong with it? Or do you need to sort the numbers?

Hehehe!
RedX that's exactly what I explained in my post. Had it been a uProcessor working at above 1000MHz, I'd definitely use that algorithm... :)
But you see, MCU chips (I am using a PIC16F887) can run at max on 20 MHz, whereas I have a crystal of 4MHz with me. Each assembly instruction takes as much as 1us and the for loops in C take dozens of assembly instructions... Not even that, I have to literally turn on the respective pixels on a graphic LCD in the same loop. Determining which one's the largest and displaying the result on LCD can take 0.5 sec/cycle and that would be too much if I want my I/O to be real time... The output on LCD will be literally blinking... :)
That's why I thought to seek for a faster algorithm which would reduce my calculation time, hence keeping the animation on LCD pretty... :)

[madmaxsantana]

And Ouchhhh @ Albatross...

Very kind of you to help me... I am thankful...

But you see, my max - min range is 1024... :P

That'd even larger and slower a loop, considering that my slow MCU will have to literally run 1024 times, (instead of 8 times in bubble sorting case)...

[Albatross]

Hmm... that could be a small problem.

-Albatross

[Athar]

There can't be any better algorithm than the one RedX posted, because in order to find the largest number, you'll obviously have to look at each number at least once. Perhaps you didn't read the code properly?
It has nothing to do with bubble sort - it doesn't even sort anything.

[RedX]

Ok, i programmed an atmega myself, it was 16Mhz but still i had no problem.
The only thing i see it that you keep track everytime you insert a number if that is the new max or not. Else i think you will have to iterate over the array. A for loop is by no means expensive. When optimization is turned on it's just a few instructions (1 compare and 1 conditional jump). If you have a register to spare put the "i" (volatile) in it so you can save memory accesses.

Btw 1/4Mhz is stilll invisible to the eye. You could even compare 500 thousand values and it would not blink. On the other hand your LCD is very slow compared to the PIC.