در این مطلب، ویدئو مرتب سازی پوسته – ساختار داده ها و الگوریتم ها آموزش پایتون شماره 18 با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:18:32
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,719 –> 00:00:03,760
ما
2
00:00:03,760 –> 00:00:05,839
طبق معمول یک الگوریتم مرتبسازی مهم دیگر به نام cell short
3
00:00:05,839 –> 00:00:07,680
را مرور میکنیم، سپس برخی از نظریهها را مرور
4
00:00:07,680 –> 00:00:09,679
میکنیم، سپس کدنویسی را در پایتون انجام میدهیم و
5
00:00:09,679 –> 00:00:12,240
در پایان یک سلول تمرین
6
00:00:12,240 –> 00:00:14,960
کوتاه خواهیم داشت که یک مرتبسازی بهینهسازی یا درج است.
7
00:00:14,960 –> 00:00:15,920
اگر
8
00:00:15,920 –> 00:00:17,840
در مورد عکس درج نمیدانید،
9
00:00:17,840 –> 00:00:19,840
پیشنهاد میکنم ویدیوی کوتاه درج من را
10
00:00:19,840 –> 00:00:21,199
در همان
11
00:00:21,199 –> 00:00:24,080
لیست پخش تماشا کنید، فرض کنید این نوع
12
00:00:24,080 –> 00:00:24,640
آرایه
13
00:00:24,640 –> 00:00:27,680
را دارید، ابتدا به نحوه عملکرد عکسهای درج میپردازیم،
14
00:00:27,680 –> 00:00:28,240
15
00:00:28,240 –> 00:00:30,640
بنابراین درج کوتاه را با
16
00:00:30,640 –> 00:00:33,040
اولین عنصر شروع میکنیم که 21 است
17
00:00:33,040 –> 00:00:35,520
و عناصری که
18
00:00:35,520 –> 00:00:36,320
19
00:00:36,320 –> 00:00:38,559
در سمت چپ این
20
00:00:38,559 –> 00:00:39,360
21
00:00:39,360 –> 00:00:42,000
فلش زرد خاکستری هستند، آرایه مرتب شده شماست هر چیزی که
22
00:00:42,000 –> 00:00:43,760
فلش زرد است یا در سمت
23
00:00:43,760 –> 00:00:45,120
راست آرایه
24
00:00:45,120 –> 00:00:47,680
بدون کوتاه است، هدف شما این است که با این فلش زرد شروع
25
00:00:47,680 –> 00:00:48,399
کنید
26
00:00:48,399 –> 00:00:51,680
و عنصر بروید. توسط عنصر سپس آن
27
00:00:51,680 –> 00:00:52,320
عناصر را
28
00:00:52,320 –> 00:00:54,320
در آرایه کوتاه شده که در
29
00:00:54,320 –> 00:00:55,360
سمت چپ است قرار دهید
30
00:00:55,360 –> 00:00:58,640
تا 38 به آن نگاه کنید و سپس
31
00:00:58,640 –> 00:01:00,559
موقعیت را تغییر نخواهید داد زیرا 21
32
00:01:00,559 –> 00:01:02,640
38 قبلا مرتب شده است
33
00:01:02,640 –> 00:01:07,040
اکنون به عنصر شماره 29
34
00:01:07,040 –> 00:01:10,159
29 بروید که می خواهید در آرایه مرتب شده قرار دهید،
35
00:01:10,159 –> 00:01:12,640
بنابراین آرایه مرتب شده اساساً 21 و 38 است
36
00:01:12,640 –> 00:01:14,080
هر چیزی که
37
00:01:14,080 –> 00:01:16,880
دارای پس زمینه آبی است که یک آرایه مرتب شده است،
38
00:01:16,880 –> 00:01:17,600
39
00:01:17,600 –> 00:01:20,640
بنابراین در اینجا اکنون شما 29 را می گیرید و سعی می کنید
40
00:01:20,640 –> 00:01:22,320
اینجا را قرار دهید، بنابراین در چه موقعیتی است
41
00:01:22,320 –> 00:01:23,040
که آن
42
00:01:23,040 –> 00:01:26,560
را بین این دو قرار دهید و شما این را دریافت می کنید
43
00:01:26,560 –> 00:01:30,560
، حالا به
44
00:01:30,560 –> 00:01:33,920
38 می روید، سپس به 17
45
00:01:33,920 –> 00:01:36,000
می روید وقتی 70 دارید، اکنون سعی
46
00:01:36,000 –> 00:01:37,759
کنید 17 را در جایی قرار دهید،
47
00:01:37,759 –> 00:01:40,400
جایی که باید خوب پیش برود،
48
00:01:40,400 –> 00:01:43,200
در قسمت جلو می رود
49
00:01:43,200 –> 00:01:46,479
خوب است، بنابراین تا زمانی که شما به انجام آن
50
00:01:46,479 –> 00:01:49,920
ادامه دهید. کل آرایه خود را مرتب کنید،
51
00:01:49,920 –> 00:01:53,040
اما یکی از مشکلات این درج
52
00:01:53,040 –> 00:01:54,640
به هر شکلی که ما به آن نگاه کردیم
53
00:01:54,640 –> 00:01:57,600
، درج کوتاه است، مشکل این
54
00:01:57,600 –> 00:01:58,159
است که
55
00:01:58,159 –> 00:02:00,240
فقط به این فکر کنید که وقتی می خواهید
56
00:02:00,240 –> 00:02:01,280
چهار
57
00:02:01,280 –> 00:02:04,000
در این آرایه مرتب شده قرار دهید، اول از همه
58
00:02:04,000 –> 00:02:05,200
باید درست با هم مقایسه کنید.
59
00:02:05,200 –> 00:02:07,119
در اینجا، بنابراین شما شروع به مقایسه
60
00:02:07,119 –> 00:02:09,840
با 38 می کنید، چاه 38 بزرگتر از 4 است،
61
00:02:09,840 –> 00:02:12,959
بنابراین به 29 منتقل می شوید، همچنین بزرگتر است،
62
00:02:12,959 –> 00:02:14,800
بنابراین به 21 می روید که بزرگتر است
63
00:02:14,800 –> 00:02:18,000
17 بزرگتر، بنابراین اکنون 4 را اینجا قرار می دهید،
64
00:02:18,000 –> 00:02:20,959
بنابراین باید مقایسه های زیادی انجام دهید و
65
00:02:20,959 –> 00:02:22,720
زمانی که قرار می دهید چهار در اینجا
66
00:02:22,720 –> 00:02:24,640
شما در واقع در حال مبادله هستید
67
00:02:24,640 –> 00:02:26,239
درست است که شما در حال انتقال
68
00:02:26,239 –> 00:02:29,440
17 به اینجا 21 به اینجا هستید،
69
00:02:29,440 –> 00:02:32,640
بنابراین تعویض های زیادی وجود دارد و مقایسه های زیادی وجود دارد،
70
00:02:32,640 –> 00:02:34,720
بنابراین این
71
00:02:34,720 –> 00:02:36,160
نقطه ضعف
72
00:02:36,160 –> 00:02:39,360
درج کوتاه است که اگر
73
00:02:39,360 –> 00:02:42,640
عناصر پایینی شما یا عناصر کوچکتر
74
00:02:42,640 –> 00:02:45,360
به سمت انتها یا در سمت
75
00:02:45,360 –> 00:02:46,480
راست باشند. از یک آرایه
76
00:02:46,480 –> 00:02:48,640
پس از آن شما مقایسه و جابجایی زیادی انجام خواهید داد
77
00:02:48,640 –> 00:02:49,599
78
00:02:49,599 –> 00:02:52,400
و سلول کوتاه سعی می کند این مشکل را حل
79
00:02:52,400 –> 00:02:53,599
کند
80
00:02:53,599 –> 00:02:56,560
چقدر خوب در سلول کوتاه کاری که می خواهید
81
00:02:56,560 –> 00:02:58,080
انجام دهید
82
00:02:58,080 –> 00:02:59,840
هر آرایه ای که دارید درست مثل این
83
00:02:59,840 –> 00:03:02,080
آرایه من بود شما سعی خواهید کرد
84
00:03:02,080 –> 00:03:04,480
عنصر سنگین تر را جابجا کنید. در سمت راست
85
00:03:04,480 –> 00:03:05,120
86
00:03:05,120 –> 00:03:08,319
به نحوی نه لزوماً آنها
87
00:03:08,319 –> 00:03:09,280
مرتب می شوند،
88
00:03:09,280 –> 00:03:12,400
اما به نوعی شما کاری انجام می دهید که عناصر
89
00:03:12,400 –> 00:03:13,440
90
00:03:13,440 –> 00:03:15,440
سنگین تر که 38 29 است در
91
00:03:15,440 –> 00:03:16,640
سمت راست قرار بگیرند
92
00:03:16,640 –> 00:03:18,560
و اگر عناصر سنگین تر در
93
00:03:18,560 –> 00:03:19,920
سمت راست به طور طبیعی در سمت راست قرار گیرند.
94
00:03:19,920 –> 00:03:22,800
شما درج
95
00:03:22,800 –> 00:03:23,599
96
00:03:23,599 –> 00:03:26,159
تعداد کوتاهی از مبادله ها را در مقایسه انجام می
97
00:03:26,159 –> 00:03:27,120
دهید، بنابراین بیایید به
98
00:03:27,120 –> 00:03:29,920
اینجا برویم و با شکاف
99
00:03:29,920 –> 00:03:30,480
سه شروع کنیم،
100
00:03:30,480 –> 00:03:34,080
بنابراین سلول کوتاه از این مفهوم شکاف استفاده می کند
101
00:03:34,080 –> 00:03:36,319
که در آن شما با مقداری شکاف شروع می کنید، بنابراین
102
00:03:36,319 –> 00:03:39,920
فرض کنید من با شکاف 3 در اینجا شروع می کنم،
103
00:03:39,920 –> 00:03:43,840
بنابراین در شکاف 3
104
00:03:43,840 –> 00:03:46,319
شما تمام عناصر خود را دریافت می کنید و به
105
00:03:46,319 –> 00:03:48,159
نوعی یک آرایه فرعی تشکیل می دهید،
106
00:03:48,159 –> 00:03:51,120
بنابراین در اینجا آرایه فرعی من دارای سه عنصر
107
00:03:51,120 –> 00:03:52,879
21 17 و 11 است
108
00:03:52,879 –> 00:03:54,159
و ببینید که آنها یک شکاف از سه
109
00:03:54,159 –> 00:03:56,480
عنصر دارند، بنابراین بعد از 21 1 2
110
00:03:56,480 –> 00:04:00,319
3 بعد از 17 1 2 3 بعد از یازده و یک
111
00:04:00,319 –> 00:04:02,400
دو آه، هیچ عنصری وجود ندارد، بنابراین ما به
112
00:04:02,400 –> 00:04:03,680
اینجا پایان می
113
00:04:03,680 –> 00:04:08,239
دهیم و اکنون سعی می کنیم این آرایه فرعی را مرتب کنیم،
114
00:04:08,239 –> 00:04:09,840
بنابراین ببینید که مرتب سازی
115
00:04:09,840 –> 00:04:11,920
اکنون فقط روی آرایه فرعی انجام می شود نه در
116
00:04:11,920 –> 00:04:12,799
کل آرایه،
117
00:04:12,799 –> 00:04:14,720
بنابراین فرض کنید شما آرایه ای دارید. سه
118
00:04:14,720 –> 00:04:16,560
عنصر 21 17
119
00:04:16,560 –> 00:04:20,478
11 و سپس آن آرایه را مرتب می
120
00:04:20,478 –> 00:04:24,160
کنید بسیار خوب
121
00:04:24,160 –> 00:04:27,759
حالا به یک آرایه فرعی دیگر با
122
00:04:27,759 –> 00:04:30,479
همان شکاف می روید که سه است، پس اگر
123
00:04:30,479 –> 00:04:31,440
124
00:04:31,440 –> 00:04:35,919
از این به اینجا حرکت کنم چه می شود، حالا
125
00:04:35,919 –> 00:04:39,680
دوباره اینجا هستم، یک آرایه فرعی تشکیل می دهم
126
00:04:39,680 –> 00:04:42,240
که دارای یک شکاف از سه عنصر است و
127
00:04:42,240 –> 00:04:44,320
آن آرایه فرعی اکنون 38
128
00:04:44,320 –> 00:04:47,440
یا 32 است. چگونه آن را به خوبی مرتب می
129
00:04:47,440 –> 00:04:51,360
کنید، 4 32 38 است،
130
00:04:51,360 –> 00:04:52,960
بنابراین به عناصری که در پس زمینه آبی هستند نگاه کنید،
131
00:04:52,960 –> 00:04:55,199
من فقط آنهایی را مرتب
132
00:04:55,199 –> 00:04:56,639
می کنم که بقیه را لمس نمی کنم عناصر
133
00:04:56,639 –> 00:04:58,320
134
00:04:58,320 –> 00:05:01,280
اوکی هستند و سپس از 38 به 38
135
00:05:01,280 –> 00:05:03,600
می روید و اکنون به 29 می روید بنابراین 29 می شود
136
00:05:03,600 –> 00:05:07,039
25 و
137
00:05:07,039 –> 00:05:10,000
سعی کنید مرتب سازی کنید 9 این مقدار وقتی 29
138
00:05:10,000 –> 00:05:10,639
25
139
00:05:10,639 –> 00:05:15,360
9 را مرتب می کنید، 9 25 9 29 دریافت می کنید
140
00:05:15,600 –> 00:05:18,960
و این کار را تا انتها
141
00:05:18,960 –> 00:05:19,600
142
00:05:19,600 –> 00:05:22,639
برای فاصله سه ادامه می دهید، بنابراین وقتی
143
00:05:22,639 –> 00:05:25,759
این کار را برای فاصله سه انجام دادید، آنچه را
144
00:05:25,759 –> 00:05:26,800
که از این
145
00:05:26,800 –> 00:05:29,600
آرایه منبع دریافت کردید، این را دریافت کردید. آرایه اکنون این
146
00:05:29,600 –> 00:05:31,199
آرایه مرتب
147
00:05:31,199 –> 00:05:34,479
نشده است اما یک چیز نیست همه عناصر سنگین تر
148
00:05:34,479 –> 00:05:35,280
149
00:05:35,280 –> 00:05:37,199
یا عناصر بزرگتر اکنون
150
00:05:37,199 –> 00:05:39,039
151
00:05:39,039 –> 00:05:42,240
در سمت راست هستند.
152
00:05:42,240 –> 00:05:43,280
153
00:05:43,280 –> 00:05:46,560
154
00:05:46,560 –> 00:05:49,120
آرایه شما مقایسه کمتری خواهید داشت
155
00:05:49,120 –> 00:05:50,880
و مبادله کمتری خواهید داشت،
156
00:05:50,880 –> 00:05:55,600
بنابراین به فاصله دو
157
00:05:55,600 –> 00:05:58,400
می روید که چگونه شکاف را کاهش
158
00:05:58,400 –> 00:05:59,199
159
00:05:59,199 –> 00:06:02,080
160
00:06:02,080 –> 00:06:03,520
161
00:06:03,520 –> 00:06:07,520
162
00:06:07,520 –> 00:06:10,960
می دهید. هدف نهایی این است که به حالتی
163
00:06:10,960 –> 00:06:11,680
برسید که در آن
164
00:06:11,680 –> 00:06:14,720
شکاف یک به دست آورید، بنابراین فرض کنید من یک
165
00:06:14,720 –> 00:06:15,600
شکاف دو دارم،
166
00:06:15,600 –> 00:06:18,000
بنابراین شکاف دو یعنی هر عنصر جایگزین
167
00:06:18,000 –> 00:06:19,759
168
00:06:19,759 –> 00:06:22,319
در حال حاضر شما سعی می کنید این آرایه فرعی را مرتب کنید، بنابراین
169
00:06:22,319 –> 00:06:23,440
آرایه فرعی من چیست
170
00:06:23,440 –> 00:06:26,720
11 9 32
171
00:06:26,720 –> 00:06:30,560
21 و 29 مرتب می کنند که باشه
172
00:06:30,560 –> 00:06:34,560
شما 9 11 21 29 32 می گیرید
173
00:06:34,560 –> 00:06:36,319
پس آرایه فرعی دوم من w چیست
174
00:06:36,319 –> 00:06:37,840
تمام عناصر باقیمانده درست است 4
175
00:06:37,840 –> 00:06:41,039
17 25، اما اگر به آنهایی که
176
00:06:41,039 –> 00:06:41,840
فقط مرتب شده اند نگاه
177
00:06:41,840 –> 00:06:43,600
کنم، من در اینجا خوش شانس هستم، بنابراین نیازی به انجام کاری ندارم،
178
00:06:43,600 –> 00:06:45,919
179
00:06:45,919 –> 00:06:49,520
سپس فاصله خود را به یک کاهش می دهم به یاد داشته باشید به
180
00:06:49,520 –> 00:06:50,639
طور
181
00:06:50,639 –> 00:06:52,720
خلاصه باید آخرین مرحله خود را انجام دهید شکاف یک خواهد بود
182
00:06:52,720 –> 00:06:53,759
183
00:06:53,759 –> 00:06:56,720
و وقتی شکاف یک باشد در واقع
184
00:06:56,720 –> 00:06:57,280
تبدیل به کوتاه می شود
185
00:06:57,280 –> 00:07:01,039
بله شکاف یک
186
00:07:01,039 –> 00:07:03,919
به این معنی است که یک عکس درج است و اکنون
187
00:07:03,919 –> 00:07:06,639
وقتی درج کوتاه را در اینجا انجام
188
00:07:06,639 –> 00:07:08,639
می دهید متوجه خواهید شد که اکثر عناصر
189
00:07:08,639 –> 00:07:11,919
فقط با 9 مرتب شده اند و 4 نیست. مرتب شده است
190
00:07:11,919 –> 00:07:14,639
به طوری که وقتی از درج کوتاه استفاده
191
00:07:14,639 –> 00:07:16,560
می کنید فقط یک جابجایی وجود خواهد داشت
192
00:07:16,560 –> 00:07:19,919
و تعداد مبادله ها اکنون به
193
00:07:19,919 –> 00:07:22,880
طور کلی کاهش می یابد، بنابراین الگوریتم کلی
194
00:07:22,880 –> 00:07:23,919
این است
195
00:07:23,919 –> 00:07:26,319
که روش رایج این است که شما
196
00:07:26,319 –> 00:07:27,520
با n به دو
197
00:07:27,520 –> 00:07:31,280
به عنوان شکاف شروع کنید، سپس آرایه فرعی را مرتب کنید و
198
00:07:31,280 –> 00:07:33,919
سپس در تکرار بعدی شما
199
00:07:33,919 –> 00:07:35,520
فاصله خود را دو کاهش می دهید
200
00:07:35,520 –> 00:07:37,919
بنابراین n به دو کاهش می دهید و سپس به n چهار تبدیل می شود و
201
00:07:37,919 –> 00:07:40,240
سپس به هشت پایان می رسد
202
00:07:40,240 –> 00:07:42,840
آخرین تکرار باید شکاف برابر با
203
00:07:42,840 –> 00:07:44,000
یک باشد
204
00:07:44,000 –> 00:07:46,400
که در این مرحله تبدیل کوتاه می شود
205
00:07:46,400 –> 00:07:47,120
206
00:07:47,120 –> 00:07:49,680
بنابراین در واقع ما درج کوتاه را انجام می دهیم
207
00:07:49,680 –> 00:07:52,240
اما با مقداری بهینه سازی به طوری که
208
00:07:52,240 –> 00:07:55,199
بی حس تعویض و مقایسه را می توان
209
00:07:55,199 –> 00:07:56,560
کاهش داد
210
00:07:56,560 –> 00:07:59,039
پیچیدگی بزرگتر در بدترین حالت
211
00:07:59,039 –> 00:07:59,599
مرتبه
212
00:07:59,599 –> 00:08:02,720
n مربع است. اوه، بدترین مورد شناخته شده،
213
00:08:02,720 –> 00:08:05,599
یک دنباله شکاف
214
00:08:05,599 –> 00:08:06,160
ترتیبی از
215
00:08:06,160 –> 00:08:10,639
n مربع log و و uh عملکرد را به شما می دهد
216
00:08:10,639 –> 00:08:13,199
و در اینجا چند آمار از
217
00:08:13,199 –> 00:08:14,800
عملکرد بهترین حالت شما وجود دارد.
218
00:08:14,800 –> 00:08:17,919
این را از ویکیپدیا گرفتهام، پس حالا
219
00:08:17,919 –> 00:08:18,400
220
00:08:18,400 –> 00:08:20,879
بیایید وارد کدنویسی پایتون شویم،
221
00:08:20,879 –> 00:08:22,879
حالا در اینجا سلول کوتاه را در پایتون مینویسیم
222
00:08:22,879 –> 00:08:25,599
، همان عناصری را که
223
00:08:25,599 –> 00:08:26,319
224
00:08:26,319 –> 00:08:29,120
در ارائه به شما نشان دادم برداشتهام و
225
00:08:29,120 –> 00:08:29,440
اکنون
226
00:08:29,440 –> 00:08:32,479
تابع کوتاه سلولی را مینویسم، بنابراین ابتدا چه خواهیم کرد
227
00:08:32,479 –> 00:08:32,799
انجام دهید این
228
00:08:32,799 –> 00:08:36,320
است که من به شما نشان خواهم داد که وقتی شکاف سه را می گیرید چه اتفاق