Четыре тысячи девятьсот пятьдесят сравнений нужно, чтобы упорядочить сто заявок пузырьком. Вставки справятся вдвое быстрее, а с одной новой заявкой – в двадцать пять раз. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует оба алгоритма тремя нотациями, сравнивает их и выбирает лучшую.
Рис. 1. Пузырёк гоняет пары соседей, пока в проходе случаются обмены
В одной из команд, с которыми довелось сотрудничать, заявки заказчиков на доработки распределяли на исполнителей в порядке живой очереди. Стоило важному или скандальному клиенту потребовать ускорения, начиналась чехарда перестановок, которую ненавидели все. По сути это ручная сортировка – самая дорогая из возможных.
Короткий ответ: пузырёк – самый понятный и самый медленный способ навести порядок в списке. Вставки так же просты, но на живой очереди справляются в десятки раз быстрее. Рисовать оба алгоритма руководителю удобнее всего структограммой Насси – Шнейдермана, а разработчику стоит приложить псевдокод.
Как устроен пузырёк?
Пузырьковая сортировка – способ упорядочить список, сравнивая только соседние строки. Алгоритм идёт сверху вниз, и если верхняя заявка должна стоять ниже, их переставляют. За проход самая поздняя заявка «всплывает» в конец, как пузырёк в газировке, – отсюда название метода.
Затем проход повторяют без последней позиции: она уже на месте. Каждый следующий проход короче на одну пару. Работа заканчивается, когда за целый проход не случилось ни одного обмена, – это досрочный выход, который на рисунке ведёт прямо к концу. Без него алгоритм отработал бы все проходы даже на готовом списке.
По ГОСТ 19.701 такая логика превращается в два вложенных цикла. Шестиугольник «Проход» считает круги, шестиугольник «Пара» перебирает соседей, ромб решает, менять ли их местами. Схема точная, но занимает целую страницу ради семи строк смысла.
Как пузырёк упорядочит пять заявок?
В сервисной компании «Кедр», с которой читатель встретится во всех статьях сборника, сорок инженеров и очередь заявок. Возьмём пять из них: до срока осталось семь, три, девять, один и пять дней. Диспетчер выстраивает их от самой срочной, чтобы бригады брали работу сверху.
Рис. 2. Каждый проход пузырька ставит на место ещё одну заявку
Первый проход делает четыре сравнения и три обмена, и девятидневная заявка уходит в конец. Второй короче на одну пару. К четвёртому проходу обменов не остаётся, но одно сравнение нужно, чтобы в этом убедиться. Итог – десять сравнений и шесть обменов ради пяти строк.
Чем вставки лучше пузырька?
Сортировка вставками – способ, которым игрок раскладывает карты в руке: берёт следующую карту и вставляет её среди уже упорядоченных. Начало списка всегда готово, а каждая новая заявка ищет в нём место, сравниваясь с соседями справа налево.
Рис. 3. Вставки: внешний цикл выбирает заявку, внутренний сдвигает более поздние
Схема по ГОСТ здесь чуть сложнее: цикл «пока» – не перебор с известным числом шагов, он останавливается, как только нашлась заявка раньше ключа. Поэтому его рисуют ромбом с возвратной стрелкой, а не шестиугольником.
На тех же пяти заявках вставки обходятся восемью сравнениями вместо десяти. Сдвигов столько же, сколько было обменов, – шесть: ровно столько пар стояло в неверном порядке. Экономия идёт на сравнениях: заявка «9» сразу видит, что уже на месте.
Рис. 4. Вставки упорядочивают те же пять заявок за восемь сравнений
Сколько стоит каждый метод?
На случайной сотне заявок пузырёк делает в среднем около 4’900 сравнений, а вставки – около 2’500. При десяти секундах на сравнение это 13,5 и 7 часов ручной работы. Худший случай, когда список выстроен наоборот, у обоих одинаков – 4’950 сравнений.
Разница взрывается на почти готовом списке. Сотня заявок упорядочена, и в конец добавили одну срочную. Вставки поставят её на место за 149 сравнений, пузырёк – за 3’775: заявка поднимается лишь на позицию за проход. Программисты называют такие медленно ползущие к началу списка элементы черепахами.
Рис. 5. Одна новая заявка в конце: вставки в двадцать пять раз дешевле пузырька
Встречал и другую крайность. Заявку, втиснутую в свёрстанный план, отдавали сверхурочной команде, чтобы не перекраивать всё полотно задач. Сотрудники быстро научились изображать необычайную занятость, лишь бы их не догрузили. Понятное всем правило вставки снимает этот театр: срочная заявка встаёт в очередь по сроку.
Сортировка слиянием, о которой пойдёт речь в следующей статье сборника, упорядочит любые сто заявок не более чем за 573 сравнения. Но для очереди, куда заявки приходят по одной, вставки остаются естественным методом: диспетчер и так делает именно их.
Какими нотациями рисовать сортировку?
ГОСТ 19.701 – стандарт схем алгоритмов 1990 года: овалы, прямоугольники, ромбы и шестиугольники циклов, соединённые стрелками. Его предпочитают авторы регламентов и аудиторы: на каждую фигуру есть пункт стандарта. Цена строгости – размер: два коротких алгоритма заняли два больших рисунка.
Структограмма Насси – Шнейдермана – схема без стрелок: цикл изображается рамкой, а всё повторяемое вложено внутрь. Её придумали Айзек Насси и Бен Шнейдерман в 1973 году.
Её любят преподаватели программирования: вложенность видна с первого взгляда, а клубок из стрелок нарисовать невозможно. У обоих алгоритмов по две рамки цикла, одна внутри другой, и сразу видно, какие шаги идут по кругу.
Рис. 6. Структограмма показывает вложенность циклов рамками без единой стрелки
Выбор нотации – не вопрос вкуса. Бизнес часто рисует самый логичный путь и отмахивается от «незначительных» отклонений. В жизни они доходят до четверти всех случаев и проходят втрое дольше типового маршрута, то есть съедают половину времени. Структограмма требует заполнить обе ветки развилки, хотя бы прочерком, и этим вытаскивает аппендиксы на свет.
Псевдокод – запись алгоритма словами с отступами, как программа, но без синтаксиса конкретного языка. Отступ здесь играет роль рамки структограммы.
Им пользуются разработчики и аналитики: текст легко поправить, сравнить версии и вставить в задачу. Нейросеть прочтёт его без ошибок, в отличие от рисунка.
Рис. 7. Псевдокод укладывает каждый алгоритм в семь строк
Какая нотация лучше?
Лучшая нотация для сортировки – структограмма Насси – Шнейдермана: в оценке по четырём вопросам она набрала 22 балла из 25. Решающим стал первый вопрос: поймёт ли руководитель схему за минуту. Вес этого вопроса удвоен, ведь сборник написан для руководителя.
Рис. 8. Структограмма выигрывает у ГОСТ и на балл опережает псевдокод
Псевдокод отстал всего на балл и выиграл в двух вопросах – для разработчика и для ИИ. Отсюда рабочая связка: структограмма – для обсуждения с командой, псевдокод – приложением к задаче. ГОСТ остаётся для регламентов, где важна ссылка на стандарт.
Когда какой метод уместен?
Пузырёк оправдан на списке до десяти строк и в обучении: объяснить его можно за минуту. Он быстро справляется и с почти готовым списком, если беспорядок в начале: поздняя заявка «всплывает» за один проход. Такие элементы программисты называют кроликами.
Вставки подходят для короткого, почти готового списка и живой очереди, куда заявки приходят по одной. Сотни и тысячи строк лучше отдать электронной таблице или системе учёта.
Что сделать руководителю?
Хватит четырёх шагов:
- Посчитайте, сколько раз в неделю сотрудники вручную переставляют строки в реестрах, графиках и очередях.
- Договоритесь о ключе сортировки заранее: срок, сумма или приоритет клиента.
- Новую заявку ставьте на место сразу, а не пересобирайте очередь на планёрке.
- Логику для команды рисуйте структограммой, а разработчику давайте псевдокод.
Что запомнить?
- пузырёк сравнивает соседей и меняет их местами
- вставки ставят каждую заявку на место в готовом начале списка
- на случайном списке вставки вдвое дешевле пузырька
- одну срочную заявку вставки пристроят в двадцать пять раз быстрее
- сортировку рисуют структограммой, а разработчику дают псевдокод.