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