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