データを配列に蓄積し、処理する際にソートする必要がある際、様々なソート方法がある。昔から簡単かつ高速にソートする手法としてはquicksortがある。

メモリ消費が少なく、貧弱なArduinoでもquicksortで高速に並び替えが出来る。以下、100個のランダムな数字の配列を作成し、クイックソートするサンプル。

参考サイト：
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/

#define NUM_DATA	100
typedef struct SOMEDATA {
	int val;
	float time;
};
SOMEDATA data[NUM_DATA];
int num_data;

//クイックソート
int pivot(int i, int j) {
	int k = i + 1;
	while (k <= j && data[i].val == data[k].val) k++;
	if (k > j) return -1;
	if (data[i].val >= data[k].val) return i;
	return k;
}
int partition(int i, int j, int x) {
	int l = i, r = j;
	while (l <= r) {
		while (l <= j && data[l].val < x)  l++;
		while (r >= i && data[r].val >= x) r--;
		if (l > r) break;
		float t = data[l].time;
		int val = data[l].val;
		data[l].time = data[r].time;
		data[l].val = data[r].val;
		data[r].time = t;
		data[r].val = val;
		l++; r--;
	}
	return l;
}
void quickSort(int i, int j) {
	if (i == j) return;
	int p = pivot(i, j);
	if (p != -1) {
		int k = partition(i, j, data[p].val);
		quickSort(i, k - 1);
		quickSort(k, j);
	}
}
void sort() {
	quickSort(0, num_data - 1);
}

void setup() {
	Serial.begin(9600);
	randomSeed(analogRead(0));

	for (int i=0;i<NUM_DATA;i++){
		data[i].val = random(500);
		data[i].time = millis();
		Serial.println(data[i].val);
	}
	num_data = NUM_DATA;
	Serial.println("Sorting...");
	sort();

	for (int i=0;i<NUM_DATA;i++){
		Serial.println(data[i].val);
	}
}

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

}