1
00:00:00,000 --> 00:00:04,419
>> [MÜZİK OYUN]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> Doug LLOYD: Tamam, bir birleştirme
Sıralama başka algoritma

4
00:00:08,460 --> 00:00:11,200
Biz dışarı sıralamak için kullanabileceğiniz
Bir dizinin elemanları.

5
00:00:11,200 --> 00:00:14,480
Biz göreceğiz Ancak, bu var bir
Çok temel fark

6
00:00:14,480 --> 00:00:17,850
Seçim sıralama, kabarcık
sıralama ve yerleştirme sıralama

7
00:00:17,850 --> 00:00:20,280
o gerçekten çok zeki olun.

8
00:00:20,280 --> 00:00:24,290
>> Birleştirme arkasındaki temel fikir
Sıralama küçük diziler sıralamak için

9
00:00:24,290 --> 00:00:27,430
ve daha sonra bu dizileri birleştirmek
Birlikte veya them-- birleştirme

10
00:00:27,430 --> 00:00:31,440
dolayısıyla sıralı sırayla aşkına--.

11
00:00:31,440 --> 00:00:34,230
Sıralama yapar birleştirme yolu
Bu bir araç yararlanarak gereğidir

12
00:00:34,230 --> 00:00:37,290
ne olduğu, yineleme denilen
Biz yakında bahsediyoruz gidiyoruz

13
00:00:37,290 --> 00:00:39,720
ama biz gerçekten hakkında henüz konuşmadık.

14
00:00:39,720 --> 00:00:43,010
>> İşte birleştirme sıralama ardındaki temel fikir.

15
00:00:43,010 --> 00:00:46,320
Dizinin sol yarısını sıralama
n varsayılarak 1 daha büyüktür.

16
00:00:46,320 --> 00:00:49,980
Ve ben derken ne demek
n varsayılarak, 1 daha büyüktür

17
00:00:49,980 --> 00:00:53,970
Sanırım kabul düşünüyorum olduğu bir dizi halinde
yalnızca tek bir elemandan oluşur,

18
00:00:53,970 --> 00:00:54,680
o tür var.

19
00:00:54,680 --> 00:00:56,560
Biz aslında ihtiyacımız yok
buna bir şey yapmak için.

20
00:00:56,560 --> 00:00:58,059
Biz sadece sıralanabilir için ilan edebilir.

21
00:00:58,059 --> 00:01:00,110
Sadece bir tek eleman var.

22
00:01:00,110 --> 00:01:03,610
>> Yani sözde kod, yine,
dizinin sol yarısını sıralamak

23
00:01:03,610 --> 00:01:08,590
sonra sağ yarım dizi sıralamak,
sonra birlikte iki yarısı birleştirme.

24
00:01:08,590 --> 00:01:11,040
Şimdi, zaten olabilir
düşünme, bu tür sadece

25
00:01:11,040 --> 00:01:14,080
Şeyin kapalı koyarak konum gibi geliyor
aslında hiçbir şey yapmıyorsun.

26
00:01:14,080 --> 00:01:16,330
Sen sol sıralamak söylüyorsun
yarısı sağ yarısı sıralamak

27
00:01:16,330 --> 00:01:19,335
ama sen söylemediğin
Bana bunu nasıl yapıyorsun.

28
00:01:19,335 --> 00:01:22,220
>> Ama sürece unutmayın
Bir dizi tek unsurdur,

29
00:01:22,220 --> 00:01:23,705
Biz o tür bildirebilirsiniz.

30
00:01:23,705 --> 00:01:25,330
Sonra biz sadece onları bir arada birleştirebilirsiniz.

31
00:01:25,330 --> 00:01:27,788
Ve bu aslında
Birleştirme sıralama ardındaki temel fikir,

32
00:01:27,788 --> 00:01:31,150
Bu yüzden yıkmak olduğunu
senin diziler büyüklüğü biri vardır.

33
00:01:31,150 --> 00:01:33,430
Ve sonra oradan yeniden.

34
00:01:33,430 --> 00:01:35,910
>> Sıralama kesinlikle Birleştirme
Karmaşık bir algoritma.

35
00:01:35,910 --> 00:01:38,210
Ve o da biraz var
görselleştirmek için karmaşık.

36
00:01:38,210 --> 00:01:41,870
Yani umarım, görselleştirme ben
Eğer birlikte takip yardımcı olacaktır burada var.

37
00:01:41,870 --> 00:01:45,640
Ve ben bir şeyler anlatmaya elimden geleni yapacağım
ve bu biraz daha ile devam

38
00:01:45,640 --> 00:01:49,180
Yavaş yavaş diğer olanlardan daha
Sadece umarım başını almak için

39
00:01:49,180 --> 00:01:51,800
Birleştirme tür arkasındaki fikir etrafında.

40
00:01:51,800 --> 00:01:54,680
>> Yani biz aynı dizi var
Diğer sıralama algoritması videoları

41
00:01:54,680 --> 00:01:57,120
Gördüğünüz eğer them--
altı unsur dizisi.

42
00:01:57,120 --> 00:02:02,110
Ve burada bizim pseudocode kodu tür
Sol yarısı sağ yarısı sıralamak

43
00:02:02,110 --> 00:02:03,890
Birlikte iki yarısını birleştirmek.

44
00:02:03,890 --> 00:02:09,770
Yani bu çok karanlık bir tuğla kırmızı atalım
Dizi ve bunun sol yarısı sıralayın.

45
00:02:09,770 --> 00:02:13,380
>> Bu yüzden şu anda, biz gidiyoruz
Sağdaki şeyler görmezden.

46
00:02:13,380 --> 00:02:15,740
Orada, ama biz konum
henüz o aşamada.

47
00:02:15,740 --> 00:02:18,220
Biz değiliz de sıralama
Dizinin sağ yarısı.

48
00:02:18,220 --> 00:02:21,037
Biz tür sol konum
Dizinin yarısı.

49
00:02:21,037 --> 00:02:22,870
Ve sadece uğruna
biraz daha olmak

50
00:02:22,870 --> 00:02:26,480
açık, bu yüzden başvurabilirsiniz
Ne adım biz konum,

51
00:02:26,480 --> 00:02:29,800
Ben geçmek için gidiyorum
turuncu, bu setin rengi.

52
00:02:29,800 --> 00:02:33,190
Şimdi, biz hala hakkında konuşuyor
Orijinal dizinin aynı sol yarısı.

53
00:02:33,190 --> 00:02:38,520
Ama edememek tarafından umuyorum
çeşitli öğelerin renklerine bakın

54
00:02:38,520 --> 00:02:40,900
o biraz daha yapacağız
Burada neler oluyor temizleyin.

55
00:02:40,900 --> 00:02:43,270
>> Tamam, şimdi biz bir
Üç element dizisi.

56
00:02:43,270 --> 00:02:46,420
Biz bu sol yarısını sıralama nasıl
hala bu adım dizi?

57
00:02:46,420 --> 00:02:49,400
Biz sol sıralamak için çalışıyoruz
tuğla kırmızısı array-- yarısı

58
00:02:49,400 --> 00:02:52,410
Sol yarısı
Ben şimdi turuncu renkli ettik.

59
00:02:52,410 --> 00:02:54,840
>> Eh, biz denemek olabilir ve
Yine bu işlemi tekrarlayın.

60
00:02:54,840 --> 00:02:56,756
Yani biz hâlâ
sıralamak için çalışıyor orta

61
00:02:56,756 --> 00:02:58,700
Tam dizinin sol yarısı.

62
00:02:58,700 --> 00:03:00,450
Sol yarısı
Dizi, ben sadece gidiyorum

63
00:03:00,450 --> 00:03:03,910
keyfi karar olduğunu sol yarım
Sağ yarısından daha küçük olacak,

64
00:03:03,910 --> 00:03:06,550
Bu olur çünkü
Üç öğeden oluşur.

65
00:03:06,550 --> 00:03:11,260
>> Ve bu yüzden söylemek için gidiyorum
Sol yarısı dizisi sol yarısı

66
00:03:11,260 --> 00:03:14,050
Sadece eleman beş.

67
00:03:14,050 --> 00:03:18,360
Beş, tek bir eleman olmak
Dizi, biz bunu sıralamak için biliyorum.

68
00:03:18,360 --> 00:03:21,615
Ve böylece beş sıralanır.

69
00:03:21,615 --> 00:03:22,990
Biz sadece beyan edeceğiz.

70
00:03:22,990 --> 00:03:24,890
Tek eleman dizisi var.

71
00:03:24,890 --> 00:03:29,015
>> Yani biz şimdi sıralanmış ettik
Sol half-- sol yarısı

72
00:03:29,015 --> 00:03:33,190
ya da daha doğrusu, biz kriteri ettik
turuncu sol yarısı.

73
00:03:33,190 --> 00:03:37,970
Yani şimdi, sırayla hala tam
Genel dizinin sol yarısı,

74
00:03:37,970 --> 00:03:43,481
Doğru yarısını sıralamak gerekiyor
turuncu veya bu şeyler.

75
00:03:43,481 --> 00:03:44,230
Biz nasıl yapacağız?

76
00:03:44,230 --> 00:03:45,930
Peki, biz bir iki eleman dizi var.

77
00:03:45,930 --> 00:03:50,470
Bu yüzden sol yarısını sıralayabilirsiniz
iki dizisinin.

78
00:03:50,470 --> 00:03:52,090
İki tek unsurdur.

79
00:03:52,090 --> 00:03:55,890
Yani varsayılan sıralama kriteri oluyor.
Sonra sağ yarısını sıralayabilirsiniz

80
00:03:55,890 --> 00:03:58,530
tadını birinin bu kısmının.

81
00:03:58,530 --> 00:04:00,210
Bu varsayılan çeşit var.

82
00:04:00,210 --> 00:04:03,610
>> Bu şimdi ilk kez
Biz bir birleştirme adımı ulaştınız.

83
00:04:03,610 --> 00:04:06,135
Biz her ne kadar, tamamlamış
Şimdi biraz down-- iç içe konum

84
00:04:06,135 --> 00:04:08,420
ve bu zor bir çeşit
yineleme ile bir şey,

85
00:04:08,420 --> 00:04:10,930
Eğer sizin yanınızdaki tutmak gerekir
Nerede ilgili baş.

86
00:04:10,930 --> 00:04:15,560
Bu yüzden sol çeşit var
Turuncu bölümünün yarısı.

87
00:04:15,560 --> 00:04:21,280
>> Ve şimdi, biz sıralama ortasýndayýz
Turuncu bölümünün sağ yarısı.

88
00:04:21,280 --> 00:04:25,320
Ve bu süreçte, biz
adım olması şimdi hakkında

89
00:04:25,320 --> 00:04:27,850
Birlikte iki yarısını birleştirmek.

90
00:04:27,850 --> 00:04:31,700
Biz iki yarısı baktığımızda
dizinin, biz iki ve bir bakın.

91
00:04:31,700 --> 00:04:33,880
Hangi element küçüktür?

92
00:04:33,880 --> 00:04:35,160
Bir.

93
00:04:35,160 --> 00:04:36,760
>> Daha sonra bu eleman daha küçüktür?

94
00:04:36,760 --> 00:04:38,300
Peki, iki ya da hiçbir şey.

95
00:04:38,300 --> 00:04:39,910
Yani iki.

96
00:04:39,910 --> 00:04:43,690
Yani şimdi, sadece tekrar çerçeve
Biz bağlamında nerede,

97
00:04:43,690 --> 00:04:48,230
biz sıralamış
turuncu sol yarısı

98
00:04:48,230 --> 00:04:49,886
ve menşe sağ yarısı.

99
00:04:49,886 --> 00:04:52,510
Ben renkleri değişti biliyorum
nerede kalmıştık yine, ama bu.

100
00:04:52,510 --> 00:04:54,676
Ve neden ben yaptım
bu işlem olduğu için olan

101
00:04:54,676 --> 00:04:57,870
Aşağı yineleme, devam edecek.

102
00:04:57,870 --> 00:05:00,500
Biz sol kriteri ettik
Eski portakal yarısı

103
00:05:00,500 --> 00:05:02,590
ve eski portakal sağ yarısı.

104
00:05:02,590 --> 00:05:05,620
>> Şimdi, biz o birleştirmek gerekiyor
birbirine çok iki yarısı.

105
00:05:05,620 --> 00:05:07,730
Yani biz konum adımdır.

106
00:05:07,730 --> 00:05:11,440
Bu yüzden bütün düşünün
Şimdi yeşil unsurlar,

107
00:05:11,440 --> 00:05:12,972
Orijinal dizinin sol yarısı.

108
00:05:12,972 --> 00:05:14,680
Ve biz o birleştirme
Aynı işlem kullanılarak

109
00:05:14,680 --> 00:05:18,660
biz iki birleştirmek için yaptım
ve bir sadece bir an önce.

110
00:05:18,660 --> 00:05:23,080
>> Sol yarım, en küçük
Sol yarısında eleman beştir.

111
00:05:23,080 --> 00:05:25,620
En küçük eleman üzerinde
Sağ yarım biridir.

112
00:05:25,620 --> 00:05:27,370
Bunların hangisi daha küçüktür?

113
00:05:27,370 --> 00:05:29,260
Bir.

114
00:05:29,260 --> 00:05:32,250
>> En küçük eleman üzerinde
Sol yarım beş.

115
00:05:32,250 --> 00:05:35,540
En küçük eleman üzerinde
Sağ yarım ikidir.

116
00:05:35,540 --> 00:05:36,970
En küçük nedir?

117
00:05:36,970 --> 00:05:38,160
İki.

118
00:05:38,160 --> 00:05:41,540
Ve son olarak beş
hiçbir şey biz beş söyleyebiliriz.

119
00:05:41,540 --> 00:05:43,935
>> Tamam, büyük resim, diyelim
Bir saniye bir mola

120
00:05:43,935 --> 00:05:46,080
Nerede olduğumuzu ve anlamaya.

121
00:05:46,080 --> 00:05:48,580
Biz kimden başladıysanız
başından, biz

122
00:05:48,580 --> 00:05:51,640
şimdi tamamlamış
Genel dizi sadece

123
00:05:51,640 --> 00:05:53,810
Burada pseudocode kodunun bir adım.

124
00:05:53,810 --> 00:05:56,645
Biz sıralamış
Dizinin sol yarısı.

125
00:05:56,645 --> 00:05:59,490
>> Orijinal hatırlayın
Sipariş beş, iki, bir oldu.

126
00:05:59,490 --> 00:06:02,570
Bu süreçten geçiyor tarafından
aşağı yuvalama ve yinelenen,

127
00:06:02,570 --> 00:06:05,990
Sorunu kırmaya devam
Aşağı küçük ve daha küçük parçalar haline,

128
00:06:05,990 --> 00:06:09,670
Şimdi tamamlamış
pseudocode birini adım

129
00:06:09,670 --> 00:06:13,940
Tüm başlangıç ​​dizisi için.

130
00:06:13,940 --> 00:06:16,670
Biz onun sol yarısı sıralamış.

131
00:06:16,670 --> 00:06:18,670
>> Yani şimdi orada dondurma edelim.

132
00:06:18,670 --> 00:06:23,087
Ve şimdi hakkını sıralamak edelim
Orijinal dizinin yarısı.

133
00:06:23,087 --> 00:06:25,670
Ve biz tarafından o yapacağız
Aynı yinelemeli geçiyor

134
00:06:25,670 --> 00:06:30,630
şeyleri aşağı kırılma süreci
ve daha sonra onları bir arada birleştirilmesi.

135
00:06:30,630 --> 00:06:34,290
>> Yani sol yarısı
kırmızı veya sol yarım

136
00:06:34,290 --> 00:06:38,830
orijinal sağ yarısı
Dizi, söylemek için gidiyorum üçtür.

137
00:06:38,830 --> 00:06:40,312
Yine, ben burada tutarlı olmaya çalışıyorum.

138
00:06:40,312 --> 00:06:42,020
Eğer bir garip varsa
elemanların sayısı, o

139
00:06:42,020 --> 00:06:44,478
Gerçekten farketmez
Eğer sol bir küçük yapmak

140
00:06:44,478 --> 00:06:45,620
ya da doğru bir küçük.

141
00:06:45,620 --> 00:06:49,230
>> Önemli olan zaman sizi o
yürütürken bu sorunla karşılaştığınızda

142
00:06:49,230 --> 00:06:51,422
Bir birleştirme, tutarlı olması gerekir.

143
00:06:51,422 --> 00:06:53,505
Ya hep gerekir
Bir sol taraf daha küçük yapmak

144
00:06:53,505 --> 00:06:55,421
ya da her zaman yapmak gerekir
sağ tarafı daha küçük.

145
00:06:55,421 --> 00:06:57,720
Burada, ben her zaman seçtiniz
sol taraf daha küçük yapmak

146
00:06:57,720 --> 00:07:04,380
benim dizi veya benim
alt dizi, garip bir boyutudur.

147
00:07:04,380 --> 00:07:07,420
>> Üç tek unsurdur,
ve bu yüzden sıralanır.

148
00:07:07,420 --> 00:07:10,860
Biz bu varsayımı kaldıraçlı ettik
bizim tüm süreç boyunca şimdiye kadar.

149
00:07:10,860 --> 00:07:15,020
Yani şimdi hakkını sıralamak edelim
sağ yarısında yarısı,

150
00:07:15,020 --> 00:07:18,210
ya da kırmızı sağ yarısı.

151
00:07:18,210 --> 00:07:20,390
>> Yine, biz bu aşağı bölmek gerekir.

152
00:07:20,390 --> 00:07:21,910
Bu, tek bir unsur dizisi değil.

153
00:07:21,910 --> 00:07:23,970
Biz o tür beyan edemez.

154
00:07:23,970 --> 00:07:27,060
Ve böylece ilk, biz gidiyoruz
sol yarısı sıralamak için.

155
00:07:27,060 --> 00:07:31,620
>> Sol yarım, tek bir unsurdur,
yani varsayılan olarak çeşit var.

156
00:07:31,620 --> 00:07:34,840
Sonra sağa sıralamak için gidiyoruz
Tek bir öğedir yarısı.

157
00:07:34,840 --> 00:07:41,250
Varsayılan sıralama kriteri oluyor. Ve şimdi,
Beraber bu ikisini birleştirebilirsiniz.

158
00:07:41,250 --> 00:07:45,820
Dört küçük ve
Daha sonra altı küçüktür.

159
00:07:45,820 --> 00:07:48,870
>> Yine, ne bu noktada yapmış?

160
00:07:48,870 --> 00:07:52,512
Biz sol kriteri ettik
Sağ yarım yarım.

161
00:07:52,512 --> 00:07:54,720
Ya da orijinal geri dönüyor
vardı renkler,

162
00:07:54,720 --> 00:07:57,875
Biz sol kriteri ettik
yumuşak kırmızı yarısı.

163
00:07:57,875 --> 00:08:00,416
Başlangıçta koyu tuğla oldu
Kırmızı ve şimdi yumuşak bir kırmızı var,

164
00:08:00,416 --> 00:08:02,350
ya da bir yumuşak kırmızı oldu.

165
00:08:02,350 --> 00:08:05,145
>> Ve sonra biz kriteri ettik
yumuşak kırmızı sağ yarısı.

166
00:08:05,145 --> 00:08:08,270
Şimdi de, onlar sadece, yine yeşil konum
Biz bir süreçten geçiyoruz çünkü.

167
00:08:08,270 --> 00:08:10,720
Ve biz tekrarlamak zorunda
Bu tekrar ve tekrar.

168
00:08:10,720 --> 00:08:14,695
>> Yani şimdi o birleştirebilirsiniz
Birlikte iki yarısı.

169
00:08:14,695 --> 00:08:15,820
Ve biz burada ne var.

170
00:08:15,820 --> 00:08:17,653
Siyah çizgi Yani sadece
Sol ikiye bölünür

171
00:08:17,653 --> 00:08:19,690
ve bu tür kısmının sağ yarısı.

172
00:08:19,690 --> 00:08:24,310
>> Biz en küçük değeri karşılaştırmak
array-- sol tarafındaki

173
00:08:24,310 --> 00:08:26,710
ya afedersiniz, küçük
Sol yarısı değeri

174
00:08:26,710 --> 00:08:30,790
Sağ en küçük değere
Yarım ve üç küçük olduğunu bulmak.

175
00:08:30,790 --> 00:08:32,530
Ve şimdi bir optimizasyon biraz, değil mi?

176
00:08:32,530 --> 00:08:35,175
Hiçbir şey gerçekte var
Sol tarafta bıraktı.

177
00:08:35,175 --> 00:08:37,440
>> Kalan bir şey yok
sol tarafta,

178
00:08:37,440 --> 00:08:40,877
bu yüzden verimli olabilir
sadece biz ilan edebilir move--

179
00:08:40,877 --> 00:08:42,960
Gerisi aslında
sıralanır ve sadece tack

180
00:08:42,960 --> 00:08:45,126
hiçbir şey yok, çünkü üzerinde
karşılaştırmak için başka.

181
00:08:45,126 --> 00:08:49,140
Ve biz biliyoruz sağ tarafı
sağ tarafında sıralanır.

182
00:08:49,140 --> 00:08:52,770
>> Tamam, şimdi tekrar donmasına izin ve
Biz hikayenin neresinde olduğunu anlamaya.

183
00:08:52,770 --> 00:08:56,120
Genel dizide,
ne başardık?

184
00:08:56,120 --> 00:08:58,790
Biz aslında başarmak ettik
şimdi bir adım ve iki adımları tekrarlayın.

185
00:08:58,790 --> 00:09:03,300
Biz sol yarısı sıralanır ve
Doğru yarısını sıralanır.

186
00:09:03,300 --> 00:09:08,210
>> Yani şimdi, kaldığı hepimizin için
birlikte bu iki yarısını birleştirmek için.

187
00:09:08,210 --> 00:09:11,670
Bu yüzden en değerli karşılaştırmak
Dizinin her yarım elemanının

188
00:09:11,670 --> 00:09:13,510
ve sırayla devam edin.

189
00:09:13,510 --> 00:09:16,535
Bir üç daha azdır, böylece bir gider.

190
00:09:16,535 --> 00:09:19,770
>> İki, üç daha azdır, bu nedenle iki gider.

191
00:09:19,770 --> 00:09:22,740
Üç 5 den az, Yani üç gider.

192
00:09:22,740 --> 00:09:25,820
Dört 5 den az,, dört gider.

193
00:09:25,820 --> 00:09:30,210
Sonra beş, altı daha azdır
ve altı tüm kalır olduğunu.

194
00:09:30,210 --> 00:09:31,820
>> Şimdi, biliyorum, o adımları çok oldu.

195
00:09:31,820 --> 00:09:33,636
Ve biz çok bıraktık
Bizim sonrasında bellek.

196
00:09:33,636 --> 00:09:35,260
Ve o gri kareler ne olduğunu.

197
00:09:35,260 --> 00:09:40,540
Bu aldı gibi Ve muhtemelen keçe
Ekleme sıralama daha uzun lot, kabarcık

198
00:09:40,540 --> 00:09:42,660
sıralama veya seçim sıralama.

199
00:09:42,660 --> 00:09:45,330
>> Ama aslında, çünkü
Bu işlemlerin çok

200
00:09:45,330 --> 00:09:48,260
Aynı olan Zamanın de gerçekleşiyor
hangi yine yaparız şeydir

201
00:09:48,260 --> 00:09:51,100
biz hakkında konuşmak ne zaman hakkında konuşmak
gelecekteki bir yineleme video--

202
00:09:51,100 --> 00:09:53,799
aslında bu algoritma
açıkça temelde

203
00:09:53,799 --> 00:09:55,590
bir şey daha farklı
Daha önce gördüğümüz

204
00:09:55,590 --> 00:09:58,820
ancak önemli ölçüde aynı zamanda
daha verimli.

205
00:09:58,820 --> 00:09:59,532
>> Neden?

206
00:09:59,532 --> 00:10:01,240
Peki, en kötü
senaryo, biz

207
00:10:01,240 --> 00:10:04,830
n unsurları bölmek
ve sonra onları recombine.

208
00:10:04,830 --> 00:10:06,680
Ama biz recombine zaman
Onları, ne yapıyoruz

209
00:10:06,680 --> 00:10:11,110
temelde ikiye katlanıyor
Daha küçük dizilerin boyutu.

210
00:10:11,110 --> 00:10:14,260
Biz bir elemanın bir grup var
diziler biz etkin bir şekilde

211
00:10:14,260 --> 00:10:16,290
İki eleman diziler halinde birleştirir.

212
00:10:16,290 --> 00:10:18,590
Ve sonra biz o almak
İki element diziler

213
00:10:18,590 --> 00:10:21,890
ve içine birleştirebilirsiniz
böylece dört elemanlı bir dizi, ve

214
00:10:21,890 --> 00:10:26,130
ve böylece, ve böylece, biz gelene kadar
Tek n eleman dizi var.

215
00:10:26,130 --> 00:10:29,910
>> Ama kaç çiftlenmeler
o n almak için sürer?

216
00:10:29,910 --> 00:10:31,460
Geri telefon rehberi örnek düşünün.

217
00:10:31,460 --> 00:10:34,490
Kaç kere biz gözyaşı var
yarısında telefon rehberi, daha kaç

218
00:10:34,490 --> 00:10:38,370
kere telefon rehberini gözyaşı var
yarısında, eğer telefon rehberinin boyutu

219
00:10:38,370 --> 00:10:39,680
iki katına?

220
00:10:39,680 --> 00:10:41,960
Sadece bir sağ, yok mu?

221
00:10:41,960 --> 00:10:45,360
>> Yani bir çeşit var
Burada logaritmik unsur.

222
00:10:45,360 --> 00:10:48,590
Ama biz de hala var en azından
n tüm öğeleri bak.

223
00:10:48,590 --> 00:10:53,860
, En kötü durum senaryosunda Yani
sıralama n günlük n çalışır birleştirme.

224
00:10:53,860 --> 00:10:56,160
Biz bakmak zorunda
n bütün elemanları,

225
00:10:56,160 --> 00:11:02,915
ve biz onları birleştirmek zorunda
Birlikte günlük n adımlar setleri.

226
00:11:02,915 --> 00:11:05,290
En iyi senaryoya göre,
Dizi mükemmel sıralanır.

227
00:11:05,290 --> 00:11:06,300
Bu harika.

228
00:11:06,300 --> 00:11:09,980
Ama algoritmasına dayanan Biz burada var
biz hala bölünmüş ve rekombinasyona var.

229
00:11:09,980 --> 00:11:13,290
Bu durumda da,
yeniden birleştirici etkisiz türüdür.

230
00:11:13,290 --> 00:11:14,720
Bu gerekli değildir.

231
00:11:14,720 --> 00:11:17,580
Ama biz yine de geçmesi
Zaten bütün süreç.

232
00:11:17,580 --> 00:11:21,290
>> En iyi durumda Yani
ve en kötü durumda,

233
00:11:21,290 --> 00:11:24,970
Bu algoritma n günlüğüne n zaman içinde çalışır.

234
00:11:24,970 --> 00:11:29,130
Birleştirmeli sıralama kesinlikle biraz daha zordur
Diğer ana sıralama algoritmaları daha

235
00:11:29,130 --> 00:11:33,470
Biz CS50 hakkında konuştuk ama ettik
önemli ölçüde daha güçlü.

236
00:11:33,470 --> 00:11:35,400
>> Ve eğer öyleyse hiç bulmak
vesilesiyle ihtiyaç için

237
00:11:35,400 --> 00:11:38,480
veya sıralamak için kullanmak
Büyük veri seti, alıyorum

238
00:11:38,480 --> 00:11:41,940
özyineleme fikri etrafında başınızı
gerçekten güçlü olacak.

239
00:11:41,940 --> 00:11:45,270
Ve bunu yapmak için gidiyor senin
programlar gerçekten çok daha etkili

240
00:11:45,270 --> 00:11:48,700
başka bir şey karşı birleştirmeli sıralama kullanarak.

241
00:11:48,700 --> 00:11:49,640
Ben Doug Lloyd değilim.

242
00:11:49,640 --> 00:11:51,970
Bu CS50 olduğunu.

243
00:11:51,970 --> 00:11:53,826