1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Убацивања Сортирај]

2
00:00:02,290 --> 00:00:04,240
[Томми МацВиллиам] [Универзитет Харвард]

3
00:00:04,240 --> 00:00:07,290
[Ово је ЦС50.ТВ]

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
и ј представља нашу индекс у некласификовани дела.

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
>> Знамо да је у реду да убаците у положај ј,

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
Подсетимо се да заступамо ову време рада са великим О нотацији.

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
Интуитивно, ово звучи као О (н ^ 2) рада.

90
00:06:47,950 --> 00:06:51,840
>> Гледајући наше Псеудокод, имамо петљу угнежђену у другој петље,

91
00:06:51,840 --> 00:06:55,290
који је, заиста, звучи као О (н ^ 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
Дакле, убацивање врста је велики О (н ^ 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
које представљају са Ω (н).

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
Моје име је Томи, а ово је ЦС50.

113
00:08:43,210 --> 00:08:44,880
[ЦС50.ТВ]

114
00:08:46,110 --> 00:08:49,230
Ох, не могу да престанем да једном када почне.

115
00:09:01,620 --> 00:09:04,760
Ох, то смо урадили - >> Бум!