1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Merge Sort]

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

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

4
00:00:07,000 --> 00:00:09,000
Beszéljünk merge sort.

5
00:00:09,000 --> 00:00:14,000
Eddig láttad buborék rendezés, beszúrásos rendezés, és a kiválasztás sort.

6
00:00:14,000 --> 00:00:17,000
Bár Majd egyfajta hullám kezem, mit gondolok a jobb,

7
00:00:17,000 --> 00:00:21,000
merge sort általában jobban teljesít, mint bármelyik a 3 fajta.

8
00:00:22,000 --> 00:00:27,000
>> De mielőtt beszélünk merge sort, beszéljünk egyesülő 2 rendezett listákat.

9
00:00:27,000 --> 00:00:31,000
Hívjuk a folyamat figyelembe 2 rendezett listákat, mint ezek,

10
00:00:31,000 --> 00:00:35,000
és így egy rendezett listát ki őket - összevonása a listák.

11
00:00:35,000 --> 00:00:37,750
Hogyan tudjuk ezt megtenni?

12
00:00:37,750 --> 00:00:41,290
Nos, az egyik cél az, hogy csak kibír egy lista rá a végén a másik lista

13
00:00:41,290 --> 00:00:43,830
sort, majd a kapott listát.

14
00:00:43,830 --> 00:00:47,220
>> Bár ez működik, ez egy csomó felesleges munka.

15
00:00:47,220 --> 00:00:49,900
Meg tudjuk csinálni gyorsabban, mint válogatás.

16
00:00:49,900 --> 00:00:54,100
Figyeljük meg, hogy egy rossz ötlet, hogy csak úgy váltakozó kupák minden listáról.

17
00:00:54,100 --> 00:00:56,460
Bár ez tűnhet, hogy a munkálatok az első,

18
00:00:56,460 --> 00:01:05,760
ezzel, hogy a végén a 4, 8, 15, 23, 16 - nyilatkozat, hogy 16 és 23 van a helyén.

19
00:01:05,760 --> 00:01:09,380
Ennek az az oka, hogy a 2 elem jelenjen meg egymás után az egyesített listán

20
00:01:09,380 --> 00:01:11,720
ugyanabban az eredeti listában.

21
00:01:11,720 --> 00:01:14,850
Mind a 15 és 16 van a listán a bal oldalon.

22
00:01:14,850 --> 00:01:19,810
A trükk az, hogy kihasználja azt a tényt, hogy mindkét lista már rendezve.

23
00:01:19,810 --> 00:01:23,320
Ez azt jelenti, hogy ha csak nézd meg az első elemeit egyaránt listák -

24
00:01:23,320 --> 00:01:29,580
Itt, 4 és 8 - egyikük is kell az első eleme az új lista.

25
00:01:29,580 --> 00:01:31,620
Nos, miért van ez?

26
00:01:31,620 --> 00:01:33,520
Mindkét listák már rendezve,

27
00:01:33,520 --> 00:01:38,410
és így 4 vagy 8 kell, hogy legyen a legkisebb elem, ha kombináljuk a 2 lista.

28
00:01:38,410 --> 00:01:41,770
Ebben az esetben, a legkisebb a 4,

29
00:01:41,770 --> 00:01:46,370
így tudjuk kivenni 4, és ez az első eleme egyesített listán.

30
00:01:46,370 --> 00:01:50,710
Most tovább egyesülő fennmaradó 3 elem az első lista

31
00:01:50,710 --> 00:01:52,920
és 4 elemeit a második listán.

32
00:01:52,920 --> 00:01:57,150
>> Még egyszer, csak meg kell nézni az első elemet mindkét listát.

33
00:01:57,150 --> 00:02:01,060
Minél kisebb a 2 kell, hogy legyen a második eleme egyesített listán.

34
00:02:01,060 --> 00:02:05,440
Ez alkalommal, 8 és 15 a legkisebb 8, és így be az

35
00:02:05,440 --> 00:02:09,240
a második eleme a rendezett lista.

36
00:02:09,240 --> 00:02:12,180
Mi továbbra is összehasonlítjuk az első elemeit egyaránt listák

37
00:02:12,180 --> 00:02:14,420
és eltávolítása a kisebb a 2.

38
00:02:14,420 --> 00:02:19,460
Összehasonlítása 15. és 23, 15 kisebb, és annak érdekében, hogy azon a harmadik elem.

39
00:02:21,000 --> 00:02:23,910
Most összehasonlítása 16. és 23., a 16 kisebb.

40
00:02:23,910 --> 00:02:26,820
Szóval ez a negyedik elem.

41
00:02:26,820 --> 00:02:30,390
>> Figyeljük meg, hogy 2 elem származik az ugyanazon a listán a sorban.

42
00:02:30,390 --> 00:02:34,400
Ezért az összefonódással lista nem csupán alternatív elemeket a 2 listákból.

43
00:02:34,400 --> 00:02:40,020
Összehasonlítva 50 és 23, 23 kisebb, ezért úgy döntünk, hogy.

44
00:02:40,770 --> 00:02:44,070
50 és 42, 42 kisebb.

45
00:02:44,070 --> 00:02:48,290
Az 50 és 108, 50 kisebb.

46
00:02:48,290 --> 00:02:52,330
És végül már csak 108, így kell menni a végén a mi listáját.

47
00:02:53,750 --> 00:02:56,180
Figyeljük meg, hogy van egy szép, rendezett listát.

48
00:02:56,180 --> 00:02:59,040
Minden alkalommal, amikor összehasonlítottuk az első 2 elem a 2 listák

49
00:02:59,040 --> 00:03:02,730
tudtuk meghatározni a következő eleme az új lista.

50
00:03:02,730 --> 00:03:08,070
Ez azt jelenti, hogy amennyiben a végleges lista n szám, ahol n itt 8,

51
00:03:08,070 --> 00:03:12,610
akkor meg kell legfeljebb n összehasonlítást, hogy az összes ilyen számokat a megfelelő helyre.

52
00:03:13,230 --> 00:03:16,230
Egy ilyen algoritmus azt mondta, hogy fut a lineáris idő,

53
00:03:16,230 --> 00:03:18,090
de ne aggódj, hogy itt.

54
00:03:18,570 --> 00:03:22,810
>> Használd az algoritmus egyesülő, tudjuk, hogy egy gyors merge rendezési algoritmus.

55
00:03:22,810 --> 00:03:25,170
Nos, nézzük vissza a listákat.

56
00:03:35,210 --> 00:03:37,750
Van 2 nagy lépés a folyamat merge sort.

57
00:03:37,750 --> 00:03:41,500
Először is, folyamatosan szét a listáját cups figyelembe félidőt

58
00:03:41,500 --> 00:03:44,860
amíg van egy csomó listák csak 1 csésze őket.

59
00:03:44,860 --> 00:03:47,350
Ne aggódjon, ha a lista tartalmazza a páratlan számú

60
00:03:47,350 --> 00:03:49,880
és nem lehet, hogy egy teljesen tiszta vágás között.

61
00:03:49,880 --> 00:03:53,750
Csak önkényesen válasszon, amely lista tartalmazza az extra pohár be

62
00:03:53,750 --> 00:03:56,240
Szóval, most szét ezeket a listákat.

63
00:03:58,140 --> 00:04:01,310
Most van 2 listákat.

64
00:04:04,120 --> 00:04:06,570
Most már 4 listákat.

65
00:04:10,350 --> 00:04:13,870
>> És most már 8 listák egy csésze mindegyik listán.

66
00:04:13,870 --> 00:04:16,630
Szóval ez azt az 1. lépést.

67
00:04:16,630 --> 00:04:22,230
A 2. lépésben, akkor ismételten egyesítése pár listák segítségével az egyesítés algoritmus tudtuk korábban.

68
00:04:22,230 --> 00:04:29,160
Egyesítése 108 és 15, akkor a végén a listát 15, 108.

69
00:04:30,330 --> 00:04:36,250
Összevonása 50 és 4, a végén 4, 50.

70
00:04:36,960 --> 00:04:41,400
Egyesítése 8 és 42, a végén 8, 42.

71
00:04:42,790 --> 00:04:48,130
És egyesülő 23 és 16, a végén 16, 23.

72
00:04:49,740 --> 00:04:52,450
Most minden a mi listák a 2-es méret.

73
00:04:53,020 --> 00:04:56,180
Figyeljük meg, hogy mind a 4 listák rendezve.

74
00:04:56,180 --> 00:04:59,160
>> Így tudjuk kezdeni egyesülő pár listák újra.

75
00:04:59,160 --> 00:05:03,240
Összevonása 15. és a 108. és 4 és 50 -

76
00:05:03,240 --> 00:05:11,170
előbb a 4, akkor a 15, majd a 50, majd a 108.

77
00:05:11,170 --> 00:05:15,120
Összevonása 8, 42 és 16, 23,

78
00:05:15,120 --> 00:05:22,440
mi előbb a 8, akkor a 16, majd a 23, majd a 42.

79
00:05:22,440 --> 00:05:27,370
Így most már csak 2 listák 4 nagyság, amelyek mindegyike rendezve.

80
00:05:27,370 --> 00:05:30,980
Tehát most már eleget a 2 listákat.

81
00:05:30,980 --> 00:05:33,440
Először vegyük a 4.

82
00:05:33,440 --> 00:05:36,580
Akkor tegye meg a 8.

83
00:05:36,580 --> 00:05:50,700
Akkor vesszük a 15 és 16, majd 23, majd 42, majd 50, majd 108.

84
00:05:50,700 --> 00:05:52,220
És mi történt.

85
00:05:52,220 --> 00:05:54,900
Most már van egy rendezett listát.

86
00:05:54,900 --> 00:05:57,890
Szóval, milyen gyors volt ez pontosan?

87
00:05:57,890 --> 00:06:02,000
Műszaki szempontból egyesítés rendezés O (n log n),

88
00:06:02,000 --> 00:06:07,380
mivel az összes buborék rendezés, beszúrásos rendezés, és a kiválasztási sort az O (n ²).

89
00:06:07,380 --> 00:06:11,120
Valójában, ahogy megtudhatja hamarosan, akkor nem fogja tudni, hogy dolgozzon ki egy sort

90
00:06:11,120 --> 00:06:14,820
hogy jobban teljesít, mint a O (n log n) az általános esetben.

91
00:06:14,820 --> 00:06:19,120
Ismételten, ne aggódj ez a nagy O jelölést, ha még nem látta még.

92
00:06:19,120 --> 00:06:23,490
>> Csak tudom, hogy ez azt jelenti, ha azt akartuk, hogy rendezni egy igazán nagy listát

93
00:06:23,490 --> 00:06:26,820
buborék rendezés, beszúrásos rendezés, és a kiválasztási sorrend esetleg venni

94
00:06:26,820 --> 00:06:29,500
lényegesen hosszabb merge sort.

95
00:06:29,500 --> 00:06:33,210
Ez nem jelenti azt, hogy merge sort gyorsabb lesz az összes listák

96
00:06:33,210 --> 00:06:36,220
vagy akár egyetlen listán egy bizonyos méret alatt.

97
00:06:36,220 --> 00:06:41,950
Például a beszúrási sort lehet a leggyorsabb fajta összes listák kisebb, mint 5 elemeket.

98
00:06:41,950 --> 00:06:47,360
A gyakorlatban, merge sort általában gyorsabb listák kisebb, mint 50 elemét.

99
00:06:47,360 --> 00:06:51,120
>> De ez az extra sebesség nem jön nélkül ár.

100
00:06:51,120 --> 00:06:54,770
Ellentétben a többi fajta, amelyek figyelembe egy listát, és módosítsa a listát a helyére

101
00:06:54,770 --> 00:06:58,740
amíg nem kap egy rendezett lista merge sort igényel további helyet

102
00:06:58,740 --> 00:07:00,900
egyesíteni 2 listákat együtt.

103
00:07:00,900 --> 00:07:04,690
Nem azonnal használhatja a listákat, amelyek összevonták, hogy tárolja az új listát

104
00:07:04,690 --> 00:07:08,880
mert talán felülbírálhatja elemek kell még vonni.

105
00:07:08,880 --> 00:07:13,540
Ez a hely egy kicsit az ára, de ez általában nem ésszerűtlen.

106
00:07:13,540 --> 00:07:15,330
És ez azt merge sort.

107
00:07:15,330 --> 00:07:18,490
>> A nevem Rob Bowden, és ez CS50.

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

109
00:07:20,500 --> 00:07:24,000
- És kiválasztás sort.

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

111
00:07:25,880 --> 00:07:31,480
Ó, értem, hogy ezt ki is kapcsol, mert hogyan is bemutató.

112
00:07:31,480 --> 00:07:35,680
Sorolja fel a bal oldalon. Ez egy elírás.

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

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

115
00:07:41,190 --> 00:07:44,190
Én nem tudom, mi -