Известно, что портные используют сортировку вставки, чтобы расположить одежду в определенном порядке. Давайте погрузимся в увлекательную историю одного такого портного, который использует технический алгоритм сортировки вставками для своих повседневных задач.
Джейкоб, портной из маленького городка, посещает ближайшую библиотеку, где находит молодого увлеченного мальчика по имени Чарли. Чарли — студент технического профиля и с большим энтузиазмом относится к алгоритмам и их реализации в реальной жизни.
«Ты что, шутишь? Сортировка вставками!!», — сказал Чарли. Всего 2 месяца в его техническом образовании, а Чарли уже стал немного высокомерным в своем тоне.
«Кто-нибудь когда-нибудь использовал сортировку вставками?» — продолжил Чарли.
«Это алгоритм O(log n2), и есть несколько других, лучше, чем сортировка вставками. Как насчет того, чтобы попытаться продвинуться вперед с сортировкой слиянием? Если хочешь, я могу помочь», — сказал Чарли.
«О!», — ответил потрясенный мужчина, все еще глядя на Чарли.
Ворвался библиотекарь и спросил двоих: «Что это за замалчивание? Это библиотека, пожалуйста, соблюдайте приличия».
«Ваш восторженный ученик обучал меня ценности других алгоритмов сортировки по сравнению с тем, который я сейчас использую — сортировкой вставками», — воскликнул Джейкоб.
Мисс, он использует «Сортировку вставками!» — сказал Чарли с лукавой ухмылкой, ожидая, что библиотекарь присоединится к нему со смехом. Но его постигло разочарование, так как хозяйка отреагировала не так, как он ожидал.
«Я думал, вы пришли для исследования методов удаления пятен, которые не повлияют на качество одежды, не так ли?», спросила библиотекарь с любопытством.
Портной кивнул. «Я ждал тебя здесь, пока Чарли застал меня в своей интересной битве за то, какой сорт мне использовать и как работает мой магазин. У него были некоторые идеи и разногласия по поводу того, как я сортирую куртки в своем магазине».
— Понятно, — сказал библиотекарь. Как она знала, портной долго продолжал: «Лучшим методом в вашей ситуации было бы использовать сортировку вставками».
Чарли, потрясенный до невозможности слов, закричал: «Что!!» Его лицо покраснело от крови, и он не мог понять, почему они оба не понимают разницы между вычислительной мощностью двух алгоритмов.
Библиотекарь бросил на Чарли холодный суровый взгляд. Смущенный, он быстро опустил глаза и смиренно спросил портного: «Может быть, вы объясните, почему вы предпочитаете сортировку вставками другим алгоритмам сортировки?»
«Послушайте, мой магазин небольшой, и у меня есть только одна стойка для курток, и мне нравится сортировать их по размеру. Потому что проще, когда приходят клиенты. Они просят конкретный размер, и я использую бинарный поиск, чтобы найти нужный», — продолжил Портной.
«В этом есть смысл», — согласился Чарли. Бинарный поиск был еще одним его любимым, и он подумал про себя, что, по крайней мере, портной использует правильный алгоритм для поиска пиджака.
«Каждый понедельник я получаю новую партию курток, и мне нужно повесить их на вешалку. Таким образом, чтобы уберечь их от складок (именно поэтому я не держу их на полу), я подвешиваю их все в конце стойки. У меня есть N отсортированных жакетов на одном конце, а за ними M новых несортированных жакетов. Итак, я беру каждую новую куртку и вставляю ее в уже рассортированный комплект курток. После вставки первой куртки у меня есть N+1 отсортированных курток и M-1 несортированных курток. Я продолжаю делать это, пока все не будет вставлено», — продолжил портной.
Прежде чем Чарли успел вмешаться, библиотекарь попросила его сначала послушать.
«Я думаю, что Чарли хочет знать: «Почему бы вам не снять куртки полностью и не использовать какой-нибудь другой механизм сортировки, такой как Mergesort?», — объяснил библиотекарь.
«Потому что куртки тяжелее», — объяснил портной. «Было больно снимать их со стойки. Но они легко соскальзывают».
Чарли выглядел сбитым с толку. По какой причине это имело значение, что было так трудно снять вещи со стойки? Это был спор о вычислительной сложности.
«Я думаю, что вы упускаете из виду тот фактор, что когда большинство людей используют сортировку вставками, вставки обходятся дорого», — объяснил библиотекарь Питеру. «Представьте себе бухгалтера, который пытается отсортировать список счетов в одной из своих книг. Каждая строка — это одна учетная запись — как записи в компьютерном массиве. Вы не можете просто вставить что-то, а остальное автоматически сместится вниз. Это потребовало бы самой утомительной формы магии. Каждый раз, когда бухгалтер хочет сделать вставку, ему приходится вручную сдвигать вниз все, что ниже. Одна вставка — это операция O(N). Это много стираний и переписываний».
«Но для портного вставка — это операция O(1). Вы просто сбрасываете пальто», — добавила библиотекарь.
Чарли согласно кивнул. Внутри он дразнил тупую деталь физического мира, которая выглядит за счет различных действий. Гипотетический мир был намного чище. Как бы то ни было, он согласился с библиотекарем и портным; в этой ситуации действительно казалось, что сортировка вставками имеет смысл. Он размышлял над тем, какие другие настоящие приложения могут проверить его предположение о вычислительной сложности».
