1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Sloučit Třídit]

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
Pojďme mluvit o jakési sloučení.

5
00:00:09,000 --> 00:00:14,000
Zatím jste viděli bubble sort, vložení druhu, a výběr řazení.

6
00:00:14,000 --> 00:00:17,000
I když budu trochu vlny mé ruky na to, co tím myslím lepší,

7
00:00:17,000 --> 00:00:21,000
sloučit druh obecně lepší než některý z těchto 3 druhů.

8
00:00:22,000 --> 00:00:27,000
>> Ale dříve, než mluvit o jakési sloučení, pojďme mluvit o sloučení 2 tříděné seznamy.

9
00:00:27,000 --> 00:00:31,000
Zavoláme proces přijímání 2 tříděné seznamy, jako jsou tyto,

10
00:00:31,000 --> 00:00:35,000
a dělat jeden seřazený seznam z nich - sloučení seznamů.

11
00:00:35,000 --> 00:00:37,750
Jak to můžeme udělat?

12
00:00:37,750 --> 00:00:41,290
No, jeden nápad je jen držet jeden seznam na konci druhého seznamu

13
00:00:41,290 --> 00:00:43,830
a pak třídit výsledný seznam.

14
00:00:43,830 --> 00:00:47,220
>> Zatímco toto funguje, je to hodně zbytečné práce.

15
00:00:47,220 --> 00:00:49,900
Můžeme to udělat rychleji, než jen třídění.

16
00:00:49,900 --> 00:00:54,100
Všimněte si, že jeden špatný nápad, je prostě vzít střídající poháry z každého seznamu.

17
00:00:54,100 --> 00:00:56,460
I když to může vypadat jako to funguje na první,

18
00:00:56,460 --> 00:01:05,760
dělá, že jsme skončili s 4, 8, 15, 23, 16 - oznámení, že 16 a 23 jsou z místa.

19
00:01:05,760 --> 00:01:09,380
To je proto, že 2 prvky, které by měly být uvedeny za sebou ve sloučené seznamu

20
00:01:09,380 --> 00:01:11,720
jsou ve stejné původního seznamu.

21
00:01:11,720 --> 00:01:14,850
Oba 15 a 16 jsou v seznamu na levé straně.

22
00:01:14,850 --> 00:01:19,810
Trik je využít skutečnosti, že oba seznamy jsou již seřazeny.

23
00:01:19,810 --> 00:01:23,320
To znamená, že pokud se jen podívat na první prvky obou seznamů -

24
00:01:23,320 --> 00:01:29,580
zde, 4 a 8 - musí být jeden z nich rovněž být první prvek sloučeného seznamu.

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

26
00:01:31,620 --> 00:01:33,520
Oba tyto seznamy jsou již seřazeny,

27
00:01:33,520 --> 00:01:38,410
a tak buď 4 nebo 8, musí být nejmenší prvek, když spojíme 2 seznamy.

28
00:01:38,410 --> 00:01:41,770
V tomto případě, nejmenší je 4,

29
00:01:41,770 --> 00:01:46,370
takže můžeme vzít ven 4 a dělat to první prvek naší sloučené seznamu.

30
00:01:46,370 --> 00:01:50,710
Nyní budeme pokračovat sloučení zbývající 3 prvky prvního seznamu

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

32
00:01:52,920 --> 00:01:57,150
>> Opět jsme Stačí se podívat na první prvek obou seznamů.

33
00:01:57,150 --> 00:02:01,060
Menší z 2 musí být druhý prvek naší sloučené seznamu.

34
00:02:01,060 --> 00:02:05,440
Tentokrát mezi 8 a 15 nejmenší je 8, a tak jsme se vložit, aby

35
00:02:05,440 --> 00:02:09,240
jako druhý prvek našeho tříděného seznamu.

36
00:02:09,240 --> 00:02:12,180
Můžeme pokračovat v porovnání prvních prvky obou seznamů

37
00:02:12,180 --> 00:02:14,420
a odstranění menší z 2.

38
00:02:14,420 --> 00:02:19,460
Porovnání 15 a 23, 15 je menší, a tak to je naše třetí element.

39
00:02:21,000 --> 00:02:23,910
Nyní srovnání 16 a 23, 16, je menší.

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

41
00:02:26,820 --> 00:02:30,390
>> Všimněte si, že 2 prvky pocházejí ze stejného seznamu v řadě.

42
00:02:30,390 --> 00:02:34,400
To je důvod, proč vzniklý seznam nemůže jen střídají prvky od 2 seznamů.

43
00:02:34,400 --> 00:02:40,020
Porovnání 50 a 23, 23 je menší, tak jsme se rozhodli, že.

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

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

46
00:02:48,290 --> 00:02:52,330
A konečně, musíme jen 108, tak to musí jít na konci našeho seznamu.

47
00:02:53,750 --> 00:02:56,180
Všimněte si, že máme pěkný, seřazený seznam.

48
00:02:56,180 --> 00:02:59,040
Pokaždé, když jsme porovnali první 2 prvky 2 seznamů

49
00:02:59,040 --> 00:03:02,730
jsme byli schopni určit další prvek sloučeného seznamu.

50
00:03:02,730 --> 00:03:08,070
To znamená, že v případě, že konečný seznam obsahuje n čísla, kde n je zde 8,

51
00:03:08,070 --> 00:03:12,610
pak musíme na většině n srovnání dostat všechny z těchto čísel na správné místo.

52
00:03:13,230 --> 00:03:16,230
Takový algoritmus je řekl, aby spuštění v lineárním čase,

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

54
00:03:18,570 --> 00:03:22,810
>> Pomocí našeho algoritmu pro slučování, můžeme udělat rychlý sloučení řazení algoritmus.

55
00:03:22,810 --> 00:03:25,170
Takže, pojďme obnovit naše seznamy.

56
00:03:35,210 --> 00:03:37,750
K dispozici jsou 2 velké kroky v procesu druhu korespondence.

57
00:03:37,750 --> 00:03:41,500
Za prvé, neustále rozdělí seznam šálků do poloviny

58
00:03:41,500 --> 00:03:44,860
dokud nebudeme mít spoustu seznamů pouze s 1 šálkem v nich.

59
00:03:44,860 --> 00:03:47,350
Nebojte se, pokud seznam obsahuje lichý počet

60
00:03:47,350 --> 00:03:49,880
a nemůžete udělat dokonale čistý řez mezi nimi.

61
00:03:49,880 --> 00:03:53,750
Jen libovolně vybrat, které uvádějí, aby zahrnovala další šálek dovnitř

62
00:03:53,750 --> 00:03:56,240
Takže, pojďme rozdělit tyto seznamy.

63
00:03:58,140 --> 00:04:01,310
Nyní máme 2 seznamy.

64
00:04:04,120 --> 00:04:06,570
Nyní máme 4 seznamy.

65
00:04:10,350 --> 00:04:13,870
>> A teď máme 8 seznamů s jedním šálkem v každém seznamu.

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
Pro kroku 2, jsme opakovaně spojí dva seznamy algoritmem sloučení jsme se naučili předtím.

68
00:04:22,230 --> 00:04:29,160
Sloučení 108 a 15, skončíme s přehledem 15, 108.

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

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

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

72
00:04:49,740 --> 00:04:52,450
Nyní jsou všechny naše seznamy jsou velikosti 2.

73
00:04:53,020 --> 00:04:56,180
Všimněte si, že každý z 4 seznamech seřazeny.

74
00:04:56,180 --> 00:04:59,160
>> Takže můžeme začít sloučením dvojice seznamů znovu.

75
00:04:59,160 --> 00:05:03,240
Sloučení 15 a 108 a 4 a 50 -

76
00:05:03,240 --> 00:05:11,170
první přijmout 4, pak 15, pak 50, pak 108.

77
00:05:11,170 --> 00:05:15,120
Sloučení 8, 42 a 16, 23,

78
00:05:15,120 --> 00:05:22,440
nejprve se 8, pak 16, pak 23, pak 42.

79
00:05:22,440 --> 00:05:27,370
Takže teď máme jen 2 seznamy velikosti 4, je seřazena z nichž každý.

80
00:05:27,370 --> 00:05:30,980
Takže teď jsme sloučit tyto 2 seznamy.

81
00:05:30,980 --> 00:05:33,440
Nejprve jsme se na 4.

82
00:05:33,440 --> 00:05:36,580
Pak budeme mít 8.

83
00:05:36,580 --> 00:05:50,700
Pak budeme mít 15 a 16, pak 23, pak 42, pak 50, pak 108.

84
00:05:50,700 --> 00:05:52,220
A jsme hotovi.

85
00:05:52,220 --> 00:05:54,900
Nyní máme seřazený seznam.

86
00:05:54,900 --> 00:05:57,890
Tak, jak rychle to bylo přesně?

87
00:05:57,890 --> 00:06:02,000
Z technického hlediska, sloučení sort je O (n log n),

88
00:06:02,000 --> 00:06:07,380
vzhledem k tomu, všechny bubliny druhu, vložení seřadit, a výběr druhu jsou O (n ²).

89
00:06:07,380 --> 00:06:11,120
Ve skutečnosti, jak budete brzy naučí, nebudete schopni přijít s jakýmsi

90
00:06:11,120 --> 00:06:14,820
že jsou lepší než O (n log n) v obecném případě.

91
00:06:14,820 --> 00:06:19,120
Opět, nebojte se o této velké O notace, pokud jste ho ještě neviděli ještě.

92
00:06:19,120 --> 00:06:23,490
>> Jen vím, že to znamená, že pokud bychom chtěli seřadit opravdu velký seznam

93
00:06:23,490 --> 00:06:26,820
bublina sort, vložení sort, a výběr sort by mohl mít

94
00:06:26,820 --> 00:06:29,500
podstatně déle než sloučení řazení.

95
00:06:29,500 --> 00:06:33,210
To neznamená, že sloučení třídění bude rychlejší pro všechny seznamy

96
00:06:33,210 --> 00:06:36,220
nebo dokonce pro každou jednotlivou seznamu pod určité velikosti.

97
00:06:36,220 --> 00:06:41,950
Například, může vložení druh nejrychlejší řazení pro všech seznamů menší než 5 prvků.

98
00:06:41,950 --> 00:06:47,360
V praxi, sloučení druh je obvykle rychlejší seznamy jak malý jako 50 prvků.

99
00:06:47,360 --> 00:06:51,120
>> Ale to navíc rychlost nepřijde bez ceny.

100
00:06:51,120 --> 00:06:54,770
Na rozdíl od našich ostatních druhů, které se v seznamu a upravit seznam v místě

101
00:06:54,770 --> 00:06:58,740
dokud nebudeme mít seřazený seznam, merge sort potřebuje další místo

102
00:06:58,740 --> 00:07:00,900
sloučit 2 seznamy dohromady.

103
00:07:00,900 --> 00:07:04,690
Nemůžeme ihned používat seznamy, které jsou sloučeny uložit sloučený seznam

104
00:07:04,690 --> 00:07:08,880
protože bychom mohli přepsat prvky, které ještě potřebují být sloučeny.

105
00:07:08,880 --> 00:07:13,540
Tento prostor je trochu cenu, ale to obvykle není nepřiměřené.

106
00:07:13,540 --> 00:07:15,330
A to je pro druh korespondence.

107
00:07:15,330 --> 00:07:18,490
>> Mé jméno 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ýběr druhu.

110
00:07:24,000 --> 00:07:25,880
[Smích]

111
00:07:25,880 --> 00:07:31,480
Oh, musím vzít, že příliš, protože jsem přešel, jak jsem byl, že ho představuje.

112
00:07:31,480 --> 00:07:35,680
Seznamu na levé straně. To byl překlep.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] I podělal -

114
00:07:39,290 --> 00:07:41,190
[Smích]

115
00:07:41,190 --> 00:07:44,190
Já nevím, co -