1
00:00:00,000 --> 00:00:05,726
>> [Играет музыка]

2
00:00:05,726 --> 00:00:08,600
ДАГ Lloyd: Сортировать Выбор является
алгоритм, который, как вы могли бы ожидать,

3
00:00:08,600 --> 00:00:10,470
сортирует набор элементов.

4
00:00:10,470 --> 00:00:12,470
И алгоритм отзыв
это шаг за шагом набор

5
00:00:12,470 --> 00:00:15,260
инструкций для выполнения задачи.

6
00:00:15,260 --> 00:00:17,580
>> При выборе сортировать
Основная идея это,

7
00:00:17,580 --> 00:00:22,080
найти наименьшее несортированный элемент и
добавить его в конце отсортированного списка.

8
00:00:22,080 --> 00:00:26,970
Эффективно, что это делает сборки
отсортированный список, один элемент за один раз.

9
00:00:26,970 --> 00:00:29,800
Нарушение его до псевдокоде
мы могли бы утверждать, этот алгоритм

10
00:00:29,800 --> 00:00:34,490
как следует, не повторять это, пока
нет несортированные элементы остаются.

11
00:00:34,490 --> 00:00:38,660
Поиск через несортированный
данные, чтобы найти наименьшее значение,

12
00:00:38,660 --> 00:00:44,130
Затем поменять наименьшее значение с
Первый элемент неотсортированной части.

13
00:00:44,130 --> 00:00:47,130
>> Это может помочь визуализировать это,
так что давайте взглянем на это.

14
00:00:47,130 --> 00:00:49,710
Так что это Я утверждаю, что это
несортированный массив а у меня

15
00:00:49,710 --> 00:00:53,040
указано его о том, что все
из элементов красного цвета,

16
00:00:53,040 --> 00:00:54,420
они еще не сортируются.

17
00:00:54,420 --> 00:00:57,670
Это полное
несортированный часть массива.

18
00:00:57,670 --> 00:01:02,020
>> Итак, давайте по шагам
Выбор рода сортировать этот массив.

19
00:01:02,020 --> 00:01:05,296
Итак, еще раз, мы собираемся повторить
до не несортированные элементы остаются.

20
00:01:05,296 --> 00:01:07,920
Мы собираемся Поиск по
данные, чтобы найти наименьшее значение,

21
00:01:07,920 --> 00:01:11,990
а затем обменять эту величину с
Первый элемент неотсортированной части.

22
00:01:11,990 --> 00:01:14,380
>> Сейчас, опять же, вся
Массив является несортированный часть.

23
00:01:14,380 --> 00:01:16,534
Все красных элементов несортированный.

24
00:01:16,534 --> 00:01:18,700
Таким образом, мы искать через и
мы находим наименьшее значение.

25
00:01:18,700 --> 00:01:20,533
Мы начнем с самого начала,
мы идем до конца,

26
00:01:20,533 --> 00:01:23,630
мы находим наименьшее значение, один.

27
00:01:23,630 --> 00:01:24,860
Так вот первая часть.

28
00:01:24,860 --> 00:01:29,440
И тогда вторая часть, поменять это значение с
первый элемент неотсортированной части,

29
00:01:29,440 --> 00:01:31,340
или первый элемент красный.

30
00:01:31,340 --> 00:01:34,980
>> В этом случае, было бы
пять, так что мы поменять одного до пяти.

31
00:01:34,980 --> 00:01:37,320
Когда мы делаем это, мы можем
наглядно увидеть, что мы

32
00:01:37,320 --> 00:01:41,260
переехал с наименьшим значением элемента
массива, в самом начале.

33
00:01:41,260 --> 00:01:43,920
Эффективно сортировки этот элемент.

34
00:01:43,920 --> 00:01:47,520
>> И таким образом мы можем подтвердить, действительно
и государство, что один, сортируется.

35
00:01:47,520 --> 00:01:52,080
И поэтому мы будем указывать отсортированный часть
из нашего массива, по окраске он голубой.

36
00:01:52,080 --> 00:01:53,860
>> Теперь мы просто повторить процесс снова.

37
00:01:53,860 --> 00:01:57,430
Мы ищем через несортированным части
массив, чтобы найти наименьший элемент.

38
00:01:57,430 --> 00:01:59,000
В этом случае, это два.

39
00:01:59,000 --> 00:02:02,100
>> Мы поменять, что с первого
элемент неотсортированной части.

40
00:02:02,100 --> 00:02:05,540
В этом случае два также бывает
первый элемент неотсортированной части.

41
00:02:05,540 --> 00:02:08,650
Таким образом, мы поменять два с себя,
которые на самом деле просто оставляет два

42
00:02:08,650 --> 00:02:11,257
где он находится, и это сортируется.

43
00:02:11,257 --> 00:02:13,840
Продолжая, мы ищем через
найти наименьший элемент.

44
00:02:13,840 --> 00:02:15,030
Это три.

45
00:02:15,030 --> 00:02:17,650
Мы поменять его с первым
элемент, который является пять.

46
00:02:17,650 --> 00:02:19,450
А теперь три сортируется.

47
00:02:19,450 --> 00:02:22,440
>> Мы снова искать через, и мы
найти наименьший элемент четыре.

48
00:02:22,440 --> 00:02:28,070
Мы поменять его с первым элементом
несортированный часть, и в настоящее время четыре сортируется.

49
00:02:28,070 --> 00:02:29,910
>> Мы считаем, что это пять
наименьший элемент.

50
00:02:29,910 --> 00:02:32,900
Мы поменять его с первым
элемент неотсортированной части.

51
00:02:32,900 --> 00:02:34,740
А теперь пять сортируется.

52
00:02:34,740 --> 00:02:36,660
>> И тогда, наконец, наш
несортированный часть состоит

53
00:02:36,660 --> 00:02:38,576
только из одного элемента,
поэтому мы искать через

54
00:02:38,576 --> 00:02:41,740
и мы находим, что шесть это
маленький, а на самом деле, единственным элементом.

55
00:02:41,740 --> 00:02:44,906
И тогда мы можем утверждать, что это сортируется.

56
00:02:44,906 --> 00:02:47,530
А теперь мы перешли нашу массив
от полного несортированный

57
00:02:47,530 --> 00:02:52,660
в красный, полностью сортируются
в синем, с помощью выбора рода.

58
00:02:52,660 --> 00:02:54,920
>> Так что в худшем случае здесь?

59
00:02:54,920 --> 00:02:57,830
Ну в самое худшее
так, мы должны смотреть за

60
00:02:57,830 --> 00:03:02,170
все элементы массива в
найти наименьшее несортированный элемент,

61
00:03:02,170 --> 00:03:04,750
и мы должны повторить
этот процесс п раз.

62
00:03:04,750 --> 00:03:09,090
После того, как для каждого элемента массива
потому что мы только в этом алгоритме,

63
00:03:09,090 --> 00:03:12,180
Сортировать один элемент за раз.

64
00:03:12,180 --> 00:03:13,595
>> Какой самый лучший сценарий?

65
00:03:13,595 --> 00:03:15,040
Ну, это точно так же, верно?

66
00:03:15,040 --> 00:03:18,440
Мы на самом деле нужно еще пройти через
каждый элемент массива

67
00:03:18,440 --> 00:03:22,040
для того, чтобы подтвердить, что он есть,
В самом деле, наименьший элемент.

68
00:03:22,040 --> 00:03:26,760
>> Таким образом, в худшем случае выполнения, мы
придется повторить процесс п раз,

69
00:03:26,760 --> 00:03:28,960
один раз для каждого из п элементов.

70
00:03:28,960 --> 00:03:31,940
И в лучшем случае,
мы должны сделать то же самое.

71
00:03:31,940 --> 00:03:35,340
>> Так вспоминая наш
вычислительная сложность инструментов,

72
00:03:35,340 --> 00:03:39,250
то, что вы думаете, это худшее
Дело исполнения для выбора рода?

73
00:03:39,250 --> 00:03:41,840
Что вы считаете лучшим
Дело исполнения для выбора рода?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Вы догадались Big O н квадрат,
и Большой Омега п квадрате?

76
00:03:49,325 --> 00:03:49,950
Вы были бы правы.

77
00:03:49,950 --> 00:03:52,490
Те, в самом деле,
в худшем случае и лучший случай выполнения

78
00:03:52,490 --> 00:03:55,100
раз, для выбора рода.

79
00:03:55,100 --> 00:03:56,260
>> Я Дуг Ллойд.

80
00:03:56,260 --> 00:03:58,600
Это CS50.

81
00:03:58,600 --> 00:04:00,279