1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Сартаванне зліццём]

2
00:00:02,000 --> 00:00:04,000
[Rob Боуден - Гарвардскі універсітэт]

3
00:00:04,000 --> 00:00:07,000
[Гэта CS50. - CS50.TV]

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
З тэхнічнага пункту гледжання, зліццё сартавання O (п § п),

88
00:06:02,000 --> 00:06:07,380
у той час як усе пузырьковый сартавання, сартавання устаўкай, і выбар роду з'яўляюцца O (N ²).

89
00:06:07,380 --> 00:06:11,120
На самай справе, як вы даведаецеся ў бліжэйшы час, вы не зможаце прыдумаць свайго роду

90
00:06:11,120 --> 00:06:14,820
, Што працуе лепш, чым O (п § п) у агульным выпадку.

91
00:06:14,820 --> 00:06:19,120
Зноў жа, не турбуйцеся аб гэтым вялікім пазначэнне O, калі вы яго яшчэ не бачыла.

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
>> Мяне клічуць Боб Боуден, і гэта CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

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
Я не ведаю, што -