Как быстро упорядочить парк машин по наработке и найти нужную? Сортируй пузырьком, вставками и быстрой сортировкой по шагам и сравни, сколько операций уходит у каждой.
Наработку всех машин парка удобно держать в одном списке: часы = [6200, 7400, 5100, …]. К любой машине обращаются по номеру в квадратных скобках, и счет идет с нуля: часы[0] это первая машина. Чтобы составить очередь на ремонт, список сортируют. Самый простой способ, пузырек, сравнивает соседей и меняет их местами, но для большого парка он делает очень много сравнений. Быстрая сортировка делит список на части и справляется в разы быстрее. А в отсортированном списке нужную машину можно найти делением пополам, за несколько шагов вместо перебора всех.
Список, номер элемента и обмен двух ячеек: из этих трех приемов собраны все сортировки. Числа ниже берутся из опыта.
Как достать элемент?
Имя списка и номер в квадратных скобках. Номер может быть числом или выражением: часы[j + 1] это сосед справа. Если номер больше последнего, программа остановится с ошибкой.
Как поменять местами?
Справа сначала берутся оба старых значения, потом они раскладываются по ячейкам слева. Без такой записи понадобилась бы третья переменная, иначе одно число потеряется.
Сколько это стоит?
Пузырек сравнивает каждую пару: первый проход n − 1 сравнений, второй n − 2 и так далее. Быстрая сортировка делит список пополам около log₂n раз, и на каждом уровне просматривает все n элементов.
Справа программа из опыта на Python. Списки там пишутся так же, индексы тоже с нуля, а обмен a[i], a[j] = a[j], a[i] работает точно так же. Целочисленное деление // в двоичном поиске тоже из Python.
В настоящей работе сортировку не пишут руками: в Python есть sorted(часы) и часы.sort(), а в Excel кнопка «Сортировка». Внутри них стоит алгоритм порядка n · log n. Писать пузырек самому нужно, чтобы понять, откуда берется разница в скорости и почему программа, которая летала на 10 машинах, зависает на миллионе строк телеметрии.
Список машин сортируют по наработке или по сроку до ТО, и сверху оказываются те, кого нужно ставить в бокс первыми.
Номенклатура на десятки тысяч позиций хранится отсортированной по каталожному номеру, и поиск фильтра идет делением пополам, а не перебором.
Самосвал пишет данные каждую секунду: за месяц миллионы строк. Отсортировать их по времени пузырьком невозможно, нужны быстрые алгоритмы.
Чтобы найти пять машин с самым большим простоем, список сортируют по убыванию и берут первые пять. В Excel это фильтр «первые 10».
Таблицы моментов затяжки и допусков упорядочены по размеру. Человек ищет в них так же, как двоичный поиск: открывает середину и смотрит, левее или правее.
В системе учета ТО у таблиц есть индексы: отсортированные копии столбцов. Благодаря им карточка машины открывается сразу, а не через минуту.
Сравнением считается каждое сравнение, в котором участвует элемент списка (часы[j] > часы[j + 1], часы[j] > x); сравнения счетчиков вроде j >= 0 не считаются. Перестановкой считается каждая строка, которая записывает в список: обмен двух ячеек и сдвиг при вставке идут как одна операция. Быстрая сортировка взята в простом варианте с опорой в последнем элементе (схема Ломуто): на уже отсортированном списке она вырождается до n². Наработка машин сгенерирована случайно в пределах 3000–15000 ч, все значения разные. Замер роста гоняет готовые программы на случайных списках по одному разу.