88 подписчиков

5 алгоритмов сортировки массивов в Arduino

21 марта 202021 мар 2020

715

5 мин

Оглавление

Подготовка и оборудование
Ардуино
Алгоритм замера времени работы кода

Алгоритмы, на самом деле не только для ардуино, но и для всех проектов работающих на С/Wiring, да и вообще для любого языка при желании можно адаптировать. В планах провести аналогичный эксперимент на Raspberry Pi и посмотреть, как разные версии этого робомозга воспримут задачу.

Подготовка и оборудование

Для работы с алгоритмами нам понадобятся 3 сущности:

- Любой компьютер или ноутбук с USB:
- Arduino UNO, можно с LCD шилдом;
- Алгоритм замера времени;
- Алгоритмы сортировки (пока для 5 штук, позже расширим список).

Ардуино

Самая простая часть эксперимента, подойдёт любая, главное, что бы работала и было удобно работать с ней

В зависимости от модели результаты замеров будут немного отличаться.

Для примера сортировать будем массив из 10 элементов, заполненный случайными числами из показаний аналогового порта:

int sensArr[10];
void FillArray() {
// считываем показания датчиков в массив
for (int i = 0; i < 10; ++i) {
sensArr[i] = analogRead(A1);
delay(100);
}
}

Алгоритм замера времени работы кода

Для корректного замера воспользуемся следующим алгоритмом. алгоритм работает наиболее точный результат, т.к. обращается напрямую к регистрам контроллера.

unsigned int timerValue; // значение таймера

void setup() {
Serial.begin(115200); //добавим возможность вывода в монитор порта
// установки таймера 1
TCCR1A = 0;
TCCR1B = 0;
}
void loop() {
noInterrupts(); // запрет прерываний
TCNT1H = 0; // сброс таймера
TCNT1L = 0;
TCCR1B = 1; // разрешение работы таймера

// ---------- исследуемый программный блок ---------

Serial.print("Hello world");

// вставляем сюда исследуемые функции

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

TCCR1B = 0; // остановка таймера
timerValue = (unsigned int)TCNT1L | ((unsigned int)TCNT1H << 8); // чтение таймера
interrupts(); // разрешение прерываний
// вывод результатов на компьютер
Serial.print( (float)(timerValue - 2) * 0.0625);
Serial.println(" mks");
delay(500);
}

При желании можно добавить вывод на экран LCD-шилда. Делается это буквально парой строчек кода из стандартных примеров библиотеки LiquidCrystal.

Функции алгоритмов сортировки и результаты их работы

Сортировка расчёской

349.38 mks на сортировку массива из 10 чисел

Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.

Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1,247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1,247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.

Проблема оказались в работе с дробными числами и их обработка. Ардуино не охотно их обрабатывала и результаты оказались крайне плохими:

void CombSort() {
const double factor = 1.247; // Фактор уменьшения
int stepIter = maxVal - 1;
while (stepIter >= 1) {
for (int i = 0; i + stepIter < maxVal; ++i) {
if (sensArr[i] > sensArr[i + stepIter]) {
int temp = sensArr[i];
sensArr[i] = sensArr[i + stepIter];
sensArr[i + stepIter] = temp;
}
}
stepIter /= factor;
}
}

Пузырьковая сортировка

90.62 mks на сортировку массива из 10 чисел

При данной сортировке нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.

На нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.

На ардуино она реализуется самым простым способом и является самой простой для реализации:

void BubbleSort() {
for (int j = 0; j + 1 < maxVal; ++j) {
for (int i = 0; i + 1 < maxVal - j; ++i) {
if ( sensArr[i] > sensArr[i + 1]) {
int temp = sensArr[i];
sensArr[i] = sensArr[i + 1];
sensArr[i + 1] = temp;
}
}
}
}

Сортировка выбором

81.31 mks на сортировку массива из 10 чисел

Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.

Запись алгоритма несколько длиннее, однако прирост в скорости реализации уже на лицо:

void SelectionSort() {
for (int j = 0; j < maxVal; ++j) {
int temp = sensArr[j];
int ind = j;
for (int i = j + 1; i < maxVal; ++i) {
if (temp > sensArr[i]) {
temp = sensArr[i];
ind = i;
}
}
sensArr[ind] = sensArr[j];
sensArr[j] = temp;
}
}

Сортировка перемешиванием (шейкерная сортировка)

80.31 mks на сортировку массива из 10 чисел

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.

Простейшая модернизация пузырькового алгоритма, но еще более эффективная:

void MixerSort() {
int left = 0;
int right = maxVal - 1;
while (left <= right) {
for (int i = right; i > left; --i) {
if (sensArr[i - 1] > sensArr[i]) {
int temp = sensArr[i];
sensArr[i] = sensArr[i - 1];
sensArr[i - 1] = temp;
}
} ++left;
for (int i = left; i < right; ++i) {
if (sensArr[i] > sensArr[i + 1]) {
int temp = sensArr[i];
sensArr[i] = sensArr[i + 1];
sensArr[i + 1] = temp;
}
}
--right;
}
}

Сортировка вставками

68.25 mks на сортировку массива из 10 чисел

При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.

На данный момент самый эффективный алгоритм из исследованных: