_size=255 and bubble sort

[Khalinda]

Whatever the problem, bubble sort is usually not the answer. Hopefully I haven't done anything wrong, but I bench marked an int16_t version of RunningMedian on an Arduino Uno., and I compared bubble sort (with early termination) to insert sort and quick sort. With random data, _size=255 and no oversampling, insert sort was almost 30 times faster than bubble sort and almost 5 times faster than quick sort. (With significant oversampling, it is likely that quick sort is the better choice.)

void RunningMedian::sort()
{
    uint8_t i;                          // loop index
    uint8_t j;                          // loop index
    uint8_t t;                          // swap buffer

    for(i=1;i<_cnt;i++)
    {
        t=_p[i];
        for(j=i;j>=1&&_ar[t]<_ar[_p[j-1]];j--)
            _p[j]=_p[j-1];
        _p[j]=t;
    }
    _sorted=true;
}

[RobTillaart]

Hi Khalinda,

Thanks for your post, I am aware of the problem.,

In previous versions of RunningMedian, bubblesort was fast enough as the maximum set was at most 19 elements. With the change that the internal dataset may become up to 250 something bubblesort is indeed not the way to go.

I did not taken time to investigate which other sort is best it is still on my TODO list.

The first issue is that one can sort on two moments

1. when an element is added
2. when the median is requested (current choice)

The second issue is that when the internal buffer is full you want to know which value is removed. As you also know which value is added you need only to shift elements in between, either up or down.

simplified example:

assume remove 16 and add 11

before add               [  1  3  4  5  7   8  9  10  12  14  15  16  17  18  20 ]
remove 16                [  1  3  4  5  7   8  9  10  12  14  15  __  17  18  20 ]
shift until 11 fits in   [  1  3  4  5  7   8  9  10  __  12  14  15  17  18  20 ]
add 11 done              [  1  3  4  5  7   8  9  10  11  12  14  15  17  18  20 ]

As the shift can go upwards an downwards a bidirectional insertion sort is probably the way to go IF you do the sorting after each addition. IF you do the sorting last minute it depends on how much new values are added. Is this low then the array is nearly sorted, but if there are many one can consider it unsorted and quicksort might be the thing.

Feel free to create a pull request that solves the issue.

[RobTillaart]

Investigation done, insertionSort is way faster and compared to quicksort (at least the recursive one) more memory friendly.

Solved in c3de2e1 Release 0.3.2