Re: Median algorithm for 8051


"Paul Carpenter" <paul$@pcserviceselectronics.co.uk> wrote in message
news:20070502.0916.328572snz@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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


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


.

Relevant Pages

  • Re: Median algorithm for 8051
    ... The data is obtained sequentially from a ADC so that it may be possible to ... link lists, but may end up using more data storage of byte size. ... 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: Make sense of Arrays after Transpose
    ... When I try to bubble sort this transposed array ... Function Transpose2DAs Variant ... Dim i As Long, j As Long ...
    (microsoft.public.excel.programming)