1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Zlúčiť Triediť]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[To je CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Poďme hovoriť o akejsi zlúčenie.

5
00:00:09,000 --> 00:00:14,000
Zatiaľ ste videli bubble sort, vloženie druhu, a výber radenie.

6
00:00:14,000 --> 00:00:17,000
Aj keď budem trochu vlny mojej ruky na to, čo tým myslím lepšie,

7
00:00:17,000 --> 00:00:21,000
zlúčiť druh všeobecne lepší ako niektorý z týchto 3 druhov.

8
00:00:22,000 --> 00:00:27,000
>> Ale skôr, než hovoriť o akejsi zlúčenie, poďme hovoriť o zlúčenie 2 triedené zoznamy.

9
00:00:27,000 --> 00:00:31,000
Zavoláme proces prijímania 2 triedené zoznamy, ako sú tieto,

10
00:00:31,000 --> 00:00:35,000
a robiť jeden zoradený zoznam z nich - zlúčenie zoznamov.

11
00:00:35,000 --> 00:00:37,750
Ako to môžeme urobiť?

12
00:00:37,750 --> 00:00:41,290
No, jeden nápad je len držať jeden zoznam na konci druhého zoznamu

13
00:00:41,290 --> 00:00:43,830
a potom triediť výsledný zoznam.

14
00:00:43,830 --> 00:00:47,220
>> Zatiaľ čo toto funguje, je to veľa zbytočnej práce.

15
00:00:47,220 --> 00:00:49,900
Môžeme to urobiť rýchlejšie, než len triedenie.

16
00:00:49,900 --> 00:00:54,100
Všimnite si, že jeden zlý nápad, je jednoducho vziať striedajúci poháre z každého zoznamu.

17
00:00:54,100 --> 00:00:56,460
Aj keď to môže vyzerať ako to funguje na prvý,

18
00:00:56,460 --> 00:01:05,760
robí, že sme skončili s 4, 8, 15, 23, 16 - oznámenie, že 16 a 23 sú z miesta.

19
00:01:05,760 --> 00:01:09,380
To je preto, že 2 prvky, ktoré by mali byť uvedené za sebou v zlúčenej zoznamu

20
00:01:09,380 --> 00:01:11,720
sú v rovnakej pôvodného zoznamu.

21
00:01:11,720 --> 00:01:14,850
Obaja 15 a 16 sú v zozname na ľavej strane.

22
00:01:14,850 --> 00:01:19,810
Trik je využiť skutočnosť, že oba zoznamy sú už zoradené.

23
00:01:19,810 --> 00:01:23,320
To znamená, že ak sa len pozrieť na prvé prvky oboch zoznamov -

24
00:01:23,320 --> 00:01:29,580
tu, 4 a 8 - musí byť jeden z nich byť aj prvý prvok zlúčeného zoznamu.

25
00:01:29,580 --> 00:01:31,620
No, prečo to je?

26
00:01:31,620 --> 00:01:33,520
Oba tieto zoznamy sú už zoradené,

27
00:01:33,520 --> 00:01:38,410
a tak buď 4 alebo 8, musí byť najmenší prvok, keď spojíme 2 zoznamy.

28
00:01:38,410 --> 00:01:41,770
V tomto prípade, najmenší je 4,

29
00:01:41,770 --> 00:01:46,370
takže môžeme vziať von 4 a robiť to prvý prvok našej zlúčené zoznamu.

30
00:01:46,370 --> 00:01:50,710
Teraz budeme pokračovať zlúčenie zvyšné 3 prvky prvého zoznamu

31
00:01:50,710 --> 00:01:52,920
a 4 prvky druhého zoznamu.

32
00:01:52,920 --> 00:01:57,150
>> Opäť sme Stačí sa pozrieť na prvý prvok oboch zoznamov.

33
00:01:57,150 --> 00:02:01,060
Menší z 2 musí byť druhý prvok našej zlúčené zoznamu.

34
00:02:01,060 --> 00:02:05,440
Tentoraz medzi 8 a 15 najmenších je 8, a tak sme sa vložiť, aby

35
00:02:05,440 --> 00:02:09,240
ako druhý prvok nášho triedeného zoznamu.

36
00:02:09,240 --> 00:02:12,180
Môžeme pokračovať v porovnaní prvých prvky oboch zoznamov

37
00:02:12,180 --> 00:02:14,420
a odstránenie menšie z 2.

38
00:02:14,420 --> 00:02:19,460
Porovnanie 15 a 23, 15 je menšie, a tak to je naša tretia element.

39
00:02:21,000 --> 00:02:23,910
Teraz porovnaní 16 a 23, 16, je menšia.

40
00:02:23,910 --> 00:02:26,820
Tak to je štvrtý element.

41
00:02:26,820 --> 00:02:30,390
>> Všimnite si, že 2 prvky pochádzajú z rovnakého zoznamu v rade.

42
00:02:30,390 --> 00:02:34,400
To je dôvod, prečo by nový zoznam nemôže len striedajú prvky od 2 zoznamov.

43
00:02:34,400 --> 00:02:40,020
Porovnanie 50 a 23, 23 je menší, tak sme sa rozhodli, že.

44
00:02:40,770 --> 00:02:44,070
Medzi 50 a 42, 42 je menší.

45
00:02:44,070 --> 00:02:48,290
Medzi 50 a 108, 50 je menší.

46
00:02:48,290 --> 00:02:52,330
A konečne, musíme len 108, tak to musí ísť na konci nášho zoznamu.

47
00:02:53,750 --> 00:02:56,180
Všimnite si, že máme pekný, zoradený zoznam.

48
00:02:56,180 --> 00:02:59,040
Zakaždým, keď sme porovnali prvé 2 prvky 2 zoznamov

49
00:02:59,040 --> 00:03:02,730
sme boli schopní určiť ďalší prvok zlúčeného zoznamu.

50
00:03:02,730 --> 00:03:08,070
To znamená, že v prípade, že konečný zoznam obsahuje n čísla, kde n je tu 8,

51
00:03:08,070 --> 00:03:12,610
potom musíme na väčšine n porovnaní dostať všetky z týchto čísel na správne miesto.

52
00:03:13,230 --> 00:03:16,230
Takýto algoritmus je povedal, aby spustenie v lineárnom čase,

53
00:03:16,230 --> 00:03:18,090
ale nebojte sa o tom tu.

54
00:03:18,570 --> 00:03:22,810
>> Pomocou nášho algoritmu pre zlučovanie, môžeme urobiť rýchly zlúčenie radenie algoritmus.

55
00:03:22,810 --> 00:03:25,170
Takže, poďme obnoviť naše zoznamy.

56
00:03:35,210 --> 00:03:37,750
K dispozícii sú 2 veľké kroky v procese druhu korešpondencie.

57
00:03:37,750 --> 00:03:41,500
Po prvé, neustále rozdelí zoznam šálok do polovice

58
00:03:41,500 --> 00:03:44,860
kým nebudeme mať veľa zoznamov iba s 1 šálkou v nich.

59
00:03:44,860 --> 00:03:47,350
Nebojte sa, ak zoznam obsahuje nepárny počet

60
00:03:47,350 --> 00:03:49,880
a nemôžete urobiť dokonale čistý rez medzi nimi.

61
00:03:49,880 --> 00:03:53,750
Len ľubovoľne vybrať, ktorú Zoznam zahrnúť ďalšie šálku dovnútra

62
00:03:53,750 --> 00:03:56,240
Takže, poďme rozdeliť tieto zoznamy.

63
00:03:58,140 --> 00:04:01,310
Teraz máme 2 zoznamy.

64
00:04:04,120 --> 00:04:06,570
Teraz máme 4 zoznamy.

65
00:04:10,350 --> 00:04:13,870
>> A teraz máme 8 zoznamov s jedným šálkou v každom zozname.

66
00:04:13,870 --> 00:04:16,630
Tak to je to v 1. kroku.

67
00:04:16,630 --> 00:04:22,230
Pre kroku 2, sme opakovane spojí dva zoznamy algoritmom zlúčenie sme sa naučili predtým.

68
00:04:22,230 --> 00:04:29,160
Zlúčenie 108 a 15, skončíme s prehľadom 15, 108.

69
00:04:30,330 --> 00:04:36,250
Zlúčenie 50 a 4, skončíme s 4, 50.

70
00:04:36,960 --> 00:04:41,400
Zlúčenie 8 a 42, skončíme s 8, 42.

71
00:04:42,790 --> 00:04:48,130
A zlúčenie 23 a 16, skončíme s 16, 23.

72
00:04:49,740 --> 00:04:52,450
Teraz sú všetky naše zoznamy sú veľkosti 2.

73
00:04:53,020 --> 00:04:56,180
Všimnite si, že každý z 4 zoznamoch zoradené.

74
00:04:56,180 --> 00:04:59,160
>> Takže môžeme začať zlúčením dvojice zoznamov znova.

75
00:04:59,160 --> 00:05:03,240
Zlúčenie 15 a 108 a 4 a 50 -

76
00:05:03,240 --> 00:05:11,170
prvý prijať 4, potom 15, potom 50, potom 108.

77
00:05:11,170 --> 00:05:15,120
Zlúčenie 8, 42 a 16, 23,

78
00:05:15,120 --> 00:05:22,440
najprv sa 8, potom 16, potom 23, potom 42.

79
00:05:22,440 --> 00:05:27,370
Takže teraz máme len 2 zoznamy veľkosti 4, je zoradená z ktorých každý.

80
00:05:27,370 --> 00:05:30,980
Takže teraz sme zlúčiť tieto 2 zoznamy.

81
00:05:30,980 --> 00:05:33,440
Najprv sme sa na 4.

82
00:05:33,440 --> 00:05:36,580
Potom budeme mať 8.

83
00:05:36,580 --> 00:05:50,700
Potom budeme mať 15 a 16, potom 23, potom 42, potom 50, potom 108.

84
00:05:50,700 --> 00:05:52,220
A sme hotoví.

85
00:05:52,220 --> 00:05:54,900
Teraz máme zoradený zoznam.

86
00:05:54,900 --> 00:05:57,890
Tak, ako rýchlo to bolo presne?

87
00:05:57,890 --> 00:06:02,000
Z technického hľadiska, zlúčenie sort je O (n log n),

88
00:06:02,000 --> 00:06:07,380
vzhľadom k tomu, všetky bubliny druhu, vloženie zoradiť, a výber druhu sú O (n ²).

89
00:06:07,380 --> 00:06:11,120
V skutočnosti, ako budete čoskoro naučí, nebudete schopní prísť s akýmsi

90
00:06:11,120 --> 00:06:14,820
že sú lepšie ako O (n log n) vo všeobecnom prípade.

91
00:06:14,820 --> 00:06:19,120
Opäť, nebojte sa o tejto veľkej O notácie, ak ste ho ešte nevideli ešte.

92
00:06:19,120 --> 00:06:23,490
>> Len viem, že to znamená, že ak by sme chceli usporiadať naozaj veľký zoznam

93
00:06:23,490 --> 00:06:26,820
bublina sort, vloženie sort, a výber sort by mohol mať

94
00:06:26,820 --> 00:06:29,500
podstatne dlhšie než zlúčenie radenie.

95
00:06:29,500 --> 00:06:33,210
To neznamená, že zlúčenie triedenie bude rýchlejší pre všetky zoznamy

96
00:06:33,210 --> 00:06:36,220
alebo dokonca pre každú jednotlivú zoznamu pod určitej veľkosti.

97
00:06:36,220 --> 00:06:41,950
Napríklad, môže vloženie druh najrýchlejší radenia pre všetkých zoznamov menšie ako 5 prvkov.

98
00:06:41,950 --> 00:06:47,360
V praxi, zlúčenie druh je zvyčajne rýchlejší zoznamy ako malý ako 50 prvkov.

99
00:06:47,360 --> 00:06:51,120
>> Ale to navyše rýchlosť nepríde bez ceny.

100
00:06:51,120 --> 00:06:54,770
Na rozdiel od našich ostatných druhov, ktoré sa v zozname a upraviť zoznam v mieste

101
00:06:54,770 --> 00:06:58,740
kým nebudeme mať usporiadaný zoznam, merge sort potrebuje ďalšie miesto

102
00:06:58,740 --> 00:07:00,900
zlúčiť 2 zoznamy dohromady.

103
00:07:00,900 --> 00:07:04,690
Nemôžeme ihneď používať zoznamy, ktoré sú zlúčené uložiť zlúčený zoznam

104
00:07:04,690 --> 00:07:08,880
pretože by sme mohli prepísať prvky, ktoré ešte potrebujú byť zlúčené.

105
00:07:08,880 --> 00:07:13,540
Tento priestor je trochu cenu, ale to zvyčajne nie je neprimerané.

106
00:07:13,540 --> 00:07:15,330
A to je pre druh korešpondencie.

107
00:07:15,330 --> 00:07:18,490
>> Moje meno je Rob Bowden, a to je CS50.

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

109
00:07:20,500 --> 00:07:24,000
- A výber druhu.

110
00:07:24,000 --> 00:07:25,880
[Smiech]

111
00:07:25,880 --> 00:07:31,480
Oh, musím vziať, že príliš, pretože som prešiel, ako som bol, že ho predstavuje.

112
00:07:31,480 --> 00:07:35,680
Zoznamu na ľavej strane. To bol preklep.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] I podelal -

114
00:07:39,290 --> 00:07:41,190
[Smiech]

115
00:07:41,190 --> 00:07:44,190
Ja neviem, čo -