Median algorithm for 8051

How much time between each of the 64 ADC acquisitions?

I'm thinking linked-list implementation (using static array) as each value is acquired...

Regards,

This seems to have a reasonable discussion and code samples:

Pete Harrison

Median means you sort a number of samples and take the middle one. It cannot be too difficult to implement that functionality by yourself.

Rene

In article , Arthur Richards writes

What do you mean the Keil compiler doesn't support it?

Is this home work?

Nice resource... filed for future reference... ;)

Regards,

Possibly look at smaller sorts of sections using the top 'n' bits of the data as a hashing table to specify your sections. This is best done with some link lists, but may end up using more data storage of byte size. The hashing table may be using 4 bits of the data if twelve bit ADC, so you only actually store the bottom 8 bits directly. Even a bubble sort of each index table (upto 64 values for each) on index to byte data may be fast, but puts in a level of indirection.

With only 64 items you could possibly just use a bubble sort as each value comes in, and start by putting the values in at the middle of the array. Potential for moving blocks of the array (or indecii/link list) when bounds reached. Basically filling from the middle may save time. However needs to keep track of current lowest and highest filled positions, which is still only byte information.

That can be O(n). Just write your own. I assume the Keil beast doesn't support real C, since qsort is a part of the library. It lives in stdlib.h.

If you only want the median you don't have to store 64 elements. You only need to keep the lowest (or highest) 32 (or 31 depending on your definition of the median of an even number of elements).

Store the first 32 (or 31) conversions in an array. The next 32 (or 33) conversions search the array for the highest value and replace it with the current conversion if it is lower. At the end the highest value in the array is the median.

There is approximately 10 microsec between conversions - say 100 assembler instructions

Thanks,

I will try the Wirth algorithm and see how long it takes!

Sounds like a good idea. I will try the brute force kth_element approach first and if (or when) it takes too long this is certainly a worthwhile approach. It seems that for a small array a shell or bubble sort may be faster than a quicksort anyway. Your idea should utilize some of the wasted time while the conversions are proceeding.

Thanks, Arthur

I guess they omitted it because it is normally recursive and this doesn't suit the 8051 except perhaps with the LARGE model.

An interesting idea. I will certainly pursue this if my shellsort & kth element algorithms run out of time.

Thanks, Arthur

... snip ...

I don't believe you can sort during input, since your input is an external and you need to keep an input queue. If you use a sort you will have to copy the queue to a sortable array. See Sedgewicks "Algorithms" for a quick modification of quicksort for median extraction. I don't know if you have to keep track during the initial build-up of the queue. Bubble sort is about the slowest means of processing.

... for a _hosted_ implementation of C, that is. But not for a freestanding one, which a lot of embedded work obviously is. Keil does support as much "real" C as a 8051 can usefully handle, but they know better than to try to offer a full, hosted implementation.

Try an Insertion Sort Then you can make use of the ADC Conversion Time

Interesting observation NoSpam, sounds correct.

Finding the max would be O(N/2xN/2) not bad It could be that finding the max could be tightly coded via inline coding with constant indexes for the compare operations from the array. The data sheet said that 70% of the instructions execute in 1-2 clock cycles

Nice post IMHO.

Newman

It doesn't need to be recursive. One can simply stack one branch's indices and work the other side. The stack can be implemented without relying upon recursive calls, which is the real reason recursion is used in qsort -- as a handy, but expensive means of stacking a branch's span.

Jon