1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Sammanfoga Sortera]

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

3
00:00:04,000 --> 00:00:07,000
[Detta är CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Låt oss tala om sammanslagning slag.

5
00:00:09,000 --> 00:00:14,000
Hittills har du sett bubbla sortera, införande sortera och välja sortera.

6
00:00:14,000 --> 00:00:17,000
Även om jag ska typ av våg min hand på vad jag menar med bättre,

7
00:00:17,000 --> 00:00:21,000
samman Sortera presterar generellt bättre än någon av dessa 3 slag.

8
00:00:22,000 --> 00:00:27,000
>> Men innan jag talar om sammanslagning sortera, låt oss tala om sammanslagning 2 sorterade listor.

9
00:00:27,000 --> 00:00:31,000
Vi ringer processen att ta 2 sorterade listor, som dessa,

10
00:00:31,000 --> 00:00:35,000
och göra en enda sorterad lista av dem - sammanslagning av listorna.

11
00:00:35,000 --> 00:00:37,750
Hur kan vi göra det?

12
00:00:37,750 --> 00:00:41,290
Tja, är en idé att bara sticka en lista på slutet av den andra listan

13
00:00:41,290 --> 00:00:43,830
och sedan sortera det resulterande listan.

14
00:00:43,830 --> 00:00:47,220
>> Även om detta fungerar, det är en hel del onödigt arbete.

15
00:00:47,220 --> 00:00:49,900
Vi kan göra det snabbare än att bara sortera.

16
00:00:49,900 --> 00:00:54,100
Lägg märke till att en felaktig uppfattning är att bara ta alternerande koppar från varje lista.

17
00:00:54,100 --> 00:00:56,460
Även om det kan verka som det fungerar i början,

18
00:00:56,460 --> 00:01:05,760
gör att vi slutar med 4, 8, 15, 23, 16 - märker att 16 och 23 är på sin plats.

19
00:01:05,760 --> 00:01:09,380
Detta beror på att 2 element som ska visas i rad i den sammanslagna listan

20
00:01:09,380 --> 00:01:11,720
är i samma ursprungliga listan.

21
00:01:11,720 --> 00:01:14,850
Både 15 och 16 finns i listan till vänster.

22
00:01:14,850 --> 00:01:19,810
Tricket är att dra nytta av det faktum att båda listorna redan är sorterade.

23
00:01:19,810 --> 00:01:23,320
Det innebär att om vi bara ser på de första delarna av båda listorna -

24
00:01:23,320 --> 00:01:29,580
Här, 4 och 8 - måste en av dem vara också den första delen av det sammanslagna listan.

25
00:01:29,580 --> 00:01:31,620
Tja, varför är det?

26
00:01:31,620 --> 00:01:33,520
Båda dessa listor är redan sorterade,

27
00:01:33,520 --> 00:01:38,410
och så antingen 4 eller 8 måste vara det minsta elementet när vi kombinerar de 2 listorna.

28
00:01:38,410 --> 00:01:41,770
I detta fall är den minsta 4,

29
00:01:41,770 --> 00:01:46,370
så att vi kan ta ut 4 och göra det den första delen av vår sammanslagna lista.

30
00:01:46,370 --> 00:01:50,710
Nu fortsätter vi att slå samman de återstående 3 element i den första listan

31
00:01:50,710 --> 00:01:52,920
och 4 element i den andra listan.

32
00:01:52,920 --> 00:01:57,150
>> Återigen behöver vi bara titta på den första delen av båda listorna.

33
00:01:57,150 --> 00:02:01,060
Den mindre av de 2 skall vara den andra delen av vår sammanslagna lista.

34
00:02:01,060 --> 00:02:05,440
Den här gången, mellan 8 och 15 den minsta är 8, så vi sätter att

35
00:02:05,440 --> 00:02:09,240
som den andra delen av vår sorterade listan.

36
00:02:09,240 --> 00:02:12,180
Vi kan fortsätta att jämföra de första delarna av båda listorna

37
00:02:12,180 --> 00:02:14,420
och avlägsnande av mindre av 2.

38
00:02:14,420 --> 00:02:19,460
Jämföra 15 och 23, 15 är mindre och så det är vår tredje elementet.

39
00:02:21,000 --> 00:02:23,910
Nu jämföra 16 och 23, 16 är mindre.

40
00:02:23,910 --> 00:02:26,820
Så det är det fjärde elementet.

41
00:02:26,820 --> 00:02:30,390
>> Observera att 2 delar kom från samma lista i en rad.

42
00:02:30,390 --> 00:02:34,400
Det är därför det sammanslagna listan kan inte bara alternativa element från 2 listor.

43
00:02:34,400 --> 00:02:40,020
Jämföra 50 och 23, 23 är mindre, så vi väljer att.

44
00:02:40,770 --> 00:02:44,070
Mellan 50 och 42, är 42 mindre.

45
00:02:44,070 --> 00:02:48,290
Mellan 50 och 108, är 50 mindre.

46
00:02:48,290 --> 00:02:52,330
Och slutligen, vi bara har 108, så det måste gå på slutet av vår lista.

47
00:02:53,750 --> 00:02:56,180
Observera att vi har en fin, sorterad lista.

48
00:02:56,180 --> 00:02:59,040
Varje gång vi jämfört de första 2 delarna av de 2 listorna

49
00:02:59,040 --> 00:03:02,730
vi kunde bestämma nästa del av sammanslagna listan.

50
00:03:02,730 --> 00:03:08,070
Detta innebär att om den slutgiltiga listan innehåller n tal, där n här är 8,

51
00:03:08,070 --> 00:03:12,610
då behöver vi i de flesta n jämförelser för att få alla dessa siffror till rätt plats.

52
00:03:13,230 --> 00:03:16,230
En sådan algoritm sägs att köra i linjär tid,

53
00:03:16,230 --> 00:03:18,090
men oroa dig inte om det här.

54
00:03:18,570 --> 00:03:22,810
>> Med vår algoritm för att slå samman, kan vi göra en snabb merge sort algoritm.

55
00:03:22,810 --> 00:03:25,170
Så, låt oss återställa våra listor.

56
00:03:35,210 --> 00:03:37,750
Det finns 2 stora steg i processen sammanslagning slag.

57
00:03:37,750 --> 00:03:41,500
Först, kontinuerligt dela listan av koppar i halvor

58
00:03:41,500 --> 00:03:44,860
tills vi har ett gäng listor med bara 1 kopp i dem.

59
00:03:44,860 --> 00:03:47,350
Oroa dig inte om en lista innehåller ett udda antal

60
00:03:47,350 --> 00:03:49,880
och du kan inte göra en helt ren snitt mellan dem.

61
00:03:49,880 --> 00:03:53,750
Bara godtyckligt välja vilken lista att inkludera extra kopp i.

62
00:03:53,750 --> 00:03:56,240
Så, låt oss dela dessa listor.

63
00:03:58,140 --> 00:04:01,310
Nu har vi 2 listor.

64
00:04:04,120 --> 00:04:06,570
Nu har vi 4 listor.

65
00:04:10,350 --> 00:04:13,870
>> Och nu har vi 8 listor med en enda kopp i varje lista.

66
00:04:13,870 --> 00:04:16,630
Så det är det för steg 1.

67
00:04:16,630 --> 00:04:22,230
För steg 2, slå ihop vi upprepade par av listor med sammanslagningen algoritmen vi lärt tidigare.

68
00:04:22,230 --> 00:04:29,160
Sammanslagningen av 108 och 15 hamnar vi med listan 15, 108.

69
00:04:30,330 --> 00:04:36,250
Sammanslagningen av 50 och 4 hamnar vi med 4, 50.

70
00:04:36,960 --> 00:04:41,400
Sammanslagningen av 8 och 42, hamnar vi med 8, 42.

71
00:04:42,790 --> 00:04:48,130
Och sammanslagning 23 och 16, hamnar vi med 16, 23.

72
00:04:49,740 --> 00:04:52,450
Nu är alla våra listor är av storlek 2.

73
00:04:53,020 --> 00:04:56,180
Lägg märke till att var och en av de 4 listorna sorteras.

74
00:04:56,180 --> 00:04:59,160
>> Så vi kan börja sammanslagning par av listor igen.

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

76
00:05:03,240 --> 00:05:11,170
först ta 4, sedan 15, sedan 50, sedan 108.

77
00:05:11,170 --> 00:05:15,120
Sammanfoga 8, 42 och 16, 23,

78
00:05:15,120 --> 00:05:22,440
vi tar först 8, sedan 16, sedan 23, sedan 42.

79
00:05:22,440 --> 00:05:27,370
Så nu har vi bara 2 listor med storlek 4, är var och en sorterad.

80
00:05:27,370 --> 00:05:30,980
Så nu har vi ihop dessa 2 listor.

81
00:05:30,980 --> 00:05:33,440
Först tar vi 4.

82
00:05:33,440 --> 00:05:36,580
Sen tar vi 8.

83
00:05:36,580 --> 00:05:50,700
Då vi tar 15 och 16, sedan 23, sedan 42, sedan 50, sedan 108.

84
00:05:50,700 --> 00:05:52,220
Och vi är klara.

85
00:05:52,220 --> 00:05:54,900
Vi har nu en sorterad lista.

86
00:05:54,900 --> 00:05:57,890
Så hur snabbt var, exakt?

87
00:05:57,890 --> 00:06:02,000
I tekniska termer är sammanslagning Sortera O (n log n),

88
00:06:02,000 --> 00:06:07,380
medan hela bubbla sortera, införande sortera och val Sortera är O (n ²).

89
00:06:07,380 --> 00:06:11,120
I själva verket, eftersom du kommer lära dig snart, kommer du inte att kunna komma med ett slags

90
00:06:11,120 --> 00:06:14,820
som presterar bättre än O (n log n) i det allmänna fallet.

91
00:06:14,820 --> 00:06:19,120
Återigen, oroa dig inte om detta stora O notation om du inte har sett den ännu.

92
00:06:19,120 --> 00:06:23,490
>> Bara vet att detta innebär att om vi ville sortera en riktigt stor lista

93
00:06:23,490 --> 00:06:26,820
bubbla sortera, införande sortera och val Sortera skulle kunna ta

94
00:06:26,820 --> 00:06:29,500
betydligt längre än samman sort.

95
00:06:29,500 --> 00:06:33,210
Det betyder inte att merge sort kommer att bli snabbare för alla listor

96
00:06:33,210 --> 00:06:36,220
eller ens för en enskild lista under en viss storlek.

97
00:06:36,220 --> 00:06:41,950
Till exempel kan insättningen Sortera vara den snabbaste Sortera alla listor mindre än 5 element.

98
00:06:41,950 --> 00:06:47,360
I praktiken är merge sort oftast snabbare för listor så små som 50 element.

99
00:06:47,360 --> 00:06:51,120
>> Men denna extra fart kommer inte utan ett pris.

100
00:06:51,120 --> 00:06:54,770
Till skillnad från våra andra slag, som tar en lista och ändra listan på plats

101
00:06:54,770 --> 00:06:58,740
tills vi får en sorterad lista behöver merge sort några extra utrymme

102
00:06:58,740 --> 00:07:00,900
att sammanfoga 2 listor tillsammans.

103
00:07:00,900 --> 00:07:04,690
Vi kan inte omedelbart använda de listor som håller samman för att lagra den sammanslagna listan

104
00:07:04,690 --> 00:07:08,880
eftersom vi kan åsidosätta element som fortfarande behöver slås samman.

105
00:07:08,880 --> 00:07:13,540
Detta utrymme är lite av ett pris, men det brukar inte orimligt.

106
00:07:13,540 --> 00:07:15,330
Och det är det för sammanfogningen sorteringen.

107
00:07:15,330 --> 00:07:18,490
>> Mitt namn är Rob Bowden, och detta är CS50.

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

109
00:07:20,500 --> 00:07:24,000
- Och urval sortera.

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

111
00:07:25,880 --> 00:07:31,480
Åh, fick ta ut det också eftersom jag bytte hur jag visade upp det.

112
00:07:31,480 --> 00:07:35,680
Listan till vänster. Det var ett stavfel.

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

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

115
00:07:41,190 --> 00:07:44,190
Jag vet inte vad -