Re: Median algorithm for 8051

Arthur Richards wrote:
"Paul Carpenter" <paul$@pcserviceselectronics.co.uk> wrote:
"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.

.... snip ...

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.

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.

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.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
<http://kadaitcha.cx/vista/dogsbreakfast/index.html>
cbfalconer at maineline dot net



--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: Bubble Sort in C
    ... To sort an array using Bubble Sort algorithm ... cycles by optimizing the code, but an optimized bubble sort is still a ...
    (comp.lang.c)
  • Re: Bubble Sort in C
    ... To sort an array using Bubble Sort algorithm ... cycles by optimizing the code, but an optimized bubble sort is still a ...
    (comp.lang.c)
  • Re: Bubble Sort in C
    ... To sort an array using Bubble Sort algorithm ... cycles by optimizing the code, but an optimized bubble sort is still a ...
    (comp.lang.c)
  • Re: Help understanding O()?
    ... > This algorithm is an O? ... Some array sorting algorithms tend to be relatively immune ... Bubble sort and insertionsort are both Oworst case ... Average case for bubblesort and insertionsort is also O. ...
    (comp.programming)
  • Re: Alghoritm: how to detect % of chars. bad
    ... Make a queue 10 long, put your input into the queue ... So I wanted to make an algorithm which could work without ... any queue, array or stuff. ... Pavel. ...
    (comp.programming)