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

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

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

4
00:00:07,000 --> 00:00:09,000
Kom ons praat oor merge soort.

5
00:00:09,000 --> 00:00:14,000
Tot dusver het jy gesien borrel soort, invoeging soort, en seleksie soort.

6
00:00:14,000 --> 00:00:17,000
Alhoewel ek sal soort van golf my hand op wat ek bedoel deur 'n beter,

7
00:00:17,000 --> 00:00:21,000
saamsmelt soort voer oor die algemeen beter as enige van hierdie 3 vorme.

8
00:00:22,000 --> 00:00:27,000
>> Maar voordat praat oor merge soort, laat ons praat oor die samesmelting van 2 gesorteer lyste.

9
00:00:27,000 --> 00:00:31,000
Ons sal die proses van die neem van 2 gesorteer lyste roep, soos hierdie,

10
00:00:31,000 --> 00:00:35,000
en die maak van 'n gesorteerde lys van hulle - die samesmelting van die lyste.

11
00:00:35,000 --> 00:00:37,750
Hoe kan ons dit doen?

12
00:00:37,750 --> 00:00:41,290
Wel, 'n idee is om net te hou 'n lys op die einde van die ander lys

13
00:00:41,290 --> 00:00:43,830
en dan sorteer die lys.

14
00:00:43,830 --> 00:00:47,220
>> Terwyl hierdie werk, dit is 'n baie onnodige werk.

15
00:00:47,220 --> 00:00:49,900
Ons kan dit doen vinniger as net sorteer.

16
00:00:49,900 --> 00:00:54,100
Let daarop dat een verkeerde idee is om net wisselstroom koppies uit elke lys.

17
00:00:54,100 --> 00:00:56,460
Terwyl dit kan lyk soos dié werke op die eerste,

18
00:00:56,460 --> 00:01:05,760
doen dat ons opeindig met 4, 8, 15, 23, 16 - kennisgewing dat 16 en 23 is uit plek.

19
00:01:05,760 --> 00:01:09,380
Dit is omdat die 2 elemente wat in die saamgesmelte lys moet verskyn agtereenvolgende

20
00:01:09,380 --> 00:01:11,720
is in dieselfde aanvanklike lys.

21
00:01:11,720 --> 00:01:14,850
Beide 15 en 16 is in die lys aan die linkerkant.

22
00:01:14,850 --> 00:01:19,810
Die truuk is om voordeel te trek uit die feit dat beide lyste word reeds gesorteer.

23
00:01:19,810 --> 00:01:23,320
Dit beteken dat as ons net kyk na die eerste elemente van beide lyste -

24
00:01:23,320 --> 00:01:29,580
hier, 4 en 8 - een van hulle moet ook die eerste element van die saamgesmelte lys.

25
00:01:29,580 --> 00:01:31,620
Wel, hoekom is dit?

26
00:01:31,620 --> 00:01:33,520
Beide van hierdie lyste is reeds gesorteer,

27
00:01:33,520 --> 00:01:38,410
en so 4 of 8 moet die kleinste element wees wanneer ons kombineer die 2 lyste.

28
00:01:38,410 --> 00:01:41,770
In hierdie geval, die kleinste is 4,

29
00:01:41,770 --> 00:01:46,370
sodat ons kan neem 4 en maak dit die eerste element van die saamgesmelte lys.

30
00:01:46,370 --> 00:01:50,710
Nou moet ons voortgaan met die samesmelting van die oorblywende 3 elemente van die eerste lys

31
00:01:50,710 --> 00:01:52,920
en 4 elemente van die tweede lys.

32
00:01:52,920 --> 00:01:57,150
>> Weereens, ons moet net om te kyk na die eerste element van beide lyste.

33
00:01:57,150 --> 00:02:01,060
Die kleiner van die 2 die tweede element van ons saamgesmelte lys moet wees.

34
00:02:01,060 --> 00:02:05,440
Hierdie tyd, tussen 8 en 15 die kleinste is 8, en sodat ons voeg dat

35
00:02:05,440 --> 00:02:09,240
as die tweede element van ons gesorteerde lys.

36
00:02:09,240 --> 00:02:12,180
Ons kan voortgaan om die eerste elemente van beide lyste te vergelyk

37
00:02:12,180 --> 00:02:14,420
en die verwydering van die kleiner van die 2.

38
00:02:14,420 --> 00:02:19,460
Vergelyking van 15 en 23, 15, is kleiner en so dit is ons derde element.

39
00:02:21,000 --> 00:02:23,910
Nou vergelyk 16 en 23, 16 is kleiner.

40
00:02:23,910 --> 00:02:26,820
So dit is die vierde element.

41
00:02:26,820 --> 00:02:30,390
>> Let op dat 2 elemente kom uit dieselfde lys in 'n ry.

42
00:02:30,390 --> 00:02:34,400
Dit is waarom die saamgesmelte lys kan nie net alternatiewe elemente van die 2 lyste.

43
00:02:34,400 --> 00:02:40,020
Vergelyking van 50 en 23, 23 is kleiner, so ons kies dat.

44
00:02:40,770 --> 00:02:44,070
Tussen 50 en 42, 42 is kleiner.

45
00:02:44,070 --> 00:02:48,290
Tussen 50 en 108, 50 is kleiner.

46
00:02:48,290 --> 00:02:52,330
En, uiteindelik, ons moet net 108, so dit moet gaan op die einde van die lys.

47
00:02:53,750 --> 00:02:56,180
Let op dat ons het 'n mooi, gesorteerde lys.

48
00:02:56,180 --> 00:02:59,040
Elke keer as ons vergelyk met die eerste 2 elemente van die 2 lyste

49
00:02:59,040 --> 00:03:02,730
ons was in staat om die volgende element van die saamgesmelte lys te bepaal.

50
00:03:02,730 --> 00:03:08,070
Dit beteken dat indien die finale lys bevat N getalle, waar n is hier 8,

51
00:03:08,070 --> 00:03:12,610
dan moet ons op die meeste N vergelykings al daardie getalle in die regte plek te kry.

52
00:03:13,230 --> 00:03:16,230
So 'n algoritme word gesê in lineêre tyd uit te voer,

53
00:03:16,230 --> 00:03:18,090
maar moenie worry nie oor wat hier.

54
00:03:18,570 --> 00:03:22,810
>> Die gebruik van ons algoritme vir die kombinering, kan ons 'n vinnige merge soort algoritme.

55
00:03:22,810 --> 00:03:25,170
So, laat ons weer ons lyste.

56
00:03:35,210 --> 00:03:37,750
Daar is 2 groot stappe in die proses van merge soort.

57
00:03:37,750 --> 00:03:41,500
Eerste, voortdurend in twee helftes verdeel die lys van koppies

58
00:03:41,500 --> 00:03:44,860
totdat ons het 'n klomp van die lyste met net 1 koppie in hulle.

59
00:03:44,860 --> 00:03:47,350
Moenie bekommerd wees as 'n lys bevat 'n onewe getal

60
00:03:47,350 --> 00:03:49,880
en jy kan nie 'n volkome skoon sny tussen hulle.

61
00:03:49,880 --> 00:03:53,750
Net arbitrêr kies watter lys die ekstra koppie. In te sluit

62
00:03:53,750 --> 00:03:56,240
So, laat ons hierdie lyste verdeel.

63
00:03:58,140 --> 00:04:01,310
Nou het ons het 2 lyste.

64
00:04:04,120 --> 00:04:06,570
Nou het ons het 4 lyste.

65
00:04:10,350 --> 00:04:13,870
>> En nou het ons 8 lyste met 'n beker in elke lys.

66
00:04:13,870 --> 00:04:16,630
So wat is dit vir stap 1.

67
00:04:16,630 --> 00:04:22,230
Vir stap 2, het ons herhaaldelik saamsmelt pare van lyste met behulp van die kombinering algoritme wat ons geleer het.

68
00:04:22,230 --> 00:04:29,160
Kombineer 108 en 15, ons eindig met die lys 15, 108.

69
00:04:30,330 --> 00:04:36,250
Kombineer 50 en 4, ons eindig met 4, 50.

70
00:04:36,960 --> 00:04:41,400
Kombineer 8 en 42, het ons uiteindelik met 8, 42.

71
00:04:42,790 --> 00:04:48,130
En samesmelting 23 en 16, het ons uiteindelik met 16, 23.

72
00:04:49,740 --> 00:04:52,450
Nou al ons lyste is van grootte 2.

73
00:04:53,020 --> 00:04:56,180
Let daarop dat elk van die 4 lyste is gesorteer.

74
00:04:56,180 --> 00:04:59,160
>> Sodat ons kan begin met die samesmelting weer pare van lyste.

75
00:04:59,160 --> 00:05:03,240
Kombineer 15 en 108 en 4 en 50 -

76
00:05:03,240 --> 00:05:11,170
die eerste maal in die 4, dan is die 15, dan is die 50, dan is die 108.

77
00:05:11,170 --> 00:05:15,120
Kombineer 8, 42 en 16, 23,

78
00:05:15,120 --> 00:05:22,440
neem ons die eerste keer die 8, dan is die 16, dan 23, dan is die 42.

79
00:05:22,440 --> 00:05:27,370
So nou het ons net 2 lyste van grootte 4, wat elk gesorteer.

80
00:05:27,370 --> 00:05:30,980
So nou het ons saamsmelt hierdie 2 lys.

81
00:05:30,980 --> 00:05:33,440
Eerstens neem ons die 4.

82
00:05:33,440 --> 00:05:36,580
Dan neem ons die 8.

83
00:05:36,580 --> 00:05:50,700
Dan neem ons die 15 en 16, dan 23, dan 42, dan 50, dan is 108.

84
00:05:50,700 --> 00:05:52,220
En ons klaar is.

85
00:05:52,220 --> 00:05:54,900
Ons het nou 'n gesorteerde lys.

86
00:05:54,900 --> 00:05:57,890
So hoe vinnig was dit presies?

87
00:05:57,890 --> 00:06:02,000
In tegniese terme, merge soort is O (n log n),

88
00:06:02,000 --> 00:06:07,380
terwyl al borrel soort, invoeging soort, en seleksie soort is O (n ²).

89
00:06:07,380 --> 00:06:11,120
In werklikheid, as jy sal gou leer, sal jy nie in staat wees om vorendag te kom met 'n soort

90
00:06:11,120 --> 00:06:14,820
wat presteer beter as O (n log n) in die algemene geval.

91
00:06:14,820 --> 00:06:19,120
Weereens, moenie bekommerd wees oor hierdie groot-O notasie as jy dit nog nie gesien het nie.

92
00:06:19,120 --> 00:06:23,490
>> Weet net dat dit beteken as ons wou 'n baie groot lys te sorteer

93
00:06:23,490 --> 00:06:26,820
borrel soort, invoeging soort en die seleksie soort kan potensieel

94
00:06:26,820 --> 00:06:29,500
aansienlik langer as saamsmelt soort.

95
00:06:29,500 --> 00:06:33,210
Dit beteken nie dat merge soort sal vinniger wees vir alle lyste

96
00:06:33,210 --> 00:06:36,220
of selfs vir 'n enkele lys onder 'n sekere grootte.

97
00:06:36,220 --> 00:06:41,950
Byvoorbeeld, invoeging soort die vinnigste soort vir alle lyste kleiner as 5 elemente.

98
00:06:41,950 --> 00:06:47,360
In die praktyk, merge soort is gewoonlik vinniger lyste so klein as 50 elemente.

99
00:06:47,360 --> 00:06:51,120
>> Maar hierdie ekstra spoed nie sonder 'n prys gekom.

100
00:06:51,120 --> 00:06:54,770
Anders as ons ander vorme, wat 'n lys en die lys in plek te verander

101
00:06:54,770 --> 00:06:58,740
totdat ons 'n gesorteerde lys, merge soort moet 'n paar ekstra ruimte

102
00:06:58,740 --> 00:07:00,900
2 lyste saam te smelt.

103
00:07:00,900 --> 00:07:04,690
Ons kan nie dadelik gebruik om die lyste wat word saamgevoeg om die saamgesmelte lys te stoor

104
00:07:04,690 --> 00:07:08,880
want ons kan oorheers elemente wat nog moet word saamgevoeg.

105
00:07:08,880 --> 00:07:13,540
Hierdie ruimte is 'n bietjie van 'n prys, maar dit gewoonlik is nie onredelik nie.

106
00:07:13,540 --> 00:07:15,330
En dit is dit vir merge soort.

107
00:07:15,330 --> 00:07:18,490
>> My naam is Rob Bowden, en dit is CS50.

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

109
00:07:20,500 --> 00:07:24,000
- En seleksie soort.

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

111
00:07:25,880 --> 00:07:31,480
O, het ook om uit te neem, want ek oorgeskakel hoe ek dit was die aanbieding.

112
00:07:31,480 --> 00:07:35,680
Lys aan die linkerkant. Dit was 'n tikfout.

113
00:07:35,680 --> 00:07:39,290
[Misspoke] Ek screwed up -

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

115
00:07:41,190 --> 00:07:44,190
Ek weet nie wat -