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!