Bubble sort.

Hi all,

I'm wondering how would I be able to create a running median using the bubble sort algorithm without using any builtin libraries. I'm not sure how to do this as I'm new to Arduino and would appreciate any advice.

Use your favorite search engine, together with the search terms "arduino bubble sort" to discover many working examples.

running median using the bubble sort algorithm

Why are you using a sort in order to get an average?

Mark

Why are you using a sort in order to get an average?

Look up "median filter" to see why. Such a filter is very useful, and robust against large outliers in the raw data.

PS: The OP did not use the word "average".

Average is not the same as median. Median is the middle value, usually of an odd number of values. In general, the middle value is not known unless a sort is performed.

vaj4088:
Average is not the same as median.

Actually, the median is just one of three averages, where an average is just one of many measures of central tendency. What you meant to say was "Average is not the same as mean". Yes we loosely use the word "average" to be the "mean", but mode, median and mean are all averages.

See here for example:

There are three main types of average:

mean
mode
median

JJJ12:
Hi all,

I'm wondering how would I be able to create a running median using the bubble sort algorithm without using any builtin libraries. I'm not sure how to do this as I'm new to Arduino and would appreciate any advice.

.I don't believe any of the built-in libraries includes a bubble sort, so I think you're safe.

If you are performing a RUNNING median, you may not need a bubble sort at all. Presumably, your median has a fixed maximum size. A running calculation implies that your data arrives sequentially (samples?).

If you have reached the maximum size, delete the oldest value.
Insert the new value in its proper place.
The median is the middle value (which is usually easy to locate and is really easy once you have reached maximum size).

Moving data in an array seems to be required. Bubble sort seems to be an unnecessary requirement. Is this homework?

Insert the new value in its proper place

Can't do that without sorting.

I agree that a median requires a sort. However, if the values arrive sequentially, a bubble sort is overkill and a simple "insert in the correct place" using a loop and something like >= would be sufficient.

Once the correct place is found, another loop (possibly inside a function) will be needed to move the elements of an array. A similar loop or function will be needed to close things up when the oldest value is removed. An optimization is possible if the new value goes precisely where the oldest value was located.

This is similar to a bubble sort but not the same, and simpler I believe. No swaps needed.

Please write and post your more efficient algorithm!

If you want to sort as items come in, you'd use a tree, not an array.
More memory, but much quicker to reconfigure.

Some interesting discussion and code at reference implementation - How to build a median filter function? - Signal Processing Stack Exchange.

Benchmarking C++ code here.

Thanks!

I notice that the choice of fastest algorithm depends upon the median size and the type of variables (int, float, etc.) which the OP has not described to us.

I also see that there may be a tradeoff between speed and size.

vaj4088:
I agree that a median requires a sort. However, if the values arrive sequentially, a bubble sort is overkill and a simple "insert in the correct place" using a loop and something like >= would be sufficient.
...
This is similar to a bubble sort but not the same, and simpler I believe. No swaps needed.

Seems to me it is a bubble sort, but since you are doing nothing more than adding one element each time, then the single bubble pass is performed on the fly.

No swaps are required so it is not a bubble sort as I know it. It is more like an insertion sort, with the insertion being a list of a single value.

Yeah, adding a new number to an already sorted list is much easier than a full sort, a single bubbly number should work fine, iirc what the bubbles are supposed to be... If the number of elements is reasonably small, it’s probably not worth more than just shifting an array around (anything you’d gain in insertion speed with a tree would probably be lost when it’s time and to find the middle element.)