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 i 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
2 параўнання для трэцяга элемента, і гэтак далей.

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!