1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Мерге Сорт]

2
00:00:02,000 --> 00:00:04,000
[Роб Бовден - Универзитет Харвард]

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

4
00:00:07,000 --> 00:00:09,000
Хајде да причамо о стапања врсте.

5
00:00:09,000 --> 00:00:14,000
До сада сте видели балон врсте, уметања сортирате, а избор сортирања.

6
00:00:14,000 --> 00:00:17,000
Иако ћу некако таласа моју руку на шта мислим и боље,

7
00:00:17,000 --> 00:00:21,000
споји некако генерално обавља боље него било који од ова 3 врсте.

8
00:00:22,000 --> 00:00:27,000
>> Али пре него што говоримо о врсти стапања, хајде да разговарамо о спајању 2 сортиране листе.

9
00:00:27,000 --> 00:00:31,000
Ми ћемо позвати процес узимања 2 сортиране листе, као што су ови,

10
00:00:31,000 --> 00:00:35,000
и чинећи јединствену сортирани списак од њих - спајањем листе.

11
00:00:35,000 --> 00:00:37,750
Како можемо да урадимо ово?

12
00:00:37,750 --> 00:00:41,290
Па, једна од идеја је да се држимо само једну листу на крају друге листе

13
00:00:41,290 --> 00:00:43,830
а затим сортирати резултујућу листу.

14
00:00:43,830 --> 00:00:47,220
>> Док ово ради, то је много непотребног посла.

15
00:00:47,220 --> 00:00:49,900
Можемо то да урадимо брже него само сортирање.

16
00:00:49,900 --> 00:00:54,100
Приметите да један погрешан идеја је да се узме само наизменично шоље са сваке листе.

17
00:00:54,100 --> 00:00:56,460
Иако то може да изгледа као да радови на први поглед,

18
00:00:56,460 --> 00:01:05,760
радили да смо завршили са 4, 8, 15, 23, 16 - обавештења да је 16 и 23 су на месту.

19
00:01:05,760 --> 00:01:09,380
То је зато 2 елемента који би требало да се појављују узастопна у обједињеном листи

20
00:01:09,380 --> 00:01:11,720
у истој почетној листи.

21
00:01:11,720 --> 00:01:14,850
Оба 15 и 16 у листи са леве стране.

22
00:01:14,850 --> 00:01:19,810
Трик је у томе да се искористе чињеницу да су оба листа већ сортира.

23
00:01:19,810 --> 00:01:23,320
То значи да, ако погледамо на прве елементе обе листе -

24
00:01:23,320 --> 00:01:29,580
Овде, 4 и 8 - један од њих мора бити први елемент спојеног листе.

25
00:01:29,580 --> 00:01:31,620
Па, зашто је то тако?

26
00:01:31,620 --> 00:01:33,520
Обе листе су већ сортиран,

27
00:01:33,520 --> 00:01:38,410
па било 4 или 8 мора бити најмањи елеменат када комбинујемо 2 листа.

28
00:01:38,410 --> 00:01:41,770
У овом случају, најмања је 4,

29
00:01:41,770 --> 00:01:46,370
тако да можемо да изваде 4 и постане први елемент наше спојеном листе.

30
00:01:46,370 --> 00:01:50,710
Сада настављамо спајањем преостале 3 елемената прве листе

31
00:01:50,710 --> 00:01:52,920
и 4 елементи другој листи.

32
00:01:52,920 --> 00:01:57,150
>> Још једном, ми само треба да погледамо на првом елементу обе листе.

33
00:01:57,150 --> 00:02:01,060
Мањи од 2 мора бити Други елемент нашег спојеном листе.

34
00:02:01,060 --> 00:02:05,440
Овај пут, између 8 и 15 најмања је 8, па смо убацили да

35
00:02:05,440 --> 00:02:09,240
као други елемент нашег сортиране листе.

36
00:02:09,240 --> 00:02:12,180
Можемо да наставимо упоређујући прве елементе обе листе

37
00:02:12,180 --> 00:02:14,420
и отклањање мањих од 2.

38
00:02:14,420 --> 00:02:19,460
Упоређујући 15 и 23, 15 је мања па то је наш трећи елемент.

39
00:02:21,000 --> 00:02:23,910
Сада упоређујући 16 и 23, 16 је мањи.

40
00:02:23,910 --> 00:02:26,820
Дакле, то је четврти елемент.

41
00:02:26,820 --> 00:02:30,390
>> Приметимо да су 2 елемента дошао из исте листе за редом.

42
00:02:30,390 --> 00:02:34,400
То је разлог зашто обједињена листа не може само смењују елементи из 2 листа.

43
00:02:34,400 --> 00:02:40,020
Упоређујући 50 и 23, 23 је мања, тако да бирамо.

44
00:02:40,770 --> 00:02:44,070
Између 50 и 42, 42 је мањи.

45
00:02:44,070 --> 00:02:48,290
Између 50 и 108, 50 је мањи.

46
00:02:48,290 --> 00:02:52,330
И, коначно, имамо само 108, тако да мора да иде на крају наше листе.

47
00:02:53,750 --> 00:02:56,180
Приметите да имамо лепу, сортиране листе.

48
00:02:56,180 --> 00:02:59,040
Сваки пут смо упоредили прва 2 елементе 2 листа

49
00:02:59,040 --> 00:03:02,730
ми смо били у стању да одреди следеће елемент спојеног листе.

50
00:03:02,730 --> 00:03:08,070
То значи да ако коначна листа садржи бројеве н, где је н овде је 8,

51
00:03:08,070 --> 00:03:12,610
онда морамо највике н поређења да се све те бројеве на правом месту.

52
00:03:13,230 --> 00:03:16,230
Такав алгоритам се каже да раде у линеарном времену,

53
00:03:16,230 --> 00:03:18,090
али не брините о томе овде.

54
00:03:18,570 --> 00:03:22,810
>> Користећи наш алгоритам за спајање, можемо направити брзо стапања сортирања алгоритам.

55
00:03:22,810 --> 00:03:25,170
Дакле, хајде да поново наше листе.

56
00:03:35,210 --> 00:03:37,750
Постоје 2 велике кораке у процесу стапања врсте.

57
00:03:37,750 --> 00:03:41,500
Прво, стално поделити листу куповима у пола

58
00:03:41,500 --> 00:03:44,860
док имамо гомилу листа са само 1 шоља у њима.

59
00:03:44,860 --> 00:03:47,350
Не брините ако листа садржи непаран број

60
00:03:47,350 --> 00:03:49,880
и не може да направи савршено чист рез између њих.

61
00:03:49,880 --> 00:03:53,750
Само произвољно одабрати која листа да укључи додатну шољу унутра

62
00:03:53,750 --> 00:03:56,240
Дакле, хајде да поделите ове листе.

63
00:03:58,140 --> 00:04:01,310
Сада имамо 2 листа.

64
00:04:04,120 --> 00:04:06,570
Сада имамо 4 листа.

65
00:04:10,350 --> 00:04:13,870
>> И сада имамо 8 листе са једним купу у свакој листи.

66
00:04:13,870 --> 00:04:16,630
Дакле, то је то за корак 1.

67
00:04:16,630 --> 00:04:22,230
За корак 2, ми смо у више наврата обједињавање пара листа помоћу стапања алгоритам смо научили раније.

68
00:04:22,230 --> 00:04:29,160
Спајање 108 и 15, завршимо са листе 15, 108.

69
00:04:30,330 --> 00:04:36,250
Спајање 50 и 4, завршимо са 4, 50.

70
00:04:36,960 --> 00:04:41,400
Спајање 8 и 42, можемо завршити са 8, 42.

71
00:04:42,790 --> 00:04:48,130
И спајањем 23 и 16, можемо завршити са 16, 23.

72
00:04:49,740 --> 00:04:52,450
Сада сви наши спискови су величине 2.

73
00:04:53,020 --> 00:04:56,180
Приметите да сваки од 4 листа је сортирана.

74
00:04:56,180 --> 00:04:59,160
>> Дакле, можемо почети поново спајање парова листама.

75
00:04:59,160 --> 00:05:03,240
Спајање 15 и 108 и 4 и 50 -

76
00:05:03,240 --> 00:05:11,170
Прво узми 4, затим 15, па на 50, затим 108.

77
00:05:11,170 --> 00:05:15,120
Спајање 8, 42 и 16, 23,

78
00:05:15,120 --> 00:05:22,440
прво узме 8, затим 16, затим 23, затим 42.

79
00:05:22,440 --> 00:05:27,370
Дакле, сада имамо само 2 листе величине 4, од којих је сваки сортирају.

80
00:05:27,370 --> 00:05:30,980
Дакле, сада смо споји ове 2 листе.

81
00:05:30,980 --> 00:05:33,440
Прво узмемо 4.

82
00:05:33,440 --> 00:05:36,580
Онда узмемо 8.

83
00:05:36,580 --> 00:05:50,700
Онда узмемо 15 и 16, затим 23, затим 42, затим 50, затим 108.

84
00:05:50,700 --> 00:05:52,220
И ми смо урадили.

85
00:05:52,220 --> 00:05:54,900
Ми сада имамо сортиран списак.

86
00:05:54,900 --> 00:05:57,890
Дакле, колико брзо је ово тачно?

87
00:05:57,890 --> 00:06:02,000
У техничком смислу, обједињавање врста је О (н лог н)

88
00:06:02,000 --> 00:06:07,380
док сви балон врсте, уметања сортирање и избор сортирање су О (н ²).

89
00:06:07,380 --> 00:06:11,120
У ствари, као што ћете ускоро научити, нећете бити у могућности да дођу до неке врсте

90
00:06:11,120 --> 00:06:14,820
које обавља боље од О (н лог н) у општем случају.

91
00:06:14,820 --> 00:06:19,120
Опет, не брините о овом великом О нотацији, ако нисте видели још.

92
00:06:19,120 --> 00:06:23,490
>> Само знам да ово значи да смо желели да сортирате заиста велики списак

93
00:06:23,490 --> 00:06:26,820
мехур сортирање, убацивање сортирање, сортирање и селекција могла потенцијално узети

94
00:06:26,820 --> 00:06:29,500
знатно дуже него обједињавање врсту.

95
00:06:29,500 --> 00:06:33,210
То не значи да ће обједињавање нека буде брже свим листама

96
00:06:33,210 --> 00:06:36,220
или чак и за сваку појединачну листу под одређене величине.

97
00:06:36,220 --> 00:06:41,950
На пример, уметање некако могао бити најбржи врста свих спискова мање од 5 елемената.

98
00:06:41,950 --> 00:06:47,360
У пракси, обједињавање врста обично је бржи за листе као мали као 50 елемената.

99
00:06:47,360 --> 00:06:51,120
>> Али ово екстра брзине не долази без цене.

100
00:06:51,120 --> 00:06:54,770
За разлику од наших других врста, које узимају листу и измените листу у месту

101
00:06:54,770 --> 00:06:58,740
док не добијемо сортирани списак, обједињавања некако треба неки додатни простор

102
00:06:58,740 --> 00:07:00,900
заједно споји 2 листа.

103
00:07:00,900 --> 00:07:04,690
Ми не можемо одмах да користите листе које су стопљене за чување обједињену листу

104
00:07:04,690 --> 00:07:08,880
јер смо могли заменити елементе који још увек треба да се споје.

105
00:07:08,880 --> 00:07:13,540
Овај простор је мало цени, али то обично није неразуман.

106
00:07:13,540 --> 00:07:15,330
И то је то за стапања врсте.

107
00:07:15,330 --> 00:07:18,490
>> Моје име је Роб Бовден, а ово је ЦС50.

108
00:07:18,490 --> 00:07:20,500
[ЦС50.ТВ]

109
00:07:20,500 --> 00:07:24,000
- И избор врсте.

110
00:07:24,000 --> 00:07:25,880
[Смех]

111
00:07:25,880 --> 00:07:31,480
Ох, морам да претпоставим да се превише, јер сам се пребацио како сам представљајући га.

112
00:07:31,480 --> 00:07:35,680
Списак са леве стране. То је грешка у куцању.

113
00:07:35,680 --> 00:07:39,290
[Лапсус] Ја зезнуо -

114
00:07:39,290 --> 00:07:41,190
[Смех]

115
00:07:41,190 --> 00:07:44,190
Ја не знам шта је -