Пузырьковая сортировка одного столбца кактусов в TFWR
Эта игра дает отличную возможность посмотреть, как работают разные алгоритмы сортировки. В этом посте разберем классическую сортировку пузырьком.
Вы можете проверить код на GitHub.
Посмотрим, как построен скрипт.
best_move - вспомогательная функция для nav. nav позволяет перемещать дрон в любые координаты на поле.
Дальше в скрипте я выставляю размер фермы 16, проверяю переход в точку (6, 6), обрабатываю почву, сажаю кактусы, а затем запускаю пузырьковую сортировку (строки 32-36).
Для меня здесь важно четко задать переменные и их физический смысл. Не хочу делать лишнюю работу и хочу корректно обрабатывать крайние случаи. Итак:
y_upper- последняя ячейка, до которой в текущем проходе нужно делать сравнения и обмены
Из этого следует, что y_upper идет от (n-1) до 1 включительно. Значит правильный диапазон: range(n-1, 0, -1).
Дальше все просто. Внутренний цикл идет от 0 до y_upper - 1, то есть range(y_upper). Для задачи удобна функция measure(): сравнение с верхней ячейкой просто
measure() > measure(North)
а обмен с верхней ячейкой -
swap(North)
Еще один интересный момент: карта на торе, поэтому в начале сортировки дрон «крутится» в одну сторону. Когда отсортировано больше половины столбца, он начинает ходить туда-сюда.