Qsort alternative

[avatarengineer]

I often need to sort analog samplings for use in a median filter.
The "qsort" command has me worried,
I'm not fond of pointers and I rarely need to sort characters.

The following code snippet is what I like to use for sorting a stream
of data from the ADC (usually 10bits types or more).
A further routine (not shown) takes the inner 3 or more values and gets an average (mean).
This eliminates hi and lo values that might be considered noise.
Doing this on each analog sample, loading the array and shifting out
the oldest value allows a rolling mean to be calculated.

Often used is a "bubblesort", however that seems much slower than
the "Shell-Metzner" method (as used by the CCS qsort).

Any comments from the forum? let me know if I'm smokin' dope.

[Ttelmah]

There is a fundamental flaw in what you are doing. With an array size of 10, you have the three values you take, plus an _odd_ number of other values. Your array size must be _odd_ for the central value, and the value each side, to be used for a median filter....

Have you searched the forum?. PCM_programmer, many years ago, posted a generic median filter (based on taking the central value from a sorted array), that would be quite easy to modify to use three values.

[jeremiah]

Just for portability OCD I would change:

[temtronic]

Also consider the source. Getting reliable, consistant, accurate 10,12 16 bit data from an analog source needs a LOT of careful design/build techniques.

No 'fancy' algorithm can compensate for faulty data. Simple test, read and display the data over several hours. If the sensor source is stable the displayed data should be +-1 bit. If not, you'll have to track down the interference and eliminate it.

Jay

[PCM programmer]

Here is the code that Ttelmah referred to. It also uses Insertion sort.
http://www.ccsinfo.com/forum/viewtopic.php?t=3462&start=1

[avatarengineer]

@Ttelmah; Using odd or even array size is not a requirement for median filtering, just an old convention as to my understanding.
Whether average values are centered in an array is not germane once it's sorted as the point in time is lost and overall delay is constant regardless of offset. Typically, I'll have an array of 100 items and track the average of only a few centered with an offset that is biased for fewer or larger outliers at the high or low side depending on the trajectory.


Otherwise, I was looking for help on the code.
This is a new routine (with minimal pointers) I just tried
and with any array size 9, 11, 23, 45... I require to run this twice before a full sort occurs.
Something in the While loops is not right and I've become blind to it.

[avatarengineer]

The actual version is 32bit signed values for use with a LTC ADC 29bits.
But keep to the simple version for conversation.

...and OCD is OK.

[PCM programmer]

[Ttelmah]

[RF_Developer]

I think that to a great extent this is a case of making a mountain out of a molehill. Sorting ten integers is, in computing terms, regarded as a trivial case. There's not a lot of point worrying much, if at all, about efficiency and speed of processing. The overhead involved with more complex, but algorithmically more efficient searches can easily be greater than any gains.

The more complex methods begin to give real gains only with significantly more data points, and more complex data such as records rather than single, simple data points. Imagine the work required to sort a telephone directory, which has telephone number, name and address, by number rather than by name.

Pointers are a very effective programming technique, and make complex data structures, and easily traversilble and sortable structures, possible. There's nothing inherently wrong or frightening about them. But in C especially, they do need careful progamming and testing. Such care and careful testing should, of course, be done for all programming tasks.

The use of pointers for sortable lists really scores when the pointer is significantly smaller and easier to manipulate than the data itself. Simple int8 data is smaller and simpler to move around that those pesky pointers, so making pointer-based data structures of int8s inefficient: its far easier and quicker to move the data than to change the pointers. Think, though, about that telephone book data. There's much more data in a record - number, maybe ten or more digits, name, could be twenty or more characters, address, say another forty - than a single sixteen or thirty two bit pointer. So for telephone data sorting, pointers are a no brainer.

Pointer based sorts are also good for data you already have in a data structure. If you are collecting data sample by sample as you go along, as with an ADC, a simple linear buffer is often all you need, and anything more is overkill and more importantly, overhead.

I do some so-called "olympic" averaging on some ADC data. It's not especially good with pure randomly noisy data, but it is very good with data corrupted by spikes, such as ADC readings of voltages from a SMPS. For that I take 2n + 2 samples, e.g. 10, 18, etc. - a straight binary multiple of samples is actually more awkward - adding them and recording the highest and lowest as I sample. When I have the required number of samples I subtract the lowest and highest and divide by 2n, which is a simple divide by a binary multiple, or for integers, a shift which the CCS compiler optimises for you. On PICs it would work for many more samples, even with 12 bit ADC data, which I often use; accumulating the sum in an unsigned int16. I only convert to engineering units, which may involve float arithmethic, but I'll do in integers if I can, once I have a value I need to save or present to a user. Even then I'll nearly alwas store that internally in integer form, for example voltages in millivolts or tens of millvolts.

EDIT: Sorry, I see that Ttelmah is proposing the same form of processing. I just described it in words.

[Ttelmah]

Yes, and we both get to the same final conclusion:

"Quick, rejects 'spike' noise well, and is small/simple to code."


It is a very good approach for anything involving spike noise.

It also though illustrates the importance of 'know your noise'.
Choosing the wrong filter can/will involve unnecessary processing, and may gain you nothing. For instance, if the noise is synchronous to your sampling, or involves longer bursts, 'things change'.