[Powered by Google Translate] [Вставка Сортировка]
[Tommy MacWilliam] [Гарвардский университет]
[Это CS50.TV]
Давайте взглянем на сортировку вставками, алгоритм принятия список чисел и сортировка их.
Алгоритм, помните, это просто шаг за шагом процедуры для выполнения задачи.
Основная идея сортировки вставкой, заключается в разделении нашего списка на две части,
отсортировано части и несортированные часть.
>> На каждом шаге алгоритма, числа перемещается
от несортированные части к отсортированы часть
пока в конце концов весь список будет отсортирован.
Вот список из шести несортированные номера - 23, 42, 4, 16, 8 и 15.
Поскольку эти цифры не все в порядке, они отсортированы.
Так как мы еще не начали сортировки тем не менее, мы будем рассматривать все шесть элементов наших несортированные часть.
>> Как только мы начинаем сортировку, мы поместим эти упорядоченные номера слева от них.
Итак, давайте начнем с 23, первый элемент в нашем списке.
У нас нет никаких элементов в наших сортируются часть все же,
так что давайте просто рассмотрим 23, чтобы быть в начале и конце нашего отсортированы часть.
Теперь наши отсортированы часть имеет одно число, 23,
и наши несортированные часть имеет эти пять чисел.
Давайте теперь вставить следующий номер в нашем несортированные часть, 42, в отсортированы часть.
>> Чтобы сделать это, нам нужно сравнить с 42 до 23 - единственный элемент в наших сортируются часть до сих пор.
Сорок два больше, чем 23, поэтому мы можем просто добавить 42 к концу
из отсортированных часть списка. Отлично!
Теперь наши отсортированы часть состоит из двух элементов, и наши несортированные часть состоит из четырех элементов.
Итак, давайте перейдем к 4, то следующий элемент в несортированный часть.
Так, где это должно быть помещено в отсортированы часть?
>> Помните, мы хотим поместить это число в определенном порядке
таким образом, наши отсортированы часть остается правильно отсортированный во все времена.
Если мы поместим 4 вправо из 42, то наш список будет в порядке.
Итак, давайте продолжать двигаться справа-слева в наш род часть.
Поскольку мы двигаемся, давайте переложить каждый номер вниз место, чтобы освободить место для нового номера.
Ладно, 4 также меньше, чем 23, поэтому мы не можем поместить его и здесь.
Давайте перейдем на 23 правую одном месте.
>> Это означает, что мы хотели бы разместить 4 в первый слот в отсортированной части.
Обратите внимание, как это место в списке было уже пусто,
потому что мы двигались отсортированы элементы вниз, как мы столкнулись с ними.
Хорошо. Таким образом, мы уже на полпути.
Давайте продолжим наш алгоритм, вставив 16 в отсортированы часть.
Шестнадцать меньше, чем 42, так что давайте переложить 42 до правой.
Шестнадцать также меньше, чем 23, так что давайте также сдвиг этого элемента.
>> Теперь, 16 больше 4. Так что, похоже, мы хотели бы, чтобы вставить 16 между 4 и 23.
При перемещении через отсортированы часть списка справа налево,
4 является первым номером мы видели, что это меньше, чем число
Мы пытаемся вставить.
Итак, теперь мы можем вставить 16 в этом пустом слоте,
который, помните, мы создали на подвижных элементов в род часть более
как мы столкнулись с ними.
>> Хорошо. Теперь у нас есть четыре отсортированы элементов и двух элементов несортированные.
Итак, давайте перейдем 8 в отсортированы часть.
Восемь меньше, чем 42.
Восемь меньше, чем 23.
А 8 меньше, чем 16.
Но 8 больше 4.
Таким образом, мы хотели бы, чтобы вставить 8 между 4 и 16.
А сейчас мы просто еще один элемент оставили для сортировки - 15.
Пятнадцать меньше, чем 42,
Пятнадцать меньше, чем 23.
А 15 меньше, чем 16.
Но 15 больше, чем 8.
>> Итак, вот где мы хотим, чтобы наша конечная вставки.
И мы сделали.
У нас больше нет элементов в несортированный часть,
и наши отсортированы часть находится в правильном порядке.
Номера упорядочены от наименьшего к наибольшему.
Итак, давайте взглянем на некоторые псевдокод, описывающий шаги, которые мы только что выполнили.
>> В строке 1, мы видим, что нам нужно для перебора каждого элемента в списке
кроме первой, так как первый элемент в несортированный часть просто станут
Первый элемент в отсортированной части.
В строках 2 и 3, мы отслеживают наше нынешнее место в несортированный часть.
Элемент представляет собой число мы в настоящее время движется в отсортированы часть,
и J представляет наш индекс в несортированный часть.
>> В строке 4 мы перебора отсортированного часть справа налево.
Мы хотим остановить итерацию раз элемент слева от нашей текущей позиции
меньше, чем элемент, который мы пытаемся вставить.
В строке 5 мы перекладывая каждый элемент мы сталкиваемся одном пространстве с правой стороны.
Таким образом, мы будем иметь свободное пространство для вставки в когда мы находим первый элемент
меньше, чем элемент мы движемся.
В строке 6, мы обновляем счетчик продолжать двигаться налево через отсортированы часть.
Наконец, в строке 7, мы вставка элемента в отсортированный часть списка.
>> Мы знаем, что это нормально для вставки в позицию J,
потому что мы уже переехали элемент, используемый, чтобы быть там одно место вправо.
Помните, что мы движемся через отсортированы часть справа налево,
но мы движемся через несортированные часть слева направо.
Хорошо. Давайте теперь взглянем на то, как долго работает, что алгоритм взял.
Мы сначала задать вопрос, сколько времени потребуется для этого алгоритма для работы в худшем случае.
Напомним, что мы представляем это время работы с большой обозначение O.
Для того, чтобы разобраться наш список, мы были для перебора элементов в несортированный часть,
и для каждого из этих элементов, потенциально над всеми элементами в отсортированной части.
Интуитивно, это звучит как O (N ^ 2) операций.
>> Глядя на нашем псевдокоде, у нас есть цикл вложен в другой цикл,
который, действительно, звучит как O (N ^ 2) операций.
Тем не менее, отсортированные часть списка не содержат весь список до самого конца.
Тем не менее, мы потенциально могли бы вставить новый элемент в самом начале отсортированного часть
на каждой итерации алгоритма,
Это означает, что мы должны смотреть на каждый элемент в настоящее время в отсортированной части.
Таким образом, это означает, что мы потенциально могли бы сделать одно сравнение для второго элемента,
два сравнения для третьего элемента, и так далее.
Таким образом, общее количество шагов является сумма чисел от 1 до длины списка минус 1.
Мы можем представить это с помощью суммирования.
>> Мы не будем вдаваться в суммах здесь, но оказывается, что это суммирование равно
(п - 1) более 2, что эквивалентно п ^ 2/2 - п / 2.
Когда речь идет об асимптотической выполнения,
это п ^ 2 срока будет доминировать в этой п срок.
Таким образом, включение сортировки Big O (N ^ 2).
Что, если мы побежали сортировки вставкой в ​​уже отсортированный список.
В этом случае, мы бы просто создать отсортированный часть слева направо.
Таким образом, мы будем только нужно порядка п шагов.
>> Это означает, что сортировка вставкой имеет лучшем случае выполнения п,
которые мы представляем с Ω (N).
И вот именно для сортировки вставкой,
лишь одна из многих алгоритмов можно использовать для сортировки списка.
Меня зовут Томми, и это CS50.
[CS50.TV]
О, вы просто не можете остановиться, что как только он начинается.
Да, мы сделали это - >> Boom!