>> [Играет музыка]
>> ДАГ Lloyd: Так вставки сортировки другой Алгоритм можно использовать для сортировки массива.
Идея этого алгоритма это, чтобы построить свой отсортированный массив
в месте, переминаясь элементы из способ, как вы идете, чтобы освободить место.
Это немного отличается от выбора рода или пузыря
рода, например, где мы регулировки местоположения,
где мы делаем свопы.
>> В этом случае то, что мы на самом деле делаете раздвижные элементы
более, из пути.
Как это алгоритм работать в псевдокоде?
Ну давайте просто произвольно сказать, что Первый элемент массива сортируется.
Мы строим ее на месте.
>> Мы собираемся идти один элемент, в то время, и строить и поэтому первое, что мы видим,
это массив один элемент.
И по определению, один элемент массива сортируется.
>> Тогда мы будем повторять этот процесс until-- мы будем повторять следующую процедуру
пока все элементы не сортируются.
Посмотрите на следующий несортированным элемента и вставьте его в отсортированном части,
путем сдвига необходимое количество элементов из пути.
Надеюсь, эта визуализация поможет вам увидеть именно то, что
происходит с вставки рода.
>> Итак, еще раз, вот наш Весь массив несортированный,
все элементы отображаются в красном цвете.
И давайте следовать шаги нашего псевдокоде.
Первое, что мы делаем, является мы называем Первый элемент массива, отсортировать.
Так что мы просто собираюсь говорить пять, вы теперь сортируются.
>> Затем мы рассмотрим на следующем несортированный элемент массива
и мы хотим, чтобы вставить, что в части отсортировано,
сдвигая элементы старше.
Так два это следующий несортированный элемент массива.
Очевидно, он принадлежит до пять, так что мы собираемся сделать
является своего рода проведет два в сторону на секунду, переложить пять над, а затем вставьте два
до пяти, где должны идти.
И теперь мы можем сказать, что два сортируется.
>> Итак, как вы видите, мы только пока посмотрел на двух элементов массива.
Мы не смотрели на отдых на всех, но мы
получил эти два элемента сортируются по Способ механизма переключения.
>> Таким образом, мы повторяем процесс снова.
Посмотрите на следующий несортированный элемент, что одна.
Давайте считать, что в сторону на секунду, переложить все закончилось, и положить один
где она должна идти.
>> Опять же, до сих пор, мы только когда-либо посмотрел на один, два и пять.
Мы не знаем, что еще идет, но мы сортируются эти три элемента.
>> Следующая несортированный элемент три, так что мы будем устанавливать его в сторону.
Мы постепенно смещать то, что мы нужно, который, на этот раз
это еще не все, как и в предыдущем два случая, это просто пять.
И тогда мы будем придерживаться три в, между двумя и пятью.
>> Шесть является следующим несортированный элемент к массиву.
И в самом деле шести больше пяти, так мы даже не нужно делать какие-либо замены.
Мы можем просто лавировать шесть право на конец отсортированного части.
>> Наконец, четыре является Последнее несортированный элемент.
Таким образом, мы будем устанавливать его в сторону, перейти по элементы, которые мы должны перенести в течение,
а затем положить четыре, где она принадлежит.
А теперь посмотрите, мы вроде из всех элементов.
Обратите внимание, с введением сортировать, у нас не было
чтобы идти вперед и назад через массив.
Мы только пошли через массив одно время, и мы перешли вещи
что мы уже сталкивались в порядок чтобы освободить место для новых элементов.
>> Так что в худшем случае Сценарий с вставки рода?
В худшем случае, массив в обратном порядке.
Вы должны перейти каждого из п элементов до н позиций, каждый раз, когда мы
сделать вставку.
Это много меняется.
>> В лучшем случае, Массив прекрасно отсортированы.
И вроде как то, что произошло с пятью и шестью в примере,
где мы могли бы просто лавировать ее на без того, чтобы сделать любой сдвиг,
мы, по существу, что делать.
>> Если представить, что наши Массив был один через шесть,
мы бы начать с заявив, один сортируется.
Два приходит после одного, чтобы мы могли просто говорят, хорошо, хорошо один и два сортируются.
Три приходит после двух, так, хорошо, один и два, и три сортируются.
>> Мы не делаем никаких свопы, мы просто перемещение эту произвольную линию
между сортируются и несортированный, как мы идем.
Как эффективно, как мы это делали в примере, поворачивая элементы синий, как мы дальше.
Так что в худшем случае выполнения, то?
Помните, что если у нас есть переложить каждый из русские элементы, возможно, N позиций,
мы надеемся, что дает вам идея, что в худшем случае
выполнения является Большой О п квадрате.
>> Если массив прекрасно сортировать, все, что мы должны сделать,
это посмотреть на каждого элемента один раз, а затем мы сделали.
Таким образом, в лучшем случае, это омега п.
>> Я Дуг Ллойд.
Это CS50.