1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Вставка Сортировка]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Гарвардский университет]

3
00:00:04,240 --> 00:00:07,290
[Это CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Давайте взглянем на сортировку вставками, алгоритм принятия список чисел и сортировка их.

5
00:00:13,060 --> 00:00:18,300
Алгоритм, помните, это просто шаг за шагом процедуры для выполнения задачи.

6
00:00:18,300 --> 00:00:23,640
Основная идея сортировки вставкой, заключается в разделении нашего списка на две части,

7
00:00:23,640 --> 00:00:26,580
отсортировано части и несортированные часть.

8
00:00:26,580 --> 00:00:29,290
>> На каждом шаге алгоритма, числа перемещается

9
00:00:29,290 --> 00:00:32,439
от несортированные части к отсортированы часть

10
00:00:32,439 --> 00:00:35,680
пока в конце концов весь список будет отсортирован.

11
00:00:35,680 --> 00:00:43,340
Вот список из шести несортированные номера - 23, 42, 4, 16, 8 и 15.

12
00:00:43,340 --> 00:00:47,680
Поскольку эти цифры не все в порядке, они отсортированы.

13
00:00:47,680 --> 00:00:53,890
Так как мы еще не начали сортировки тем не менее, мы будем рассматривать все шесть элементов наших несортированные часть.

14
00:00:53,890 --> 00:00:59,270
>> Как только мы начинаем сортировку, мы поместим эти упорядоченные номера слева от них.

15
00:00:59,270 --> 00:01:03,600
Итак, давайте начнем с 23, первый элемент в нашем списке.

16
00:01:03,600 --> 00:01:06,930
У нас нет никаких элементов в наших сортируются часть все же,

17
00:01:06,930 --> 00:01:12,460
так что давайте просто рассмотрим 23, чтобы быть в начале и конце нашего отсортированы часть.

18
00:01:12,460 --> 00:01:16,510
Теперь наши отсортированы часть имеет одно число, 23,

19
00:01:16,510 --> 00:01:20,260
и наши несортированные часть имеет эти пять чисел.

20
00:01:20,260 --> 00:01:27,320
Давайте теперь вставить следующий номер в нашем несортированные часть, 42, в отсортированы часть.

21
00:01:27,320 --> 00:01:35,930
>> Чтобы сделать это, нам нужно сравнить с 42 до 23 - единственный элемент в наших сортируются часть до сих пор.

22
00:01:35,930 --> 00:01:41,980
Сорок два больше, чем 23, поэтому мы можем просто добавить 42 к концу

23
00:01:41,980 --> 00:01:45,420
из отсортированных часть списка. Отлично!

24
00:01:45,420 --> 00:01:51,850
Теперь наши отсортированы часть состоит из двух элементов, и наши несортированные часть состоит из четырех элементов.

25
00:01:51,850 --> 00:01:57,200
Итак, давайте перейдем к 4, то следующий элемент в несортированный часть.

26
00:01:57,200 --> 00:02:00,230
Так, где это должно быть помещено в отсортированы часть?

27
00:02:00,230 --> 00:02:04,220
>> Помните, мы хотим поместить это число в определенном порядке

28
00:02:04,220 --> 00:02:08,680
таким образом, наши отсортированы часть остается правильно отсортированный во все времена.

29
00:02:08,680 --> 00:02:14,380
Если мы поместим 4 вправо из 42, то наш список будет в порядке.

30
00:02:14,380 --> 00:02:18,380
Итак, давайте продолжать двигаться справа-слева в наш род часть.

31
00:02:18,380 --> 00:02:23,260
Поскольку мы двигаемся, давайте переложить каждый номер вниз место, чтобы освободить место для нового номера.

32
00:02:25,440 --> 00:02:31,740
Ладно, 4 также меньше, чем 23, поэтому мы не можем поместить его и здесь.

33
00:02:31,740 --> 00:02:34,480
Давайте перейдем на 23 правую одном месте.

34
00:02:36,500 --> 00:02:43,120
>> Это означает, что мы хотели бы разместить 4 в первый слот в отсортированной части.

35
00:02:43,120 --> 00:02:46,300
Обратите внимание, как это место в списке было уже пусто,

36
00:02:46,300 --> 00:02:51,120
потому что мы двигались отсортированы элементы вниз, как мы столкнулись с ними.

37
00:02:51,120 --> 00:02:52,740
Хорошо. Таким образом, мы уже на полпути.

38
00:02:52,740 --> 00:02:57,990
Давайте продолжим наш алгоритм, вставив 16 в отсортированы часть.

39
00:02:59,260 --> 00:03:03,820
Шестнадцать меньше, чем 42, так что давайте переложить 42 до правой.

40
00:03:05,700 --> 00:03:10,190
Шестнадцать также меньше, чем 23, так что давайте также сдвиг этого элемента.

41
00:03:11,790 --> 00:03:20,820
>> Теперь, 16 больше 4. Так что, похоже, мы хотели бы, чтобы вставить 16 между 4 и 23.

42
00:03:20,820 --> 00:03:24,620
При перемещении через отсортированы часть списка справа налево,

43
00:03:24,620 --> 00:03:29,160
4 является первым номером мы видели, что это меньше, чем число

44
00:03:29,160 --> 00:03:31,540
Мы пытаемся вставить.

45
00:03:31,540 --> 00:03:35,820
Итак, теперь мы можем вставить 16 в этом пустом слоте,

46
00:03:35,820 --> 00:03:40,520
который, помните, мы создали на подвижных элементов в род часть более

47
00:03:40,520 --> 00:03:43,340
как мы столкнулись с ними.

48
00:03:43,340 --> 00:03:47,900
>> Хорошо. Теперь у нас есть четыре отсортированы элементов и двух элементов несортированные.

49
00:03:47,900 --> 00:03:51,600
Итак, давайте перейдем 8 в отсортированы часть.

50
00:03:51,600 --> 00:03:55,010
Восемь меньше, чем 42.

51
00:03:55,010 --> 00:03:56,940
Восемь меньше, чем 23.

52
00:03:56,940 --> 00:04:00,230
А 8 меньше, чем 16.

53
00:04:00,230 --> 00:04:03,110
Но 8 больше 4.

54
00:04:03,110 --> 00:04:07,280
Таким образом, мы хотели бы, чтобы вставить 8 между 4 и 16.

55
00:04:09,070 --> 00:04:13,650
А сейчас мы просто еще один элемент оставили для сортировки - 15.

56
00:04:13,950 --> 00:04:16,589
Пятнадцать меньше, чем 42,

57
00:04:16,589 --> 00:04:19,130
Пятнадцать меньше, чем 23.

58
00:04:19,130 --> 00:04:21,750
А 15 меньше, чем 16.

59
00:04:21,750 --> 00:04:24,810
Но 15 больше, чем 8.

60
00:04:24,810 --> 00:04:27,440
>> Итак, вот где мы хотим, чтобы наша конечная вставки.

61
00:04:28,770 --> 00:04:30,330
И мы сделали.

62
00:04:30,330 --> 00:04:33,540
У нас больше нет элементов в несортированный часть,

63
00:04:33,540 --> 00:04:36,670
и наши отсортированы часть находится в правильном порядке.

64
00:04:36,670 --> 00:04:40,270
Номера упорядочены от наименьшего к наибольшему.

65
00:04:40,270 --> 00:04:44,330
Итак, давайте взглянем на некоторые псевдокод, описывающий шаги, которые мы только что выполнили.

66
00:04:46,760 --> 00:04:51,740
>> В строке 1, мы видим, что нам нужно для перебора каждого элемента в списке

67
00:04:51,740 --> 00:04:57,060
кроме первой, так как первый элемент в несортированный часть просто станут

68
00:04:57,060 --> 00:05:00,220
Первый элемент в отсортированной части.

69
00:05:00,220 --> 00:05:06,320
В строках 2 и 3, мы отслеживают наше нынешнее место в несортированный часть.

70
00:05:06,320 --> 00:05:10,450
Элемент представляет собой число мы в настоящее время движется в отсортированы часть,

71
00:05:10,450 --> 00:05:15,600
и J представляет наш индекс в несортированный часть.

72
00:05:15,600 --> 00:05:20,980
>> В строке 4 мы перебора отсортированного часть справа налево.

73
00:05:20,980 --> 00:05:26,010
Мы хотим остановить итерацию раз элемент слева от нашей текущей позиции

74
00:05:26,010 --> 00:05:30,050
меньше, чем элемент, который мы пытаемся вставить.

75
00:05:30,050 --> 00:05:35,600
В строке 5 мы перекладывая каждый элемент мы сталкиваемся одном пространстве с правой стороны.

76
00:05:35,600 --> 00:05:40,950
Таким образом, мы будем иметь свободное пространство для вставки в когда мы находим первый элемент

77
00:05:40,950 --> 00:05:44,080
меньше, чем элемент мы движемся.

78
00:05:44,080 --> 00:05:50,800
В строке 6, мы обновляем счетчик продолжать двигаться налево через отсортированы часть.

79
00:05:50,800 --> 00:05:56,860
Наконец, в строке 7, мы вставка элемента в отсортированный часть списка.

80
00:05:56,860 --> 00:06:00,020
>> Мы знаем, что это нормально для вставки в позицию J,

81
00:06:00,020 --> 00:06:05,360
потому что мы уже переехали элемент, используемый, чтобы быть там одно место вправо.

82
00:06:05,360 --> 00:06:09,460
Помните, что мы движемся через отсортированы часть справа налево,

83
00:06:09,460 --> 00:06:13,960
но мы движемся через несортированные часть слева направо.

84
00:06:13,960 --> 00:06:19,090
Хорошо. Давайте теперь взглянем на то, как долго работает, что алгоритм взял.

85
00:06:19,090 --> 00:06:25,300
Мы сначала задать вопрос, сколько времени потребуется для этого алгоритма для работы в худшем случае.

86
00:06:25,300 --> 00:06:29,040
Напомним, что мы представляем это время работы с большой обозначение O.

87
00:06:32,530 --> 00:06:38,500
Для того, чтобы разобраться наш список, мы были для перебора элементов в несортированный часть,

88
00:06:38,500 --> 00:06:43,430
и для каждого из этих элементов, потенциально над всеми элементами в отсортированной части.

89
00:06:43,430 --> 00:06:47,950
Интуитивно, это звучит как O (N ^ 2) операций.

90
00:06:47,950 --> 00:06:51,840
>> Глядя на нашем псевдокоде, у нас есть цикл вложен в другой цикл,

91
00:06:51,840 --> 00:06:55,290
который, действительно, звучит как O (N ^ 2) операций.

92
00:06:55,290 --> 00:07:01,590
Тем не менее, отсортированные часть списка не содержат весь список до самого конца.

93
00:07:01,590 --> 00:07:06,920
Тем не менее, мы потенциально могли бы вставить новый элемент в самом начале отсортированного часть

94
00:07:06,920 --> 00:07:09,320
на каждой итерации алгоритма,

95
00:07:09,320 --> 00:07:14,500
Это означает, что мы должны смотреть на каждый элемент в настоящее время в отсортированной части.

96
00:07:14,500 --> 00:07:20,090
Таким образом, это означает, что мы потенциально могли бы сделать одно сравнение для второго элемента,

97
00:07:20,090 --> 00:07:24,660
два сравнения для третьего элемента, и так далее.

98
00:07:24,660 --> 00:07:32,480
Таким образом, общее количество шагов является сумма чисел от 1 до длины списка минус 1.

99
00:07:32,480 --> 00:07:35,240
Мы можем представить это с помощью суммирования.

100
00:07:41,170 --> 00:07:47,270
>> Мы не будем вдаваться в суммах здесь, но оказывается, что это суммирование равно

101
00:07:47,270 --> 00:07:57,900
(п - 1) более 2, что эквивалентно п ^ 2/2 - п / 2.

102
00:07:57,900 --> 00:08:00,800
Когда речь идет об асимптотической выполнения,

103
00:08:00,800 --> 00:08:05,170
это п ^ 2 срока будет доминировать в этой п срок.

104
00:08:05,170 --> 00:08:11,430
Таким образом, включение сортировки Big O (N ^ 2).

105
00:08:11,430 --> 00:08:16,150
Что, если мы побежали сортировки вставкой в ​​уже отсортированный список.

106
00:08:16,150 --> 00:08:20,960
В этом случае, мы бы просто создать отсортированный часть слева направо.

107
00:08:20,960 --> 00:08:25,050
Таким образом, мы будем только нужно порядка п шагов.

108
00:08:25,050 --> 00:08:29,740
>> Это означает, что сортировка вставкой имеет лучшем случае выполнения п,

109
00:08:29,740 --> 00:08:34,130
которые мы представляем с Ω (N).

110
00:08:34,130 --> 00:08:36,190
И вот именно для сортировки вставкой,

111
00:08:36,190 --> 00:08:40,429
лишь одна из многих алгоритмов можно использовать для сортировки списка.

112
00:08:40,429 --> 00:08:43,210
Меня зовут Томми, и это CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
О, вы просто не можете остановиться, что как только он начинается.

115
00:09:01,620 --> 00:09:04,760
Да, мы сделали это - >> Boom!