Большинство алгоритмов, с которыми мы работали, были довольно медленными и кажутся неэффективными. Однако они, как правило, часто встречаются в курсах информатики и теоретических объяснениях, потому что они часто используются как наивный подход или простейшая реализация сортировки коллекции.
Сегодняшний алгоритм сортировки ничем не отличается. На самом деле некоторые люди считают эту методологию сортировки одной из самых интуитивно понятных. Мы собираемся взглянуть на сортировку вставкой, с которой вы, возможно, уже знакомы и, возможно, уже использовали в какой-то момент своей жизни. Сортировка вставкой интересна тем, что, хотя она не самая эффективная, она всегда используется в учебниках и лекциях по CS.
Так почему это?
Это связано с тем, что сортировка вставкой - один из самых простых для понимания алгоритмов сортировки. На самом деле, довольно часто возникает пример сортировки карт на руке - возможно, вы даже не осознавали этого, но в последний раз, когда у вас была куча игральных карт в руке, есть большая вероятность, что вы использовали какая-то версия алгоритма вставки сортировки для сортировки карт в вашей руке!
Давайте немного приблизимся к этому алгоритму и разберемся, в чем он заключается.
Проверка сортировки вставок
На самом базовом уровне алгоритм сортировки вставкой содержит логику перемещения и вставки элементов для сортировки неупорядоченного списка любого размера. Однако способ вставки элементов делает сортировку вставкой такой интересной!
Алгоритм сортировки вставкой имеет два основных аспекта. Первый важный аспект связан с его структурой.
Алгоритм сортировки вставкой поддерживает два подмножества (часто называемых подразделами или подсписками) - отсортированное подмножество и несортированное подмножество.
Второй аспект связан с тем, как он выполняет итерацию и сортирует заданную коллекцию элементов. Сортировка вставкой будет перебирать несортированное подмножество, эффективно «удаляя» его из несортированного подмножества и впоследствии «вставляя» в его правильное отсортированное место в отсортированном подмножестве.
Давайте посмотрим, как это работает на самом деле:
В приведенном выше примере мы начинаем с несортированной коллекции. Мы можем думать об этом как о нашей карточной руке, которая в настоящее время находится в большом беспорядке и нуждается в сортировке. Мы возьмем первый элемент и начнем сортировку на основе этого элемента. Другими словами, наш первый элемент - это первый элемент, который мы «сортируем». Теперь это дает нам две отдельные коллекции: отсортированную коллекцию и несортированную коллекцию.
Затем мы удалим первый неотсортированный элемент и добавим его в нашу отсортированную коллекцию. Чтобы выяснить, куда поместить этот новый элемент, нам нужно сравнить его с единственным элементом в нашей отсортированной коллекции; если элемент, который мы добавляем, больше, чем наш единственный отсортированный элемент, мы сохраним его в том же месте, где он сейчас находится, и пометим его как отсортированный. Однако в этом примере новый элемент меньше, чем наш единственный отсортированный элемент, мы переместим этот элемент обратно в первую позицию в коллекции и переместим отсортированный элемент вперед в коллекции, чтобы освободить для него место.
Это делает единственную итерацию сортировки вставкой. Очевидно, что список все еще не отсортирован! Нам нужно будет продолжить этот процесс для каждого оставшегося несортированного элемента и повторить те же шаги, пока мы заканчиваем итерацию по списку.
В некотором смысле сортировка вставкой похожа на другой алгоритм, который мы уже исследовали: сортировка по выбору. У обоих этих алгоритмов есть одна общая черта: каждый из них поддерживает концепцию отсортированных элементов и несортированных элементов. Однако каждый из них делает это по-разному. Это гораздо яснее на примере.
Давайте попробуем использовать сортировку вставкой для сортировки списка из шести чисел: 4, -31, 0, 99, 83, 1.
Для начала наш список будет несортированным. Мы уже знаем, что первый элемент будет перемещен в наше «отсортированное» подмножество, что означает, что изначально сортируется только число 4.
Чтобы упростить просмотр, в этом примере мы будем использовать красную разделительную линию, чтобы обозначить границу между отсортированными и несортированными коллекциями.
Затем извлечем первый несортированный элемент: -31. Мы хотим добавить его в наше отсортированное подмножество, поэтому нам нужно будет сравнить его со всеми отсортированными элементами (хотя сейчас у нас есть только один!). Поскольку -31 меньше 4, мы переместим 4 на следующую позицию в списке и переместим -31 на место, где изначально находилось число 4.
Наш отсортированный список теперь содержит -31 и 4 в правильном отсортированном порядке, как и следовало ожидать. Мы сделаем то же самое для следующего неотсортированного элемента, 0. Мы удалим его из отсортированного списка, сравним с каждым из отсортированных значений и переместим все элементы большего размера вправо, чтобы освободить место для добавляемого нового элемента.
Фактически, как только наш первый элемент помещен в «отсортированное» подмножество, мы продолжаем тот же процесс для каждого отдельного несортированного элемента в «несортированном» подмножестве, пока мы не отсортируем всю коллекцию.
Более глубокая проверка сортировки при вставке
Прежде чем мы перейдем к реализации сортировки вставкой, будет полезно попытаться немного упростить ее, чтобы было немного легче писать код. Мы можем свести этот алгоритм к основным правилам.
Во-первых, мы должны помнить, что любой элемент, начинающийся с индекса 0, будет нашим «отсортированным» подмножеством - по крайней мере, изначально. Полезное практическое правило: если у нас есть только один элемент, по определению этот элемент считается отсортированным; если вы задумаетесь, это станет более понятным. Если у вас только один элемент, нет никаких шансов, что что-то будет больше или меньше его, поэтому он отсортирован по умолчанию!
Во-вторых, по мере того, как мы повторяем и расширяем наше «несортированное» подмножество, мы медленно перемещаем элементы в отсортированное подмножество с каждой итерацией. Это означает, что одна итерация сокращает «несортированное» подмножество, удаляя элемент и и добавляя его к «отсортированному» подмножеству.
Другими словами, каждая итерация сортировки вставкой приводит к увеличению отсортированного подмножества и сжатию несортированного подмножества.
Это может пока не иметь большого смысла, и это нормально. На самом деле, я думаю, будет намного проще определить, как это работает, и увидеть его в действии, если мы посмотрим на быструю визуализацию сортировки вставкой:
В приведенном выше примере одна строка представляет состояние введенной коллекции для каждой итерации алгоритма сортировки. Надеюсь, что здесь происходит немного более очевидно. В каждой итерации еще один элемент считается «отсортированным», что обозначено красными квадратами. Мы видим, что с каждой итерацией появляется больше красных «отсортированных» элементов и меньше фиолетовых «несортированных» элементов. Количество элементов, конечно же, не меняется - мы просто перемещаемся по одному несортированному элементу на каждой итерации и добавляем его в «отсортированное» подмножество. Обратите внимание на направление, в котором происходит этот поток. Мы вернемся к этому в следующем разделе, но, возможно, вы уже можете увидеть здесь возникающую закономерность!
Хорошо, теперь, когда у нас есть два важных правила, давайте перейдем к хорошему и напишем код! Ниже представлена адаптированная версия вставки в JavaScript, основанная на реализации JS Rosetta Stone. Вот как может выглядеть наш insertionSort алгоритм:
Мы почти сразу заметим, что здесь происходят две петли, которые мы видели несколько раз раньше. Но прежде чем мы рассмотрим это… что еще здесь происходит?
Итак, мы начинаем с обхода входных данных массива и добавления первого элемента с индексом 0 в «отсортированную» часть списка; это происходит в строке 6, когда мы устанавливаем var currentUnsortedItem = array[i];. На самом деле это не меняет того, как массив выглядит, а просто создает наши «отсортированные» и «несортированные» разделы. Также следует отметить, что для первого элемента / итерации мы никогда не выполняем вложенный цикл в строке 13.
Но как насчет будущих итераций? Самый простой способ увидеть, как работает этот вложенный цикл (и когда он выполняется), - это запустить код. Так что давайте сделаем именно это! Вот как будет выглядеть наш insertionSort алгоритм при вводе [4, -31, 0, 99, 83, 1]:
Прохладный! Мы даже можем видеть, как все эти console.log распечатывают именно то, что происходит в алгоритме, что очень полезно. Наблюдение за реализацией этого кода, мы надеемся, подчеркивает, что мы все еще делаем те же шаги, что и раньше, когда у нас была только псевдокодированная сортировка вставкой:
- Мы перебираем неотсортированные элементы.
- На каждой итерации мы сравниваем первый неотсортированный элемент с каждым отсортированным элементом слева от него, который больше по размеру.
- Если элемент больше, мы перемещаем больший отсортированный элемент в следующую позицию индекса в массиве и вставляем несортированный элемент в предыдущий индекс перемещенного элемента. .
Мы также видим, что для первого элемента в этом массиве - в данном случае числа 4 - мы никогда не перебираем отсортированные элементы, и нет console.log из внутреннего цикла for (как мы и ожидали!).
Но вот мой вопрос: по сравнению с нашей недавней реализацией кода пузырьковой сортировки, здесь исполняемый код для сортировки вставкой не кажется таким плохим. Конечно, здесь проводится много сравнений, но это не кажется таким ужасным, как пузырьковая сортировка. Так что же делает этот алгоритм медленным? Почему именно это неэффективно?
Время узнать!
Устранение неэффективности вставки
Поскольку это не первое родео алгоритмов, надеюсь, когда вы увидели эти два вложенных цикла, вы сразу поняли, что это плохие новости для времени работы нашего алгоритма. Из нашего опыта с пузырьковой сортировкой на прошлой неделе и сортировкой по выбору за неделю до этого мы уже знаем, что это дает квадратичное время выполнения, или O (n²) в нотации Big O.
Квадратичное время выполнения, как правило, плохая идея, потому что это означает, что по мере того, как наш ввод удваивается, время, необходимое нашему алгоритму вставки для сортировки нашего ввода, будет четырехкратным. Это не сулит ничего хорошего, если у нас есть большой набор данных, который мы пытаемся отсортировать.
Однако все же стоит посмотреть, зачем нужны эти два вложенных цикла. И, когда дело доходит до сортировки вставкой, эти два цикла особенно интересны, потому что они работают по-настоящему уникальным образом.
Если мы посмотрим на показанный здесь пример, мы увидим, что визуализируются два цикла: внешний цикл и внутренний цикл.
Внешний цикл - это то место, где мы выполняем итерацию по несортированному списку - каждый отдельный элемент будет повторяться в этом цикле, и мы будем выполнять итерацию слева направо, начиная с первого несортированного элемента слева, который в конечном итоге становится первый отсортированный элемент.
Внутренний цикл представляет собой «переход» элементов. Здесь мы перебираем отсортированные элементы; здесь мы сравниваем несортированный элемент с отсортированными, чтобы решить, где он должен находиться в «отсортированном» подмножестве. Однако, в отличие от внешнего цикла, внутренний цикл будет выполняться только для элементов n-1, где n - общее количество элементов в массиве, поскольку он никогда не выполняется для самый первый элемент в списке. Еще одна вещь, которая отличает внутренний цикл от внешнего, заключается в том, что мы выполняем итерацию справа налево, а не слева направо.
Это имеет смысл, если мы немного подумаем об этом - когда мы реализовали и выполнили наш JavaScript insertionSort, мы сравнили первый неотсортированный элемент с крайним правым отсортированным элементом. Если он был меньше, мы перемещали элементы, а затем продолжали делать то же самое: мы сравнивали наш неотсортированный элемент со следующим самым правым отсортированным. Фактически мы выполняли итерацию снова через отсортированное подмножество.
Именно эта двойная итерация делает сортировку вставкой неэффективным алгоритмом. Однако это также то, что делает этот алгоритм сортировки таким уникальным!
Другой действительно интересной характеристикой этого алгоритма является то, что если он в основном отсортирован, ему больше не нужно делать столько итераций или сравнений во вложенном внутреннем цикле. Это означает, что даже несмотря на то, что в худшем случае время выполнения для сортировки вставкой составляет O (n²), учитывая массив, в котором почти все элементы отсортированы, временная сложность алгоритма существенно изменяется. Фактически, время работы значительно улучшается.
Наилучшее время выполнения алгоритма сортировки вставкой в почти отсортированном списке оказывается линейным - или O (n) - поскольку внутреннему циклу требуется гораздо меньше сравнений.
Конечно, мы обычно не классифицируем и не рассматриваем алгоритмы на основе их лучших сценариев, а скорее на основе наихудших сценариев. Итак, несмотря на этот интересный факт, мы в конечном итоге разбиваем сортировку вставкой как алгоритм с квадратичным временем выполнения.
Какие еще способы мы можем классифицировать алгоритм сортировки вставкой, используя термины, с которыми мы уже знакомы?
Мы уже знаем, что временная сложность сортировки при вставке квадратична или O (n²). Мы также знаем, что на самом деле для этого не требуется так много дополнительного места - объем пространства, который ему нужен внутри его двух вложенных циклов, является постоянным, или O (1), и в конечном итоге используется для создания ссылок на временные переменные на элементы в определенном индекс в массиве. Так как он работает непосредственно с введенными данными (и не копирует их) и для работы требуется только постоянный объем памяти, сортировку вставкой можно классифицировать как на месте алгоритм сортировки.
Когда алгоритм перебирает несортированные элементы и вставляет их в правильное место в «отсортированном» подмножестве, он выполняет итерацию справа налево. Это означает, что для коллекции с несколькими одинаковыми значениями они будут размещены в отсортированном подмножестве в том же порядке, что и в несортированном подмножестве. Если мы снова посмотрим на код, это станет более очевидным. Поскольку мы используем операторы сравнения (такие как < и >), если два элемента совпадают, один не будет перемещен перед другим. Вместо этого второй повторяющийся элемент будет просто вставлен справа после первого. Это делает сортировку вставкой стабильным алгоритмом сортировки. Поскольку мы также подтвердили тот факт, что этот алгоритм использует операторы сравнения, мы можем классифицировать его как алгоритм сравнения.
Поскольку мы знаем, что этот алгоритм повторяется (дважды!), Мы знаем, что он итеративный и, следовательно, нерекурсивный по своей природе. Наконец, поскольку сортировка вставкой сохраняет все свои данные в основной памяти и не требует какой-либо внешней памяти, ее можно отнести к категории внутреннего алгоритма сортировки.
Итак, в следующий раз, когда вы будете играть в Go Fish с другом и обнаружите, что ужасно проигрываете, с целой кучей карт в руке - помните о силе сортировки вставками. Может быть, вы сможете просто отвлечь всех, обучив их этому алгоритму сортировки, и стать настоящим победителем!
Ресурсы
Сортировка вставками довольно часто встречается в большинстве курсов и учебных программ по информатике, а это значит, что довольно легко найти множество примеров и руководств, объясняющих, как это работает. Если вам хочется глубже погрузиться, просмотреть другие примеры или просмотреть дополнительный код, эти ссылки - хорошее место для начала.
- Сортировка вставкой, Интерактивный Python
- Структуры данных и алгоритмы: сортировка вставкой, Учебное пособие
- Алгоритмы сортировки / сортировка вставками, Rosetta Code
- Сортировка вставками, Khan Academy
- Сортировка вставками, профессор Рашид Бин Мухаммад
- Сортировка вставкой, Harvard CS50
