ДАГ Lloyd: Так в CS50 мы узнали о разнообразие сортировки и поиска алгоритмы. И иногда это может быть немного сложнее держать трек, какой алгоритм делает. Мы действительно только обезжиренное поверхность тоже Есть много других поиск и алгоритмы сортировки. Таким образом, в этом видео давайте просто взять несколько минут чтобы попытаться отогнать каждый алгоритм до его основных элементов так что вы можете помнить, наиболее важная информация о них и быть в состоянии сформулировать различия, если это необходимо. 

Первый выбор рода. Основная идея выбора рода это найти наименьший элемент несортированный в массиве и поменять его с в первую очередь несортированный элемент этого массива. Мы сказали, что в худшем случае запустить время, что был н квадрате. И если вы хотите, чтобы вспомнить, почему, взять Посмотрите на выбор рода видео. Время работы лучшем случае также п квадрате. 

Пузырь рода, идея, что один, чтобы поменять соседние пары. Так что это ключ, который помогает вам запомнить разницу здесь. Выбор рода есть, до сих пор, найти smallest-- пузырь Сортировать вне поменять соседние пары. Мы поменять соседние пары элементов, если они вышли из строя, который эффективно пузыри крупные элементы права, и в то же время она также начинает для перемещения мелких элементов влево. Время выполнения случай наихудшего случая пузыря сортировки п квадрате. Время работы лучшем случае пузыря сортировки п. Потому что в этой ситуации мы не actually-- мы, возможно, не нужно делать какие-либо свопы на всех. У нас есть только сделать один пройти через все п элементов. 

В вставки рода, то Основная идея здесь меняется. Это ключевое слово для вставки рода. Мы собираемся выйти один раз через массив слева направо. И, как мы делаем, мы собирается перенести элементы мы уже видели, чтобы освободить место для мелкие, что нужно, чтобы соответствовать где-то назад в этой отсортировано части. Так мы строим отсортированный массив одним элемент, в то время, слева направо, и мы переходим вещи, чтобы сделать комнату. Наихудший время пробег вставка сортировки п квадрате. Время лучший вариант запуска является н. 

Слияние sort-- ключевого слова здесь разделение и слияние. Мы разделили полный спектр ли это шесть элементов, восьми элементов, 10000 elements-- мы разделили его сократилась вдвое, вдвое, вдвое, пока у нас под массив н одной массивов элементов. Набор N Один массивов элементов. Итак, мы начали с одной Массив 1000 элемент, и мы добраться до точки, где мы есть 1000 массивов одноэлементные. Тогда мы начинаем объединить эти суб массивы вместе в правильном порядке. Таким образом, мы принять два массива одноэлементные и создать массив из двух элементов. Возьмем два массивы двух элементов и создать массив из четырех элементов и так далее, и так далее, пока мы не снова восстановлен один массив п элементов. 

Наихудший время пробег сортировка слиянием п раз войти н. У нас есть п элементов, но этот процесс рекомбинирующий принимает войти п шагов, чтобы получить вернуться к полной массива. В лучшем случае время выполнения также п журнала п потому что этот процесс не имеет большого заботиться, был ли массив сортировки или не начинать. Процесс тот же, есть нет способ коротких вещей выключателей. Так п п войти в худшем случае, п п войти в лучшем случае. 

Мы говорили о двух алгоритмы поиска. Так линейный поиск о итерации. Перейдем через массив один раз, слева направо, пытаясь найти номер что мы ищем. Время худший запустить большой вывода п. Это может занять нам итерации по каждой элемента чтобы найти элемент мы ищем для, либо в последней позиции, или не на всех. Но мы не можем подтвердить, что до тех пор, мы смотрели на все. м лучшем случае, мы сразу найти. Лучший случая время пробег линейный поиск омега 1. 

Наконец, было бинарный поиск, который требует ассорти массив. Помните, что это очень важным фактором при работе с бинарного поиска. Это является необходимым условием для помощи it-- массив, что вы ищете через должны быть отсортированы. В противном случае, ключевое слово это разделяй и властвуй. Сплит массив пополам и устранения половина элементов каждый раз, как вы пройти через. Из-за этого разделяй и властвуй и разделение вещей в половине подхода, в худшем случае время выполнения бинарных поиск войти н, который, по существу лучше, чем линейный поиск в п. Время лучшем случае работать по-прежнему один. 

Мы могли бы сразу же найти Первый раз мы делаем разделение, но, снова, помните, что хотя двоичный поиск значительно лучше, чем линейный поиск в силу того, журнал N по сравнению с п, Вы, возможно, придется пройти через работу сортировки свой массив первой, может сделать его менее эффективным в зависимости на размер итерации отсортированы. 

Я Дуг Ллойд, это CS50.