データを配列に蓄積し、処理する際にソートする必要がある際、様々なソート方法がある。昔から簡単かつ高速にソートする手法としては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: }