Скачать или смотреть جلسه بیست و نهم از کتاب مرجع علم داده با استفاده از پایتون python data science handbook

جلسه بیست و نهم از کتاب مرجع علم داده با استفاده از پایتون python data science handbook

مرتب سازی آرایه ها Sorting Arrays
تا اینجا ما اغلب به ابزارهایی توجه کردیم که به داده های آرایه های Numpy دسترسی پیدا کند و اعمالی را برروی آنها انجام دهد. این بخش الگوریتمهایی را پوشش می دهد که مرتبط با مرتب سازی ارزشها در آرایه های Numpy است. این الگوریتمها یک موضوع مورد توجه در مقدمات کلاسهای علوم کامپیوتر می باشد. اگر شما چنین دوره هایی را گذرانده باشید احتمالا در این خصوص خوابهایی دیده اید!(یا وابسته به خلق و خوی شما کابوسهایی دیده باشید!) که درباره الگوریتمهای مرتب سازی insertion sorts، الگوریتم های انتخابی selection sorts، الگوریتم های merge sorts ، الگوریتمهای مرتب سازی سریع quick sorts، الگوریتمهای مرتب سازی حبابی bubble sorts و بسیاری بسیاری دیگر از این الگوریتمها وجود دارد. همه اینها هدف شان انجام وظیفه یکسانی است که عبارت است از مرتب سازی ارزشها در یک لیست یا آرایه.
برای مثالی یک الگوریتم ساده انتخابی مرتب سازی بصورت تکراری کوچکتری ارزش از یک لیست را میگیرد و آن را جابجا می کند تا جایی که لیست مرتب شود. ما میتوانیم این را در چندین خط از پایتون انجام دهیم.
In[1]: import numpy as np
def selection_sort(x):
for i in range(len(x)):
swap = i + np.argmin(x[i:])
(x[i], x[swap]) = (x[swap], x[i])
return x
In[2]: x = np.array([2, 1, 4, 3, 5])
selection_sort(x)
Out[2]: array([1, 2, 3, 4, 5])
اگر دانشجوی سال اول علوم کامپیوتر باشید، استاد به شما می گوید که، الگوریتم انتخابی مرتب سازی یا selection sort از نظر سادگی مفید است، اما بسیار کند است که برای آرایه های بزرگتر استفاده شود. برای یک لیست با Nارزش الگوریتم انتخابی مرتب سازی نیاز به N بار حلقه زدن دارد که در هر بار حلقه زدن مرتبه N مقایسه برای پیدا کردن ارزش swap جهت جایگزینی کوچکترین عنصر آرایه با عنصر i ام انجام میشود. به عبارتی با در نظر گرفتن روش big-O که اغلب برای تعیین مشخصات این الگوریتمها استفاده می شود که میتوانید در صفحه 92 کتاب مبحث Big-Notation یا به عبارتی پیچیدگی الکوریتم را مطالعه کنید الگوریتم مرتب سازی انتخابی پیچیدگی N به توان 2 دارد.یعنی آنکه اگر شما تعداد عناصر لیست را دو برابر کنید زمان اجرا با فاکتور 4 افزایش می یابد.
گرچه الکوریتم انتخابی از الگوریتم مورد علاقه من به نام الگوریتم های bogosort بهتر است.
این متد احمقالنه براساس شانس کامل عمل می کند این متد بصورت تکراری اعداد تصادفی را قاطی می کند shuffle می کند تا خروجی ناگهان مرتب شده باشد. اندازه میانگین پیچیدگی این الگوریتم N در N فاکتوریل است بصورت واضحی برای هیچ محاسبه واقعی استفاده نمی شود.







دکتر اسدی عضو هیات علمی دانشگاه آزاد، دوره آموزشی پایتون ارتباط از طریق موبایل 09305803459 و اکانت تلگرام این خط،
آیدی گروه تلگرام آموزشی برنامه نویسی پایتون: @python765
آیدی کانال متصل به گروه: @python654
فعلا تدریس کتاب python crash course چاپ دوم فایل پی دی اف و کتاب python notes for professionals
محل شرکت کامپیوتری نزدیک مترو شادمان شهر تهران جهت هماهنگیهای حضوری