در این مطلب، ویدئو ادغام مرتب سازی در پایتون توضیح داده شده (با مثال و کد) با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:13:35
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:02,490
سلام به همه و به آموزش من
2
00:00:02,490 –> 00:00:05,580
در مورد میرصاد خوش آمدید و اینکه چگونه می توانید این
3
00:00:05,580 –> 00:00:08,940
الگوریتم مرتب سازی را در پایتون در این آموزش پیاده سازی کنید
4
00:00:08,940 –> 00:00:10,679
من فقط می خواهم
5
00:00:10,679 –> 00:00:12,179
اصل کلی مرتب سازی ادغام را توضیح دهم
6
00:00:12,179 –> 00:00:14,190
بعد می خواهم یک مثال به شما نشان دهم
7
00:00:14,190 –> 00:00:16,859
و در پایان فقط می خواهم نشان دهم شما
8
00:00:16,859 –> 00:00:19,460
چگونه می توانید این الگوریتم را پیاده سازی کنید
9
00:00:19,460 –> 00:00:22,080
اول از همه مرتب سازی ادغام یک الگوریتم تقسیم و
10
00:00:22,080 –> 00:00:24,600
غلبه است به طور کلی این فقط
11
00:00:24,600 –> 00:00:26,460
به این معنی است که مسئله به
12
00:00:26,460 –> 00:00:29,429
چندین زیرمسئله تقسیم می شود و آن مسائل فرعی
13
00:00:29,429 –> 00:00:31,050
سپس توسط همان
14
00:00:31,050 –> 00:00:34,410
الگوریتم به زیرمسئله های بیشتری تقسیم می شوند و این
15
00:00:34,410 –> 00:00:37,230
روند ادامه دارد. تا زمانی که حل مسائل فرعی
16
00:00:37,230 –> 00:00:39,780
بسیار آسان شود زمانی که ما در
17
00:00:39,780 –> 00:00:42,270
این مرحله هستیم، مسائل فرعی با
18
00:00:42,270 –> 00:00:45,050
هم ترکیب می شوند تا مشکل اصلی حل شود،
19
00:00:45,050 –> 00:00:47,850
این احتمالاً وقتی با مثال میرصاد کار می کنیم بسیار منطقی خواهد بود.
20
00:00:47,850 –> 00:00:49,680
21
00:00:49,680 –> 00:00:52,860
نکته دیگر مرسیا این است
22
00:00:52,860 –> 00:00:53,430
که دارای
23
00:00:53,430 –> 00:00:57,239
oh از n بار log n زمان اجرا
24
00:00:57,239 –> 00:00:58,410
است که زمان اجرای بهینه برای
25
00:00:58,410 –> 00:01:02,760
الگوریتم های مبتنی بر مقایسه است، بنابراین فرض کنید
26
00:01:02,760 –> 00:01:04,530
می خواهیم یک آرایه را با استفاده از merge
27
00:01:04,530 –> 00:01:07,350
مرتب سازی ge مرتب کنیم. اصل عصبی این است که
28
00:01:07,350 –> 00:01:09,020
این آرایه را به نصف تقسیم کنیم و
29
00:01:09,020 –> 00:01:12,150
سپس مرتب سازی ادغام را در هر نیمه فراخوانی کنیم
30
00:01:12,150 –> 00:01:17,460
تا آن خانه به صورت بازگشتی مرتب شود و به عنوان
31
00:01:17,460 –> 00:01:20,850
مرحله سوم می خواهیم هر دو نیمه مرتب شده
32
00:01:20,850 –> 00:01:24,030
را در یک آرایه مرتب شده ادغام کنیم، بنابراین در اینجا می
33
00:01:24,030 –> 00:01:25,860
توانید این مش اصلی را تقسیم و غلبه کنید
34
00:01:25,860 –> 00:01:29,189
که فقط
35
00:01:29,189 –> 00:01:32,909
مشکل مرتبسازی یک آرایه کامل را به
36
00:01:32,909 –> 00:01:37,040
مرتبسازی دو ناحیه به اندازه نصف تقسیم میکند و
37
00:01:37,040 –> 00:01:40,860
این کار تا زمانی ادامه مییابد که فقط
38
00:01:40,860 –> 00:01:43,439
آرایههایی با اندازه یک برای مرتبسازی داشته باشیم و این مشکل
39
00:01:43,439 –> 00:01:44,909
بسیار آسان خواهد بود زیرا مناطق با اندازه
40
00:01:44,909 –> 00:01:47,670
یک همیشه مرتب میشوند تا این موضوع را بیشتر توضیح دهیم.
41
00:01:47,670 –> 00:01:49,170
میخواهم یک مثال به شما نشان دهم
42
00:01:49,170 –> 00:01:52,380
و این باید تمام
43
00:01:52,380 –> 00:01:55,610
جزئیات مرتبسازی ادغام را روشن کند،
44
00:01:56,180 –> 00:01:58,920
بنابراین اجازه دهید این ناحیه مثال
45
00:01:58,920 –> 00:02:02,280
هفت عدد را مرتب کنیم ابتدا با
46
00:02:02,280 –> 00:02:04,020
مرحله تقسیم مرتبسازی ادغام شروع میکنیم،
47
00:02:04,020 –> 00:02:06,540
بنابراین این آرایه به دو
48
00:02:06,540 –> 00:02:08,800
قسمت تقسیم میشود و
49
00:02:08,800 –> 00:02:10,960
ابتدا نگاه میکنیم. در نقطه میانی در
50
00:02:10,960 –> 00:02:12,610
این مورد، ما هفت عدد داریم، بنابراین یک
51
00:02:12,610 –> 00:02:14,170
طرف کمی بزرگتر از
52
00:02:14,170 –> 00:02:17,830
دیگری خواهد بود، اما این مشکلی ندارد، بنابراین ما فقط
53
00:02:17,830 –> 00:02:20,550
دو ناحیه فرعی را تقسیم کرده و به
54
00:02:20,550 –> 00:02:24,550
دو ناحیه جدید ذخیره می کنیم. و سپس این تقسیم
55
00:02:24,550 –> 00:02:28,720
به صورت بازگشتی ادامه می یابد، ابتدا به قسمت چپ نگاه می کنیم
56
00:02:28,720 –> 00:02:31,330
و آن را حتی بیشتر تقسیم می
57
00:02:31,330 –> 00:02:34,150
کنیم، سپس به زیر آرایه سمت راست نگاه می کنیم و
58
00:02:34,150 –> 00:02:37,180
این یکی را حتی بیشتر تقسیم می کنیم و این
59
00:02:37,180 –> 00:02:39,010
مرحله تقسیم تا زمانی ادامه می یابد که
60
00:02:39,010 –> 00:02:41,770
همه زیر آرایه ها فقط یک ورودی داشته باشند. سمت چپ،
61
00:02:41,770 –> 00:02:44,110
زیرا وقتی یک ورودی باقی مانده است،
62
00:02:44,110 –> 00:02:46,840
آرایه از قبل مرتب شده است و می
63
00:02:46,840 –> 00:02:49,450
توانیم با ترکیب شروع کنیم، اما اکنون به
64
00:02:49,450 –> 00:02:52,150
یک مرحله تقسیم دیگر نیاز داریم که ابتدا دو و
65
00:02:52,150 –> 00:02:54,010
یک شش به پنج تقسیم می شوند و
66
00:02:54,010 –> 00:02:56,560
یکی به 7 و قسمت تقسیم می شود. 4
67
00:02:56,560 –> 00:02:58,600
تقسیم می شود و 3 فعلاً دست نخورده باقی می ماند
68
00:02:58,600 –> 00:03:03,190
و همانطور که اکنون یک نظریه
69
00:03:03,190 –> 00:03:06,010
را به قسمت های فرعی تقسیم می کنیم که همه فقط یک
70
00:03:06,010 –> 00:03:08,590
عنصر دارند، اکنون می توانیم با مرحله ادغام شروع کنیم
71
00:03:08,590 –> 00:03:11,800
و اکنون آماده هستیم تا
72
00:03:11,800 –> 00:03:14,680
این آرایه های کوچکتر را در کمی بزرگتر ادغام کنیم.
73
00:03:14,680 –> 00:03:17,890
مناطقی که قبلا مرتب شده اند،
74
00:03:17,890 –> 00:03:19,420
بنابراین ما با 2 و 6 شروع می کنیم
75
00:03:19,420 –> 00:03:21,820
و اکنون می خواهیم 2 و 6 را به
76
00:03:21,820 –> 00:03:25,090
ترتیب درست بیاوریم، بنابراین با 6 مقایسه می کنیم
77
00:03:25,090 –> 00:03:28,050
و می بینیم که 2 کمتر از 6 است و
78
00:03:28,050 –> 00:03:30,490
ابتدا 2 را در جدید ذخیره می کنیم. آرایه و
79
00:03:30,490 –> 00:03:33,720
پس از آن ذخیره کنید 6 در این ناحیه جدید
80
00:03:33,720 –> 00:03:36,490
، همان رویه را برای 5
81
00:03:36,490 –> 00:03:40,120
و 1 اعمال می کنیم، ما 5 را به یکباره مقایسه می کنیم، می بینیم که 1
82
00:03:40,120 –> 00:03:43,420
کمتر از 5 است و 1 ایمن در آرایه جدید است
83
00:03:43,420 –> 00:03:46,630
و پس از آن 5
84
00:03:46,630 –> 00:03:49,810
دوباره برای 7 و 4 اعمال می شود.
85
00:03:49,810 –> 00:03:50,950
4 کمتر از 7 است
86
00:03:50,950 –> 00:03:54,970
و 4 را ذخیره می کند و بعد از آن 7
87
00:03:54,970 –> 00:03:57,010
3 فعلاً دست نخورده باقی می ماند و اکنون
88
00:03:57,010 –> 00:03:59,470
می توانیم آرایه هایی با اندازه 4 بسازیم که
89
00:03:59,470 –> 00:04:02,860
قبلا مرتب شده اند، بنابراین اکنون می خواهیم 2
90
00:04:02,860 –> 00:04:06,610
6 و 1 5 را به ترتیب درست بیاوریم.
91
00:04:06,610 –> 00:04:08,170
ما فقط باید چپ ترین
92
00:04:08,170 –> 00:04:11,230
عناصر هر دو آرایه را با هم مقایسه کنیم بنابراین 1 و 2 را با هم مقایسه می
93
00:04:11,230 –> 00:04:14,860
کنیم و می بینیم که 1 کمتر از 2 است بنابراین
94
00:04:14,860 –> 00:04:17,829
1 را در آرایه جدید ذخیره می کنیم و سپس
95
00:04:17,829 –> 00:04:21,230
می توانیم 2 و 5 را با هم مقایسه کنیم
96
00:04:21,230 –> 00:04:22,880
زیرا پنج اکنون چپ ترین عنصر است.
97
00:04:22,880 –> 00:04:25,520
در این ناحیه درست و می بینیم
98
00:04:25,520 –> 00:04:27,200
که کمتر از پنج را انتخاب می کنیم، بنابراین دو
99
00:04:27,200 –> 00:04:30,200
را در این آرایه جدید ذخیره می کنیم و اکنون فقط باید
100
00:04:30,200 –> 00:04:32,480
شش را با هم مقایسه کنیم و پنج را می بینیم که باید
101
00:04:32,480 –> 00:04:36,710
پنج را در این ناحیه جدید ذخیره کنیم و اکنون
102
00:04:36,710 –> 00:04:38,930
چیزی برای مقایسه شش تا وجود ندارد.
103
00:04:38,930 –> 00:04:40,670
بنابراین شش فقط برای انتقال آن به
104
00:04:40,670 –> 00:04:43,490
منطقه جدید است که می خواهیم یک ar بزرگتر بسازیم
105
00:04:43,490 –> 00:04:47,060
پرتو از چهار هفت و سه با
106
00:04:47,060 –> 00:04:51,590
اعمال همین رویه
107
00:04:51,590 –> 00:04:53,390
سه و چهار را با هم مقایسه می کنیم زیرا
108
00:04:53,390 –> 00:04:55,430
آنها سمت چپ ترین عناصر
109
00:04:55,430 –> 00:04:58,160
دو آرایه هستند می بینیم که 3 کمتر از 4 است و
110
00:04:58,160 –> 00:05:00,200
فقط 3 را در عنصر جدید ذخیره کرده و
111
00:05:00,200 –> 00:05:04,250
خط بزنید. بنابراین اکنون چیزی برای
112
00:05:04,250 –> 00:05:06,320
مقایسه 4 در 72 وجود ندارد و آنها در
113
00:05:06,320 –> 00:05:08,780
حال حاضر در ترتیب درستی هستند، بنابراین ما می
114
00:05:08,780 –> 00:05:13,940
توانیم آنها را به منطقه جدید منتقل کنیم، اکنون
115
00:05:13,940 –> 00:05:16,670
آخرین مرحله ادغام داریم که
116
00:05:16,670 –> 00:05:20,330
الگوریتم مرتب سازی ادغام ما را به پایان می رساند، در این
117
00:05:20,330 –> 00:05:22,610
مورد ما تازه شروع می کنیم با مقایسه یک و
118
00:05:22,610 –> 00:05:24,830
سه به دلیل اینکه یک و سه باقی مانده
119
00:05:24,830 –> 00:05:26,960
هیچ رسوبی نمی بینید که یکی کمتر از
120
00:05:26,960 –> 00:05:29,990
سه است و یکی را در منطقه جدید ذخیره
121
00:05:29,990 –> 00:05:33,830
می کنیم، سپس می توانیم دو و سه فروشگاه
122
00:05:33,830 –> 00:05:36,110
دو را در آرایه جدید جفت کنیم، سپس
123
00:05:36,110 –> 00:05:38,930
پنج و سه ذخیره سه را در آرایه جدید مقایسه می کنیم. آرایه جدید و
124
00:05:38,930 –> 00:05:43,040
سپس پنج و چهار را با هم مقایسه می کنیم که
125
00:05:43,040 –> 00:05:45,530
می توانیم در آرایه جدید ذخیره کنیم، سپس
126
00:05:45,530 –> 00:05:47,840
باید پنج و هفت را با هم مقایسه کنیم،
127
00:05:47,840 –> 00:05:51,260
7 را در آرایه جدید ذخیره می کنیم، سپس 6 و
128
00:05:51,260 –> 00:05:54,350
7 ما را در فروشگاه و منبع 6 را در آرایه جدید مقایسه
129
00:05:54,350 –> 00:05:57,920
می کنیم. فقط ما را با 7
130
00:05:57,920 –> 00:05:59,750
و ام باقی می گذارد e 7 فقط به ناحیه جدید منتقل می
131
00:05:59,750 –> 00:06:04,340
شود و دوباره این فقط
132
00:06:04,340 –> 00:06:06,260
اصل تقسیم و کنترل را نشان می دهد که ما
133
00:06:06,260 –> 00:06:08,990
آرایه را تقسیم کردیم تا زمانی که یک مشکل بسیار ساده
134
00:06:08,990 –> 00:06:12,170
از Eros داشتیم که فقط اندازه 1 را تنظیم کرده بود
135
00:06:12,170 –> 00:06:14,630
و قبلا مرتب شده بود و در مرحله ادغام
136
00:06:14,630 –> 00:06:17,480
ما فقط ترکیب بسیار کوچک آسان برای
137
00:06:17,480 –> 00:06:18,530
حل Ares
138
00:06:18,530 –> 00:06:22,520
– مناطق بزرگ تا زمانی که آرایه اولیه خود را
139
00:06:22,520 –> 00:06: