Bubblesort: für beliebige Datentypen nur 1 Algorithmus ?

[HaWe]

hallo,
für einfache Sortierzwecke kurzer Arrays verwende ich gern den Bubblesort (ansonsten Shellsort oder Quicksort).
Nun brauche ich bislang immer 2 getrennte Funktionen, eine für int32, eine für double.
Wie macht man es "schöner" mit C oder C++, dass man für beliebige (!) Datentypen im selben (!) Programm nur 1 Algorithmus braucht, evtl. auch für char*, int16_t* und float* ? (Ich arbeite mit der Arduino IDE auf 8-bit AVR und 32-bit ARM/ESP-Plattformen.)



void bubblesortn(int32_t *array, int length) {
int32_t tmp;

for (int i=0; i<length-1; i++) {
for (int j=0; j<length-i-1; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}

void bubblesortd(double *array, int length) {
double tmp;

for (int i=0; i<length-1; i++) {
for (int j=0; j<length-i-1; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}



Erste "Ideen" wären mit overloading oder mit void *array, ersteres habe ich aber noch nie gemacht und letzteres könnte zu kompliziert in der Programmierung werden, fürchte ich, etwa z.B.
void bubblesort (void *array , size_a length, size_a varsize, f_compare) // wie bei Quicksort-Implementierung
- nur die zusätzlich nötigen f_compare() Funktionen für alle Var-Typen machen es dann unterm Strich sicher auch nicht einfacher....

Auch von "Prototypen" habe ich mal was gelesen - wäre das besser und einfacher?

- - - Aktualisiert - - -

update:

habe mal ganz ohne Hoffnung, dass es klappen könnte, beide Funktionen mit unterschiedlichen Datentypen unter demselben Funktionsnamen deklariert -
überraschenderweise meckert der Compiler gar nicht und er scheint das völlig automatisch zu overloaden... das wär ja ungeahnt simpel...!


void bubblesort(int32_t *array, int length) {
int32_t tmp;

for (int i=0; i<length-1; i++) {
for (int j=0; j<length-i-1; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}

void bubblesort(double *array, int length) {
double tmp;

for (int i=0; i<length-1; i++) {
for (int j=0; j<length-i-1; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}

[Mxt]

Wenn eine zweite Datei erlaubt ist, die Arduino IDE ist da sonst etwas eigen, braucht man die Funktion nicht zweimal hinschreiben.

Beispiel, getestet mit Arduino 1.8.5 und Arduino Uno:

Datei "TemplateTest.h"


template<typename T>
void bubblesort(T *array, int length) {
T tmp;

for (int i=0; i<length-1; i++) {
for (int j=0; j<length-i-1; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}


Sketch "TemplateTest.ino"


#include "TemplateTest.h"

int Test1[] = { 4, 2, 9 };
double Test2[] = { 8.2, 7.1, 5.4, 9.6, 1.3 };

void setup() {
// put your setup code here, to run once:
Serial.begin(9600);

bubblesort(Test1, 3);

for(auto& n : Test1) {
Serial.println(n);
}

Serial.println();
bubblesort(Test2, 5);

for(auto& n : Test2) {
Serial.println(n);
}
}

void loop() {
// put your main code here, to run repeatedly:

}


Die sortierte Ausgabe sieht man im seriellen Monitor.

[HaWe]

klasse, danke, das ist ja noch viel schicker! 8)
- und wow, die Ausgabe ist ja auch sehr "sophisticated" ;)

- - - Aktualisiert - - -

Anschlussfrage...: ;)

Ich verwende den bubblesort z.B. für versch. Medianfilter:
kann man das ähnlich schick ebenfalls "overloaden" ?


// FiFo-Arrays für Median, nur für Gebrauch von FiFo-push und Medianfilter

static int16_t fifoi[8][3];
static int32_t fifon[8][3];
static double fifod[8][3];

//---------------------------------------------------------
// FiFo-push

void fifopush(int16_t col, int16_t _new) {
fifoi[col][2] = fifoi[col][1];
fifoi[col][1] = fifoi[col][0];
fifoi[col][0] = _new;
}

void fifopush(int16_t col, int32_t _new) {
fifon[col][2] = fifon[col][1];
fifon[col][1] = fifon[col][0];
fifon[col][0] = _new;
}

void fifopush(int16_t col, double _new) {
fifod[col][2] = fifod[col][1];
fifod[col][1] = fifod[col][0];
fifod[col][0] = _new;
}

//---------------------------------------------------------
// Medianfilter

int16_t medianOf3i(int col) {
int16_t temp[3];

memset ( temp, 0, 3 );
for ( int i = 0; i < 3; i++) temp[i] = fifoi[col][i];
bubblesort( temp, 3 );
return temp[1];
}

int32_t medianOf3n(int col) {
int32_t temp[3];

memset ( temp, 0, 3 );
for ( int i = 0; i < 3; i++) temp[i] = fifon[col][i];
bubblesort( temp, 3 );
return temp[1];
}

double medianOf3d(int col) {
double temp[3];

memset ( temp, 0, 3 );
for (int i = 0; i < 3; i++) temp[i] = fifod[col][i];
bubblesort( temp, 3 );
return temp[1];
}



Die Zuordnung von ggf. übergebenen Variablentypen auf die entspr. FiFo-Arrays fifoi[][], fifon[][] und fifod[][] muss dazu funktionieren; deren Namen sind aber nicht "öffentlich", sondern werden nur von Median- und FiFo-push-Funktionen "privat" verwendet.

[Mxt]

Also eigentlich ist das Prinzip bei Templates einfach. Man ersetzt die "beliebigen" Datentypen quasi durch Typvariablen. Das man die T usw. nennt ist nur eine Konvention.

Damit sollte man eigentlich aus den fifopush folgendes machen können (ungetestet)


template<typename T>
void fifopush(int16_t col, T _new) {


[Edit2]
Sorry, nein, jetzt sehe ich erst die unterschiedlichen Arrays. Die müsste man wohl zu Parametern befördern, sonst macht das keinen Sinn.

[Edit]
Die medianOf3 würden komplizierter, da werden ja abhängig vom Typ andere Arrays verwendet.

[HaWe]

kann man in den Funktionen selber die Art der übergebenen template<typename T> abfragen?
In der Art
if(T==double) ... tudies
else
if(T==int32_t) ... tudas
else
if(T==int16_t) ... tuanderes

[Mxt]

Zur Erläuterung der Edits:

Ja, man könnte Template Code schreiben in der Form "Wenn T ein int ist dann nimm dieses Array", aber das wird wohl nicht kürzer als die jetzigen Funktionen. Man bräuchte dafür std::enable_if (ab C++11) oder constexpr if (ab C++17).


Hier mal als Beispiel, die Arduino "map" Funktion, die beim Teensy in C++14 geschrieben ist:

// when the input number is an integer type, do all math as 32 bit signed long
template <class T, class A, class B, class C, class D>
long map(T _x, A _in_min, B _in_max, C _out_min, D _out_max, typename std::enable_if<std::is_integral<T>::value >::type* = 0)
{
long x = _x, in_min = _in_min, in_max = _in_max, out_min = _out_min, out_max = _out_max;
// Arduino's traditional algorithm
//return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
// st42's suggestion: https://github.com/arduino/Arduino/issues/2466#issuecomment-69873889
// more conversation:
// https://forum.pjrc.com/threads/44503-map()-function-improvements
if ((in_max - in_min) > (out_max - out_min)) {
return (x - in_min) * (out_max - out_min+1) / (in_max - in_min+1) + out_min;
} else {
return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
}
}
// when the input is a float or double, do all math using the input's type
template <class T, class A, class B, class C, class D>
T map(T x, A in_min, B in_max, C out_min, D out_max, typename std::enable_if<std::is_floating_point<T>::value >::type* = 0)
{
return (x - (T)in_min) * ((T)out_max - (T)out_min) / ((T)in_max - (T)in_min) + (T)out_min;
}

[HaWe]

aja, stimmt, sieht nicht einfacher aus ;)

[Mxt]

Man muss dabei bedenken, das sind Berechnungen die der Compiler zur Übersetzungszeit ausführen muss. Es handelt sich dabei um "Metaprogrammierung".
https://de.wikipedia.org/wiki/C%2B%2B-Metaprogrammierung

Der Knackpunkt in obigen Code ist aber eigentlich sichtbar, es handelt sich um diese zwei Stellen


long map( /* weggelassene Parameter */ , typename std::enable_if<std::is_integral<T> /* ... */)

T map(/* weggelassene Parameter */ , typename std::enable_if<std::is_floating_point<T>::value >/* ... */)


Zwei Funktionen namens map, die Parameter der ersten passen nur (enable_if) wenn T ein Integertyp ist (is_integral). Bei der zweiten muss T ein "floating_point" sein. Der Mechanismus der dann greift ist der gleiche wie bei zwei normalen Funktionen, die eine mit int die andere mit double Parameter.

[HaWe]

ja, danke, jetzt sehe ich auch das Prinzip! Interessant, was da alles so geht...!

[HaWe]

so, habe meine ardumath lib fertig, anscheinend zumindest ohne erkennbare Bugs!

Man kann einfach bubblesort für einen beliebigen Array nutzen,
dann medianofX mit Angabe von Var.-Nr und der Array-Tiefe (median of 3 oder median of 5 z.B.)
und schließlich auch medianNewOfX unter zusätzlicher Übergabe eines neuen Messwertes, der sodann erst in den FiFo Puffer eingespeist wird.

Edit:
Als Zugabe noch ein Shellsort und ein Lowpass-Filter mit beliebigem Variablentyp.

vlt kanns ja jemand brauchen - Bug Reports willkommen! 8)



// ardumath.h

#ifndef _ARDUMATH_H
#define _ARDUMATH_H


//---------------------------------------------------------
// Bubble Sort
//---------------------------------------------------------

template<typename VTYPE>
void bubblesort(VTYPE *array, int length) {
VTYPE tmp;

for (int i=0; i<length-1; i++) {
for (int j=0; j<length-i-1; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}


//---------------------------------------------------------
// Shell Sort
//---------------------------------------------------------

template<typename VTYPE>
void shellsort(VTYPE *array, int length) {
int i, j, increment;
VTYPE temp;

increment = length / 2;
while (increment > 0) {
for (i = increment; i < length; i++) {
j = i;
temp = array[i];
while ((j >= increment) && (array[j-increment] > temp)) {
array[j] = array[j - increment];
j = j - increment;
}
array[j] = temp;
}
if (increment == 2)
increment = 1;
else
increment = (unsigned int) (increment / 2.2);
}
}


//---------------------------------------------------------
// Median Filter
//---------------------------------------------------------

#define MEDMAX 5 // Median depth: 5 each (MEDMAX default)

// private FiFo Buffers: 8 variants, Median depth: 5 each (MEDMAX default)
static int16_t fifoi[8][MEDMAX];
static int32_t fifon[8][MEDMAX];
static double fifod[8][MEDMAX];



void fifopush(int16_t _new, int varnr) {
for (int i=MEDMAX-1; i>=1; i--) {
fifoi[varnr][i] = fifoi[varnr][i-1];
}
fifoi[varnr][0] = _new;
}

void fifopush(int32_t _new, int varnr) {
for (int i=MEDMAX-1; i>=1; i--) {
fifon[varnr][i] = fifon[varnr][i-1];
}
fifon[varnr][0] = _new;
}

void fifopush(double _new, int varnr) {
for (int i=MEDMAX-1; i>=1; i--) {
fifod[varnr][i] = fifod[varnr][i-1];
}
fifod[varnr][0] = _new;
}

//---------------------------------------------------------

int16_t medianOfi(int varnr, int depth) {
int16_t temp[depth];
for (int i=0; i<depth; i++) temp[i] = fifoi[varnr][i];
bubblesort( temp, depth );
return temp[depth/2];
}

int32_t medianOfn(int varnr, int depth) {
int32_t temp[depth];
for (int i=0; i<depth; i++) temp[i] = fifon[varnr][i];
bubblesort( temp, depth );
return temp[depth/2];
}

double medianOfd(int varnr, int depth) {
double temp[depth];
for (int i=0; i<depth; i++) temp[i] = fifod[varnr][i];
bubblesort( temp, depth );
return temp[depth/2];
}

//---------------------------------------------------------

int16_t medianNewOfi(int16_t _new, int varnr, int depth) {
fifopush(_new, varnr);
return medianOfi(varnr, depth);
}

int32_t medianNewOfn(int32_t _new, int varnr, int depth) {
fifopush(_new, varnr);
return medianOfn(varnr, depth);
}

double medianNewOfd(double _new, int varnr, int depth) {
fifopush(_new, varnr);
return medianOfd(varnr, depth);
}


//---------------------------------------------------------
// Tiefpass = lowpassFilter
//---------------------------------------------------------

template<typename VTYPE>
double lowpassFilt(VTYPE NewVal, VTYPE Avrg, double FF) {

return (double)(NewVal*FF + Avrg*(1.0-FF)) ;
}


//---------------------------------------------------------

#endif

//---------------------------------------------------------
//---------------------------------------------------------