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!
- 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%2...programmierung

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!

// 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

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