[Играет музыка] ДАГ Lloyd: Сортировать Выбор является алгоритм, который, как вы могли бы ожидать, сортирует набор элементов. И алгоритм отзыв это шаг за шагом набор инструкций для выполнения задачи. 

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

Это может помочь визуализировать это, так что давайте взглянем на это. Так что это Я утверждаю, что это несортированный массив а у меня указано его о том, что все из элементов красного цвета, они еще не сортируются. Это полное несортированный часть массива. 

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

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

В этом случае, было бы пять, так что мы поменять одного до пяти. Когда мы делаем это, мы можем наглядно увидеть, что мы переехал с наименьшим значением элемента массива, в самом начале. Эффективно сортировки этот элемент. 

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

Теперь мы просто повторить процесс снова. Мы ищем через несортированным части массив, чтобы найти наименьший элемент. В этом случае, это два. 

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

Мы снова искать через, и мы найти наименьший элемент четыре. Мы поменять его с первым элементом несортированный часть, и в настоящее время четыре сортируется. 

Мы считаем, что это пять наименьший элемент. Мы поменять его с первым элемент неотсортированной части. А теперь пять сортируется. 

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

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

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

Таким образом, в худшем случае выполнения, мы придется повторить процесс п раз, один раз для каждого из п элементов. И в лучшем случае, мы должны сделать то же самое. 

Так вспоминая наш вычислительная сложность инструментов, то, что вы думаете, это худшее Дело исполнения для выбора рода? Что вы считаете лучшим Дело исполнения для выбора рода? 

Вы догадались Big O н квадрат, и Большой Омега п квадрате? Вы были бы правы. Те, в самом деле, в худшем случае и лучший случай выполнения раз, для выбора рода. 

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