Алгоритмы сортировки данных
"Робот и Я"Привожу примеры нескольких способов сортировки массивов, с замерами времени выполнения, на основании которых можно проверить фундаментальную теорию алгоритмов
Алгоритмы сортировки
- Сортировка расчёской
- Пузырьковая сортировка
- Сортировка выбором
- Сортировка перемешиванием (шейкерная сортировка)
- Сортировка вставками
Подготовка и оборудование
Для работы с алгоритмами нам понадобятся:
- Любой компьютер или ноутбук с USB:
- Arduino UNO или контроллер с которым предстоит работать, можно с экраном для большей наглядности;
- Алгоритм измерения времени выполнения кода;
- Собственно алгоритмы сортировки.
Ардуино
В зависимости от модели контроллера, результаты замеров будут немного отличаться.
Для нашего исследования будем сортировать массив из 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.
Сортировка расчёской
Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.
Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 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;
}
}
Пузырьковая сортировка
При данной сортировке нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.
На нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.
На ардуино она реализуется самым простым способом и является самой простой для реализации:
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;
}
}
}
}
Сортировка выбором
Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.
Запись алгоритма несколько длиннее, однако прирост в скорости реализации уже на лицо:
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;
}
}
Сортировка перемешиванием (шейкерная сортировка)
Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.
Простейшая модернизация пузырькового алгоритма, но еще более эффективная:
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;
}
}
Сортировка вставками
При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.
На данный момент самый эффективный алгоритм из исследованных:
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;
}
}
Книги по алгоритмам
Полезные книги по теории и практике алгоритмов в программировании, найти можно в нашем телеграм канале:
- Теория алгоритмов
- Практические примеры на С++
- Практические примеры на Python