۵ الگورتمی که هر دولوپری باید بلد باشد

سلام و درود، خیلی پیچیده و تئوری نیست، نگران نباشید، الگوریتم هایی که در ادامه معرفی شون می کنیم رو اگر مشغول کد زنی در یه شرکت کوچیک یا کلا یه پروژه شخصی هم باشید احتمال کار کردن و مواجه شدن باهاشون خیلی زیاده، پس چیز پیچیده ای پیش رو نداریم و صرفا ۵ مورد از الگوریتم های مهم و ضروری برای برنامه نویسی که هر دولوپری باید بلد باشد را مطرح می کنیم 🙂

۱- الگوریتم های Sort

اگوریتم های که برای چینش و مرتب کردن استفاده می کنید، مگه میشه تو پروژتون sortکردن نداشته باشید!

در ادامه به معرفی الگوریتم های Sort مطرح می پردازیم:

• مرتب سازی حبابی –Bubble Sort: ساده ترین نوع مرتب سازی که وجود داره، به صورت تکراری المانی که در موقعیت درستی قرار نداره را جابجا می کند.

• مرتب سازی ادغام – Merge Sort : از استراتژی تقسیم و غلبه (divide and conquer) استفاده می کند.

• مرتب سازی سریع – Quicksort : الگوریتم رایج مرتب سازی می باشد، که n log n مقایسه را به طور متوسط هنگام مرتب‌سازی آرایه‌ای از n عنصر انجام می‌دهد.کوییک سورت، الگوریتم مرتب‌سازی کارآمدتر و سریع‌تر می باشد.

• مرتب سازی هیپ – Heap Sort : مرتب سازی پشته ای با تجسم عناصر آرایه به عنوان نوع خاصی از درخت دودویی کامل که به نام Heapشناخته می شود، کار می کند.

۲ – الگوریتم های جستجو – Searching Algorithm

الگوریتم پیدا کردن یک المان در یک مجموعه داده، الگوریتم های جستجوی مهم عباتر هستند از :

• جستجوی دودویی – Binary Search : جستجوی دودویی از استراتژی تقسیم و غلبه (divide and conquer) استفاده می کند که در آن یک لیست مرتب شده به دو نیمه تقسیم می شود و آیتم با الملن میانی لیست ها مقایسه می شود. اگر مطابقت پیدا شد، موقعیت المان میانی بازگردانده می شود.

• جستجوی Breadth-First یا (BFS): یک الگوریتم پیمایش گراف می باشد که از گره ریشه شروع می شود و تمام گره های مجاور را بررسی می کند.

• جستجوی Depth-First یا (DFS): از نود اول گراف شروع کرده و به عمق بیشتر و بیشتر می رود تا زمانی که گره هدف را بدون فرزند پیدا کند.

۳ – برنامه نویسی پویا (Dynamic Programming):

برنامه نویسی پویا (DP) یک تکنیک الگوریتمی برای حل یک مسئله بهینه سازی با تجزیه آن به مسائل فرعی ساده تر و بهره گیری از این واقعیت است که راه حل بهینه برای مسئله کلی وابسته به راه حل بهینه برای مسائل فرعی آن است.

۴- الگوریتم بازگشتی (Recursion Algorithm):

بازگشت یک تکنیک حل مسئله است که در آن راه حل به راه حل هایی برای نمونه های کوچکتر از همان مسئله وابسته است. محاسبات فاکتوریل یک مثال کلاسیک از برنامه نویسی بازگشتی است.

به مثال زیر توجه کنید، دو رویکرد برای مجموع n عدد طبیعی داریم :

approach(1) – Simply adding one by one

f(n) = 1 + 2 + 3 +……..+ n

********************************************************

approach(2) – Recursive adding 

f(n) = 1                  n=1

f(n) = n + f(n-1)    n>1

رویکرد دوم، یک رویکرد بازگشتی است، داخل تابع f خود تابع f فراخوانی شده است.

هر برنامه بازگشتی از ترتیب رایج و یکسانی از مراحل پیروی می کند:

• الگوریتم را تنظیم کنید. برای شروع، برنامه های بازگشتی اغلب به یک مقدار seed نیاز دارند. این کار با استفاده از یک پارامتر ارسال شده به تابع یا با ارائه یک تابع gateway غیر بازگشتی که مقادیر seed را برای محاسبه بازگشتی تنظیم می کند، انجام می شود.
• بررسی کنید که آیا مقدار(های) فعلی در حال پردازش با حالت پایه مطابقت دارد یا خیر. اگر چنین است، مقدار را پردازش کرده و آن را برگردانید.
• راه حل را در قالب یک زیرمسئله یا مسائل فرعی کوچکتر یا ساده تر بیان کنید.
• الگوریتم را روی مسئله فرعی اعمال کنید.
• برای فرموله کردن پاسخ، نتایج را با هم ترکیب کنید.
• نتایج را برگردانید.

۵ – الگوریتم تقسیم و غلبه (Divide and Conquer):

یک الگوریتم تقسیم و غلبه یک مسئله را به صورت بازگشتی به دو یا چند مشکل فرعی از یک نوع یا مرتبط تقسیم می کند، تا زمانی که به اندازه کافی ساده باشند که مستقیماً حل شوند.

الگوریتم Divide and Conquer شامل یک مشاجره (اختلاف) با استفاده از سه مرحله ذکر شده در زیر است

۱- تقسیم مسئله اصلی به زیر-مسئله ها

۲- تقسیم، حل هر زیر مسئله در یک زمان به صورت بازگشتی.

۳- ترکیب: قرار دادن راه حل های زیر مسئله ها در کنار هم برای راه حل مسئله اصلی.