1
00:00:00,000 --> 00:00:04,419
>> [موسیقی]

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

3
00:00:05,401 --> 00:00:08,460
>> داگ لوید: خوب، پس یک ادغام
مرتب سازی بر اساس الگوریتم هنوز یکی دیگر از

4
00:00:08,460 --> 00:00:11,200
که ما می توانیم به مرتب کردن استفاده
عناصر یک آرایه.

5
00:00:11,200 --> 00:00:14,480
اما همانطور که خواهیم دید، آن را به یک
تفاوت بسیار اساسی

6
00:00:14,480 --> 00:00:17,850
از مرتب سازی انتخابی، حباب
مرتب کردن، و مرتب سازی درجی

7
00:00:17,850 --> 00:00:20,280
که آن را واقعا خیلی هوشمندانه.

8
00:00:20,280 --> 00:00:24,290
>> ایده اصلی در پشت ادغام
مرتب سازی بر است برای مرتب کردن آرایه های کوچکتر

9
00:00:24,290 --> 00:00:27,430
و سپس ترکیب آن آرایه
با هم، و یا ادغام them--

10
00:00:27,430 --> 00:00:31,440
از این رو در name-- مرتب شده اند.

11
00:00:31,440 --> 00:00:34,230
راه که ادغام مرتب سازی بر کند
این است با اعمال نفوذ یک ابزار

12
00:00:34,230 --> 00:00:37,290
به نام بازگشت، آن چیزی است که
ما در حال رفتن به صحبت کردن در مورد به زودی،

13
00:00:37,290 --> 00:00:39,720
اما ما واقعا در مورد هنوز صحبت نمی کند.

14
00:00:39,720 --> 00:00:43,010
>> در اینجا ایده اصلی در پشت مرتب سازی بر ادغام است.

15
00:00:43,010 --> 00:00:46,320
مرتب کردن بر اساس نیمه سمت چپ از آرایه،
فرض n بزرگتر از 1 است.

16
00:00:46,320 --> 00:00:49,980
و آنچه که من وقتی می گویم
فرض n بزرگتر از 1 است،

17
00:00:49,980 --> 00:00:53,970
من فکر می کنم ما می توانیم که اگر یک آرایه
تنها متشکل از یک عنصر،

18
00:00:53,970 --> 00:00:54,680
آن طبقه بندی شده اند.

19
00:00:54,680 --> 00:00:56,560
ما در واقع لازم نیست
برای انجام هر کاری به آن است.

20
00:00:56,560 --> 00:00:58,059
ما فقط می تواند اعلام آن را به طبقه بندی شده اند.

21
00:00:58,059 --> 00:01:00,110
این تنها یک عنصر است.

22
00:01:00,110 --> 00:01:03,610
>> بنابراین شبه دوباره است،
مرتب کردن بر اساس نیمه سمت چپ آرایه،

23
00:01:03,610 --> 00:01:08,590
سپس به ترتیب در نیمه سمت راست آرایه،
پس از آن با هم ادغام دو نیمه.

24
00:01:08,590 --> 00:01:11,040
در حال حاضر، در حال حاضر شما ممکن است
فکر کردن، آن هم از نوع فقط

25
00:01:11,040 --> 00:01:14,080
برای تلفن های موبایل مانند شما در حال قرار دادن the--
شما در واقع انجام هر چیزی نیست.

26
00:01:14,080 --> 00:01:16,330
شما می گویید مرتب سازی بر اساس سمت چپ
نیم، مرتب کردن بر اساس نیمه سمت راست،

27
00:01:16,330 --> 00:01:19,335
اما شما در حال گفتن نیست
من چگونه شما آن را انجام می دهند.

28
00:01:19,335 --> 00:01:22,220
>> اما به یاد داشته باشید که تا زمانی که
یک آرایه یک عنصر است،

29
00:01:22,220 --> 00:01:23,705
ما می تواند اعلام آن طبقه بندی شده اند.

30
00:01:23,705 --> 00:01:25,330
سپس ما فقط می توانید آنها را با هم ترکیب.

31
00:01:25,330 --> 00:01:27,788
و این در واقع
ایده اساسی که پشت مرتب سازی بر ادغام،

32
00:01:27,788 --> 00:01:31,150
است به شکستن آن به طوری که
آرایه های خود را از اندازه یکی هستند.

33
00:01:31,150 --> 00:01:33,430
و سپس شما را از وجود دارد را بازسازی کند.

34
00:01:33,430 --> 00:01:35,910
>> مرتبسازی ادغامی است که قطعا
یک الگوریتم پیچیده است.

35
00:01:35,910 --> 00:01:38,210
و آن را نیز کمی
پیچیده به تجسم.

36
00:01:38,210 --> 00:01:41,870
پس امیدوارم، تجسم که من
در اینجا به شما کمک خواهد به دنبال همراه.

37
00:01:41,870 --> 00:01:45,640
و من سعی کنید بهترین من به روایت همه چیز
و ادامه طریق این کمی بیشتر

38
00:01:45,640 --> 00:01:49,180
به آرامی از آنهایی که دیگر
فقط به امید گرفتن سر خود را

39
00:01:49,180 --> 00:01:51,800
در اطراف ایده پشت مرتب سازی بر ادغام.

40
00:01:51,800 --> 00:01:54,680
>> بنابراین ما باید آرایه همان
فیلم های دیگر الگوریتم مرتب سازی

41
00:01:54,680 --> 00:01:57,120
اگر شما را دیده ام them--
یک آرایه شش عنصر است.

42
00:01:57,120 --> 00:02:02,110
و کد شبه ما در اینجا این است مرتب سازی بر
نیمه چپ، مرتب کردن نیمه سمت راست،

43
00:02:02,110 --> 00:02:03,890
با هم ادغام دو نیمه.

44
00:02:03,890 --> 00:02:09,770
بنابراین اجازه دهید این آجر قرمز بسیار تاریک
آرایه و مرتب کردن نیمه سمت چپ آن است.

45
00:02:09,770 --> 00:02:13,380
>> بنابراین در حال حاضر، ما قصد داریم
به چشم پوشی از مسائل در سمت راست.

46
00:02:13,380 --> 00:02:15,740
آن وجود دارد، اما ما
که در آن گام نشده است.

47
00:02:15,740 --> 00:02:18,220
ما نه در مرتب کردن بر اساس
نیمه راست آرایه.

48
00:02:18,220 --> 00:02:21,037
ما در مرتب سازی بر سمت چپ هستید
نیمی از آرایه.

49
00:02:21,037 --> 00:02:22,870
و فقط به خاطر
بودن کمی بیشتر

50
00:02:22,870 --> 00:02:26,480
روشن است، بنابراین من می توانید مراجعه کنید
به چه مرحله ما در آن هستید،

51
00:02:26,480 --> 00:02:29,800
من قصد دارم برای تغییر
رنگ این مجموعه به رنگ نارنجی.

52
00:02:29,800 --> 00:02:33,190
در حال حاضر، ما در حال صحبت کردن در هنوز هم در مورد
نیمه سمت چپ همان آرایه اصلی.

53
00:02:33,190 --> 00:02:38,520
اما من امیدوار است که قادر بودن به
به رنگ از آیتم های مختلف مراجعه کنید،

54
00:02:38,520 --> 00:02:40,900
آن را آن را کمی بیشتر را
روشن چه خبر است اینجا.

55
00:02:40,900 --> 00:02:43,270
>> OK، بنابراین در حال حاضر ما یک
سه عنصر آرایه.

56
00:02:43,270 --> 00:02:46,420
چگونه نیمه سمت چپ این که ما مرتب سازی بر اساس
آرایه، که هنوز هم این مرحله؟

57
00:02:46,420 --> 00:02:49,400
ما در حال تلاش برای مرتب کردن سمت چپ
نیمی از آجر قرمز آرایه

58
00:02:49,400 --> 00:02:52,410
نیمه سمت چپ که
من در حال حاضر رنگ نارنجی است.

59
00:02:52,410 --> 00:02:54,840
>> خب، ما می تواند امتحان کنید و
دوباره این روند را تکرار.

60
00:02:54,840 --> 00:02:56,756
بنابراین ما هنوز هم در حال
وسط تلاش برای

61
00:02:56,756 --> 00:02:58,700
نیمه چپ آرایه کامل.

62
00:02:58,700 --> 00:03:00,450
نیمه سمت چپ از
آرایه، من فقط رفتن

63
00:03:00,450 --> 00:03:03,910
به خودسرانه تصمیم می گیرید که نیمه سمت چپ
کوچکتر از نیمه سمت راست خواهد بود،

64
00:03:03,910 --> 00:03:06,550
چرا که این اتفاق می افتد به
شامل سه عنصر است.

65
00:03:06,550 --> 00:03:11,260
>> و به این ترتیب من قصد دارم به می گویند که
نیمه چپ نیمه سمت چپ آرایه

66
00:03:11,260 --> 00:03:14,050
فقط پنج عنصر است.

67
00:03:14,050 --> 00:03:18,360
پنج، که یک عنصر
آرایه، ما می دانیم چگونه به آن را مرتب.

68
00:03:18,360 --> 00:03:21,615
و به این ترتیب پنج طبقه بندی شده اند است.

69
00:03:21,615 --> 00:03:22,990
ما فقط قصد داریم تا اعلام کند که.

70
00:03:22,990 --> 00:03:24,890
این یک آرایه عنصر است.

71
00:03:24,890 --> 00:03:29,015
>> بنابراین ما در حال حاضر طبقه بندی شده اند ام
نیمه چپ چپ half--

72
00:03:29,015 --> 00:03:33,190
و یا نه، ما طبقه بندی شده اند ام
نیمه سمت چپ نارنجی.

73
00:03:33,190 --> 00:03:37,970
بنابراین در حال حاضر، به منظور هنوز هم کامل
نیمه چپ آرایه کلی است،

74
00:03:37,970 --> 00:03:43,481
ما نیاز به مرتب کردن نیمه سمت راست
از نارنجی، و یا این مسائل.

75
00:03:43,481 --> 00:03:44,230
چگونه ما انجام این کار؟

76
00:03:44,230 --> 00:03:45,930
خب، ما باید یک آرایه دو عنصر است.

77
00:03:45,930 --> 00:03:50,470
بنابراین ما می توانیم نیمه سمت چپ مرتب سازی بر اساس
از آرایه است، که دو.

78
00:03:50,470 --> 00:03:52,090
دو یک عنصر است.

79
00:03:52,090 --> 00:03:55,890
پس از آن به طور پیش فرض طبقه بندی شده اند.
پس ما می توانیم در نیمه سمت راست مرتب سازی بر اساس

80
00:03:55,890 --> 00:03:58,530
آن بخش از آرایه، یک.

81
00:03:58,530 --> 00:04:00,210
که مرتب سازی بر اساس پیش فرض.

82
00:04:00,210 --> 00:04:03,610
>> این در حال حاضر اولین بار
ما یک قدم ادغام رسیدهاید.

83
00:04:03,610 --> 00:04:06,135
ما را تکمیل کرده اند، اگر چه
ما در حال حاضر از نوع تو در تو down--

84
00:04:06,135 --> 00:04:08,420
و آن نوع از روی حیله و تزویر است
چیزی که با بازگشتی است

85
00:04:08,420 --> 00:04:10,930
شما نیاز به نگه داشتن خود را
سر در مورد که در آن ما هستند.

86
00:04:10,930 --> 00:04:15,560
بنابراین ما به نوعی از سمت چپ
نیمی از بخش نارنجی.

87
00:04:15,560 --> 00:04:21,280
>> و اکنون، ما در وسط مرتب سازی هستید
نیمه راست بخش نارنجی.

88
00:04:21,280 --> 00:04:25,320
و در این فرآیند، ما
در حال حاضر حدود به گام باشد،

89
00:04:25,320 --> 00:04:27,850
با هم ادغام دو نیمه.

90
00:04:27,850 --> 00:04:31,700
هنگامی که ما در دو نیمه نگاه
از آرایه، ما دو و یک را ببینید.

91
00:04:31,700 --> 00:04:33,880
کدام عنصر کوچکتر است؟

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

93
00:04:35,160 --> 00:04:36,760
>> پس از آن که عنصر کوچکتر است؟

94
00:04:36,760 --> 00:04:38,300
خوب، آن را دو یا هیچ چیز نیست.

95
00:04:38,300 --> 00:04:39,910
پس از آن دو.

96
00:04:39,910 --> 00:04:43,690
بنابراین در حال حاضر، فقط به دوباره قاب
که در آن ما در زمینه هستند،

97
00:04:43,690 --> 00:04:48,230
ما مرتب سازی بر حسب
نیمه سمت چپ نارنجی

98
00:04:48,230 --> 00:04:49,886
و نیمه سمت راست از مبدا.

99
00:04:49,886 --> 00:04:52,510
من می دانم من رنگ را تغییر داده ام
دوباره، اما این که در آن ما بود.

100
00:04:52,510 --> 00:04:54,676
و به همین دلیل من این
است چرا که این فرآیند است

101
00:04:54,676 --> 00:04:57,870
رفتن به رفتن ادامه، تکرار است.

102
00:04:57,870 --> 00:05:00,500
ما در سمت چپ طبقه بندی شده اند که
نیمی از پرتقال سابق

103
00:05:00,500 --> 00:05:02,590
و نیمه سمت راست از رنگ نارنجی سابق.

104
00:05:02,590 --> 00:05:05,620
>> در حال حاضر ما نیاز به ادغام آن
دو نیمه با هم بیش از حد.

105
00:05:05,620 --> 00:05:07,730
که گام ما در هستیم.

106
00:05:07,730 --> 00:05:11,440
بنابراین ما همه از نظر
عناصر که در حال حاضر سبز،

107
00:05:11,440 --> 00:05:12,972
نیمه چپ آرایه اصلی.

108
00:05:12,972 --> 00:05:14,680
و کسانی را ادغام
استفاده از روند مشابه

109
00:05:14,680 --> 00:05:18,660
ما برای ادغام دو بود
و یکی فقط یک لحظه پیش.

110
00:05:18,660 --> 00:05:23,080
>> نیمه چپ، کوچکترین
عنصر در نیمه سمت چپ و پنج است.

111
00:05:23,080 --> 00:05:25,620
کوچکترین عنصر در
در نیمه سمت راست است.

112
00:05:25,620 --> 00:05:27,370
کدام یک از این کوچکتر است؟

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

114
00:05:29,260 --> 00:05:32,250
>> کوچکترین عنصر در
نیمه سمت چپ و پنج است.

115
00:05:32,250 --> 00:05:35,540
کوچکترین عنصر در
در نیمه سمت راست دو است.

116
00:05:35,540 --> 00:05:36,970
چه کوچکترین خبر؟

117
00:05:36,970 --> 00:05:38,160
دو.

118
00:05:38,160 --> 00:05:41,540
و سپس در آخر پنج و
هیچ چیز، ما می توانیم پنج گویند.

119
00:05:41,540 --> 00:05:43,935
>> OK، تصویر بسیار بزرگ، اجازه دهید
استراحت برای یک ثانیه

120
00:05:43,935 --> 00:05:46,080
و کشف کردن که در آن ما هستند.

121
00:05:46,080 --> 00:05:48,580
اگر ما از آغاز
همان ابتدا، ما

122
00:05:48,580 --> 00:05:51,640
در حال حاضر برای تکمیل
آرایه به طور کلی فقط

123
00:05:51,640 --> 00:05:53,810
یک قدم از کد شبه در اینجا.

124
00:05:53,810 --> 00:05:56,645
ما طبقه بندی شده اند کرده اند
نیمه سمت چپ آرایه.

125
00:05:56,645 --> 00:05:59,490
>> به یاد بیاورید که اصلی
سفارش پنج، دو، یک بود.

126
00:05:59,490 --> 00:06:02,570
رفتن را از طریق این فرآیند
و تودرتو و تکرار،

127
00:06:02,570 --> 00:06:05,990
در ادامه به شکستن مشکل
را به قطعات کوچکتر و کوچکتر،

128
00:06:05,990 --> 00:06:09,670
ما در حال حاضر به اتمام
مرحله یکی از شبه

129
00:06:09,670 --> 00:06:13,940
برای کل آرایه شروع.

130
00:06:13,940 --> 00:06:16,670
ما نیمه چپ آن طبقه بندی شده اند.

131
00:06:16,670 --> 00:06:18,670
>> بنابراین در حال حاضر مسدود است.

132
00:06:18,670 --> 00:06:23,087
و اکنون اجازه دهید در سمت راست مرتب سازی بر اساس
نیمی از آرایه اصلی است.

133
00:06:23,087 --> 00:06:25,670
و ما قصد داریم به این کار را با
رفتن را از طریق تکرار همان

134
00:06:25,670 --> 00:06:30,630
روند شکستن همه چیز
و سپس آنها را ادغام با هم.

135
00:06:30,630 --> 00:06:34,290
>> بنابراین نیمه سمت چپ
قرمز، و یا نیمه سمت چپ

136
00:06:34,290 --> 00:06:38,830
از نیمه سمت راست از اصلی
آرایه، من قصد دارم به سه است.

137
00:06:38,830 --> 00:06:40,312
باز هم، من سازگار بودن در اینجا.

138
00:06:40,312 --> 00:06:42,020
اگر شما یک فرد
تعدادی از عناصر آن،

139
00:06:42,020 --> 00:06:44,478
واقعا مهم نیست که آیا
شما را به سمت چپ کوچکتر

140
00:06:44,478 --> 00:06:45,620
و یا یک حق کوچکتر است.

141
00:06:45,620 --> 00:06:49,230
>> مهم این است که هر زمان که شما
این مشکل روبرو می شوند در انجام

142
00:06:49,230 --> 00:06:51,422
ادغام، شما نیاز به سازگار است.

143
00:06:51,422 --> 00:06:53,505
شما هم همیشه نیاز به
یک سمت چپ کوچکتر

144
00:06:53,505 --> 00:06:55,421
و یا همیشه نیاز به
در سمت راست کوچکتر است.

145
00:06:55,421 --> 00:06:57,720
در اینجا، من برای همیشه انتخاب کرده اید
را در سمت چپ کوچکتر

146
00:06:57,720 --> 00:07:04,380
وقتی آرایه من، یا من
زیر آرایه است، از اندازه عجیب و غریب.

147
00:07:04,380 --> 00:07:07,420
>> سه یک عنصر است،
و پس از آن طبقه بندی شده اند است.

148
00:07:07,420 --> 00:07:10,860
ما این فرضیه را قوی تر
در سراسر کل فرآیند ما تا کنون.

149
00:07:10,860 --> 00:07:15,020
پس به سمت راست مرتب سازی بر اساس
نیمی از نیمه سمت راست،

150
00:07:15,020 --> 00:07:18,210
و یا نیمه سمت راست از رنگ قرمز است.

151
00:07:18,210 --> 00:07:20,390
>> باز هم، ما نیاز به تقسیم این پایین.

152
00:07:20,390 --> 00:07:21,910
این یک آرایه عنصر است.

153
00:07:21,910 --> 00:07:23,970
ما نمی توانیم اعلام آن به طبقه بندی شده اند.

154
00:07:23,970 --> 00:07:27,060
و به این ترتیب برای اولین بار، ما قصد داریم
مرتب سازی بر اساس نیمه سمت چپ.

155
00:07:27,060 --> 00:07:31,620
>> نیمه چپ یک عنصر است،
پس از آن نوع به طور پیش فرض.

156
00:07:31,620 --> 00:07:34,840
سپس ما قصد داریم برای مرتب کردن سمت راست
نیمه است، که یک عنصر واحد.

157
00:07:34,840 --> 00:07:41,250
آن را به طور پیش فرض طبقه بندی شده اند. و در حال حاضر،
ما می توانیم آن دو با هم ادغام خواهند شد.

158
00:07:41,250 --> 00:07:45,820
چهار کوچکتر است، و
سپس شش کوچکتر است.

159
00:07:45,820 --> 00:07:48,870
>> باز هم، آنچه را که ما در این نقطه انجام می شود؟

160
00:07:48,870 --> 00:07:52,512
ما در سمت چپ طبقه بندی شده اند که
نیمی از نیمه سمت راست.

161
00:07:52,512 --> 00:07:54,720
و یا رفتن به اصلی
رنگ هایی که وجود دارد،

162
00:07:54,720 --> 00:07:57,875
ما در سمت چپ طبقه بندی شده اند که
نیمی از قرمز نرمتر است.

163
00:07:57,875 --> 00:08:00,416
این در اصل یک آجر تاریک
قرمز و در حال حاضر آن را به یک نرم تر قرمز،

164
00:08:00,416 --> 00:08:02,350
و یا آن را به یک قرمز نرمتر بود.

165
00:08:02,350 --> 00:08:05,145
>> و سپس ما طبقه بندی شده اند ام
نیمه راست قرمز نرمتر است.

166
00:08:05,145 --> 00:08:08,270
در حال حاضر، خوب، آنها دوباره سبز هستید، فقط
چون ما قصد از طریق یک فرایند.

167
00:08:08,270 --> 00:08:10,720
و ما مجبور به تکرار
این بارها و بارها.

168
00:08:10,720 --> 00:08:14,695
>> بنابراین در حال حاضر ما می توانیم آن ادغام
دو نیمه با هم.

169
00:08:14,695 --> 00:08:15,820
و این چیزی است که ما در اینجا انجام.

170
00:08:15,820 --> 00:08:17,653
به طوری که خط سیاه و سفید فقط
نیمه چپ تقسیم

171
00:08:17,653 --> 00:08:19,690
و نیمه سمت راست این بخش مرتب سازی بر.

172
00:08:19,690 --> 00:08:24,310
>> ما به مقایسه کوچکترین مقدار
در سمت چپ از آرایه

173
00:08:24,310 --> 00:08:26,710
و یا ببخشید، کوچکترین
ارزش نیمه سمت چپ

174
00:08:26,710 --> 00:08:30,790
به کوچکترین ارزش سمت راست
نیمه و پیدا کردن که سه کوچکتر است.

175
00:08:30,790 --> 00:08:32,530
و در حال حاضر یک بیت از یک بهینه سازی، درست است؟

176
00:08:32,530 --> 00:08:35,175
در واقع وجود دارد هیچ چیز
در سمت چپ در سمت چپ.

177
00:08:35,175 --> 00:08:37,440
>> هیچ چیز باقی مانده وجود دارد
در سمت چپ،

178
00:08:37,440 --> 00:08:40,877
بنابراین ما کارآمد می تواند
فقط move-- ما می تواند اعلام

179
00:08:40,877 --> 00:08:42,960
بقیه از آن است که در واقع
طبقه بندی شده اند و فقط آن را رویه

180
00:08:42,960 --> 00:08:45,126
، چرا که هیچ چیز وجود دارد
دیگری برای مقایسه با

181
00:08:45,126 --> 00:08:49,140
و ما می دانیم که در سمت راست
از سمت راست طبقه بندی شده اند است.

182
00:08:49,140 --> 00:08:52,770
>> خوب، پس حالا بیایید دوباره منجمد و
شکل که در آن ما در داستان هستند.

183
00:08:52,770 --> 00:08:56,120
در آرایه به طور کلی،
چه انجام دهیم؟

184
00:08:56,120 --> 00:08:58,790
ما در واقع انجام
در حال حاضر یکی و گام به گام دو مرحله است.

185
00:08:58,790 --> 00:09:03,300
ما طبقه بندی شده اند در نیمه سمت چپ، و
ما در نیمه سمت راست طبقه بندی شده اند.

186
00:09:03,300 --> 00:09:08,210
>> بنابراین در حال حاضر، که باقی می ماند این است که برای ما
به ادغام این دو نیمه با هم.

187
00:09:08,210 --> 00:09:11,670
بنابراین ما به مقایسه کمترین ارزش
عنصر هر نیمی از آرایه

188
00:09:11,670 --> 00:09:13,510
به نوبه خود و ادامه دهید.

189
00:09:13,510 --> 00:09:16,535
یکی کمتر از سه است، بنابراین یک می رود.

190
00:09:16,535 --> 00:09:19,770
>> دو کمتر از سه است، بنابراین دو می رود.

191
00:09:19,770 --> 00:09:22,740
سه کمتر از 5 است، پس از سه رود.

192
00:09:22,740 --> 00:09:25,820
چهار کمتر از 5 است، بنابراین چهار می رود.

193
00:09:25,820 --> 00:09:30,210
پس از آن پنج کمتر از شش است،
و شش است که باقی می ماند.

194
00:09:30,210 --> 00:09:31,820
>> در حال حاضر، من می دانم، که بسیاری از مراحل بود.

195
00:09:31,820 --> 00:09:33,636
و ما بسیاری را ترک کرده ام
حافظه در پی ما است.

196
00:09:33,636 --> 00:09:35,260
و این چیزی است که کسانی که مربع خاکستری هستند.

197
00:09:35,260 --> 00:09:40,540
و آن را احتمالا احساس که در زمان
بسیاری دیگر از مرتب سازی بر درج، حباب

198
00:09:40,540 --> 00:09:42,660
مرتب سازی بر اساس، و یا انتخاب نوع.

199
00:09:42,660 --> 00:09:45,330
>> اما در واقع، به دلیل
بسیاری از این فرآیندها

200
00:09:45,330 --> 00:09:48,260
ها در همان اتفاق می افتد time--
چیزی خواهیم که، دوباره،

201
00:09:48,260 --> 00:09:51,100
صحبت در مورد زمانی که ما در مورد صحبت
بازگشت در آینده video--

202
00:09:51,100 --> 00:09:53,799
این الگوریتم در واقع
به وضوح اساسا

203
00:09:53,799 --> 00:09:55,590
متفاوت از هر چیزی
ما دیده اند، قبل

204
00:09:55,590 --> 00:09:58,820
اما همچنین به طور قابل توجهی
کارآمدتر.

205
00:09:58,820 --> 00:09:59,532
>> چرا چنین است؟

206
00:09:59,532 --> 00:10:01,240
خب، در بدترین
سناریو مورد، ما

207
00:10:01,240 --> 00:10:04,830
به تقسیم n عنصر تا
و سپس آنها را ترکیب.

208
00:10:04,830 --> 00:10:06,680
اما زمانی که ما ترکیب
آنها، آنچه ما انجام می

209
00:10:06,680 --> 00:10:11,110
است که اساسا دو برابر شدن
اندازه آرایه کوچکتر است.

210
00:10:11,110 --> 00:10:14,260
ما یک دسته از یک عنصر
آرایه که ما به طور موثر

211
00:10:14,260 --> 00:10:16,290
ترکیب را به دو آرایه عنصر.

212
00:10:16,290 --> 00:10:18,590
و سپس ما آن را
دو آرایه عنصر

213
00:10:18,590 --> 00:10:21,890
و آنها را با هم ترکیب را به
چهار رشته عنصر، و غیره،

214
00:10:21,890 --> 00:10:26,130
و غیره، و غیره، تا زمانی که ما
باید یک آرایه از عناصر N است.

215
00:10:26,130 --> 00:10:29,910
>> اما چگونه بسیاری از دوبرابر شدن
آن را برای رسیدن به N؟

216
00:10:29,910 --> 00:10:31,460
فکر می کنم به عنوان مثال دفترچه تلفن.

217
00:10:31,460 --> 00:10:34,490
چند بار ما باید به پاره
دفترچه تلفن در نیمه، که چگونه بسیاری از

218
00:10:34,490 --> 00:10:38,370
بار ما باید به پاره دفترچه تلفن
در نیم، اگر به اندازه دفترچه تلفن

219
00:10:38,370 --> 00:10:39,680
دو برابر؟

220
00:10:39,680 --> 00:10:41,960
فقط یک وجود دارد، درست است؟

221
00:10:41,960 --> 00:10:45,360
>> بنابراین برخی از مرتب کردن بر اساس وجود دارد
عنصر لگاریتمی است.

222
00:10:45,360 --> 00:10:48,590
اما ما نیز هنوز به حداقل
در همه عناصر N نگاه کنید.

223
00:10:48,590 --> 00:10:53,860
بنابراین در بدترین حالت،
مرتبسازی ادغامی در n log n استفاده می کند.

224
00:10:53,860 --> 00:10:56,160
ما به در نگاه کنید
همه عناصر ازت،

225
00:10:56,160 --> 00:11:02,915
و ما باید آنها را ترکیب
ورود به سیستم با هم در N مجموعه ای از مراحل.

226
00:11:02,915 --> 00:11:05,290
در بهترین حالت،
آرایه کاملا طبقه بندی شده اند.

227
00:11:05,290 --> 00:11:06,300
عالیه.

228
00:11:06,300 --> 00:11:09,980
اما بر اساس الگوریتم ما را در اینجا،
ما هنوز به تقسیم و ترکیب.

229
00:11:09,980 --> 00:11:13,290
اگر چه در این مورد،
بازترکیب نوع بی اثر است.

230
00:11:13,290 --> 00:11:14,720
این مورد نیاز است.

231
00:11:14,720 --> 00:11:17,580
اما ما هنوز هم از طریق رفتن
کل فرایند به هر حال.

232
00:11:17,580 --> 00:11:21,290
>> بنابراین در بهترین حالت
و در بدترین حالت،

233
00:11:21,290 --> 00:11:24,970
این الگوریتم را اجرا می کند در n log n استفاده می شود.

234
00:11:24,970 --> 00:11:29,130
مرتبسازی ادغامی است که قطعا یک کمی سختتر
از دیگر الگوریتم های مرتب سازی اصلی

235
00:11:29,130 --> 00:11:33,470
ما در مورد CS50 صحبت کردیم اما
قابل ملاحظه ای قوی تر است.

236
00:11:33,470 --> 00:11:35,400
>> و بنابراین اگر شما همیشه پیدا
مناسبت به آن نیاز دارید

237
00:11:35,400 --> 00:11:38,480
و یا استفاده از آن برای مرتب کردن بر اساس
مجموعه بزرگ داده ها، گرفتن

238
00:11:38,480 --> 00:11:41,940
سر خود را در اطراف این ایده از بازگشت
در حال رفتن به واقعا قدرتمند است.

239
00:11:41,940 --> 00:11:45,270
و آن را به خود
برنامه های واقعا بسیار کارآمد تر

240
00:11:45,270 --> 00:11:48,700
با استفاده از ادغام مرتب سازی بر در مقابل هر چیز دیگری.

241
00:11:48,700 --> 00:11:49,640
من داگ لوید هستم.

242
00:11:49,640 --> 00:11:51,970
این CS50 است.

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