Re: Median algorithm for 8051

On Wednesday, in article
<f198ko$6r3$1@xxxxxxxxxxxxxxxxxxxxxxxxxx>
fake@xxxxxxxxxxxxxx "Arthur Richards" wrote:

I need to find the median of a 64 element unsigned int array. I would use
qsort() but my Keil compiler doesn't support it. I'm using the small model
so the algorithm should be non-recursive. Just to make it interesting I have
less than 500 microseconds to do the calc on a 25 MHz Silabs C8051F410.

The data is obtained sequentially from a ADC so that it may be possible to
do some of the calculation while the ADC is still working.

I would welcome any suggestions/code etc.

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.

--
Paul Carpenter | paul@xxxxxxxxxxxxxxxxxxxxxxxxxxx
<http://www.pcserviceselectronics.co.uk/> PC Services
<http://www.gnuh8.org.uk/> GNU H8 & mailing list info
<http://www.badweb.org.uk/> For those web sites you hate

.

Relevant Pages

  • Re: Median algorithm for 8051
    ... fake@xxxxxxxxxxxxxx "Arthur Richards" wrote: ... The data is obtained sequentially from a ADC so that it may be possible to ... With only 64 items you could possibly just use a bubble sort as each value ... and start by putting the values in at the middle of the array. ...
    (comp.arch.embedded)
  • Re: "Sorting" assignment
    ... If the array is already sorted, this means that you end up ... rather slower than a bubble sort. ...     int intLeft, ... Why don't you declare intExchange at this scope? ...
    (comp.programming)
  • Re: Rexxtacy
    ... It's not any more complicated than bubble sort and is, well, quicker. ... Store pointers to the array items in a separate array, ...
    (comp.os.os2.programmer.misc)
  • Re: Median algorithm for 8051
    ... using the small model so the algorithm should be non-recursive. ... With only 64 items you could possibly just use a bubble sort as ... Potential for moving blocks of the array (or ... you will have to copy the queue to a sortable array. ...
    (comp.arch.embedded)
  • Re: [C++] Binary Search Confusion
    ... > all the information (bubble sort) once all the information is entered. ... then the array which stores those numbers is bubble sorted (in ... way we have the exact same program with the exact same numbers as you have. ...
    (alt.comp.lang.learn.c-cpp)