آموزش طراحی الگوریتم از پایه + بررسی الگوریتم مرتب سازی انتخابی

الگوریتم چیست؟ چرا مطالعۀ الگوریتم ها ارزشمند است؟ نقش الگوریتم ها در ارتباط با سایر فناوری های مورد استفاده در دنیای کامپیوترها چیست؟ در طول مقالۀ آموزش طراحی الگوریتم از پایه سعی داریم تا حد امکان پاسخ شایسته ای به این سوالات بدهیم. اگر بخواهیم تعریفی غیر رسمی از الگوریتم (algorithm) ارائه دهیم، می توانیم بگوییم که یک روش محاسباتی است که مقدار یا مجموعه ای از مقادیر را به عنوان ورودی دریافت می کند و مقدار یا مجموعه مقادیری را به عنوان خروجی ارائه می دهد. اگر با مبحث تابع در ریاضی آشنایی داشته باشید، نسبتاً شبیه آن عمل می کند. اگر این گونه به قضیه نگاه کنیم، الگوریتم دنباله ای از مراحل محاسباتی است که ورودی را به خروجی تبدیل می کند. همچنین می توانیم به الگوریتم به عنوان ابزاری برای حل یک مسئله محاسباتی مشخص نگاه کنیم. به عنوان مثال ممکن است بخواهیم مجموعه ای از اعداد که به صورت غیر مرتب کنار یکدیگر قرار گرفته اند را به ترتیب از کوچک به بزرگ یا بالعکس مرتب سازیم. در این حالت ورودی الگوریتم ما آن مجموعۀ اعداد نامرتب می باشد و خروجی آن مجموعۀ اعداد مرتب خواهد بود. و در این میان الگوریتم ما به نحوی این ورودی را به آن خروجی تبدیل می کند.

اگر بخواهیم مثال بالا را ملموس تر کنیم، مجموعۀ \(\{ 31,41,59,26,41,58 \}\) را در نظر بگیرید. اگر این مجموعه را به الگوریتم مرتب سازی بدهیم، مجموعۀ مرتب شدۀ \(\{ 26,31,41,41,58,59 \}\) را به عنوان خروجی دریافت خواهیم کرد. بد نیست بدانید مرتب سازی یکی از مسائل پایه ای و اساسی در علوم کامپیوتر می باشد. از این رو تعداد الگوریتم هایی که تاکنون برای این منظور نوشته شده اند، بسیارند. در حال حاضر ما الگوریتم های مرتب سازی فراوانی را در اختیار داریم، اما مسلماً این پایان راه نیست و جا برای تلاش های بیشتر هنوز باز است. کوچکترین ارتقایی در الگوریتم های بنیادین علوم کامپیوتر می تواند منجر به تحولاتی عظیم در آن شود و از این رو موضوع الگوریتم برای همیشه مبحثی داغ و با ارزش باقی خواهد ماند. زبان های برنامه نویسی می آیند و می روند، روزگاری زبان فرترن و پاسکال مطرح بودند، مدتی زبان بیسیک و دلفی مطرح شدند، نوبت به سی شارپ ها و پایتون ها و ... می رسد و خلاصه در هر مقطعی، زبانی طلوع می کند و دیگری افول می کند، اما آنچه در این میان همیشگی و پایدار است الگوریتم است.

اگر مشتاق هستید دانشتان در حوزۀ الگوریتم را ارتقاء بخشید، مجموعه آموزش ساختمان داده و طراحی الگوریتم را به شما پیشنهاد می کنم.

مجموعه آموزش ساختمان داده و طراحی الگوریتم -- کلیک کنید

چه نوع مسائلی توسط الگوریتم ها حل می شوند؟

تا این جای آموزش طراحی الگوریتم از پایه، دانستید الگوریتم چیست و دست کم آشنایی اجمالی با یکی از انواع مهم الگوریتم ها در دنیای کامپیوترها که همان الگوریتم های مرتب سازی می باشند، پیدا کردید. اما مسلّماً مرتب سازی، تنها الگوریتم توسعه داده شده توسط دانشمندان علوم کامپیوتر نیست. کاربردهای مختلف الگوریتم ها را می توان در همه جا یافت:

پروژۀ ژنوم انسان (The Human Genome Project) یکی از بزرگترین پروژه های تحقیقاتی تاریخ بشریت می باشد. هدف این پروژه اینست که تمامی ژن های موجود در DNA انسان را شناسایی کنند و نقشۀ تمامی آنها را با تمامی جزییات مشخص سازند. چندین میلیارد ترکیب شیمیایی وجود دارند که DNA انسان را تشکیل می دهند. ذخیره سازی اطلاعات این ترکیبات شیمیایی در پایگاه های داده، و ایجاد و توسعۀ ابزارهایی برای تجزیه و تحلیل این حجم داده، بخشی از کارهایی از پروژه است که بدون کمک علوم کامپیوتر و الگوریتم ها شدنی نیست. هر کدام از این بخش ها و جزییات فراون علمی دیگر موجود در آنها، نیازمند ایجاد الگوریتم های پیچیده و دقیقی می باشد.
اینترنت افراد را قادر ساخته است که به سادگی از هر نقطۀ جهان با یکدیگر ارتباط برقرار کنند. تمامی این فرآیندهای ارتباطی از قسمت های زیر ساختی اش گرفته تا قسمت های سطح بالاترش توسط الگوریتم ها طراحی شده اند. وقتی بسته های داده که در واقع همان اطلاعاتی هستند که شما در اینترنت ارسال یا دریافت می کنید، در بستر شبکه جابجا می شوند، به کمک الگوریتم های هوشمندی بهترین مسیرها را پیدا می کنند تا بتوانند سریعتر به مقصد برسند. همچنین موتورهای جستجو همچون گوگل با حجم کلانی از داده ها سر و کار دارند، به کمک الگوریتم هایی هوشمند، این همه داده را پردازش می کنند تا شما بتوانید نتایج جستجو را در کسری از ثانیه دریافت کنید.
امروزه بخش عمده ای از خرید و فروش های بازارهای سنتی به دنیای دیجیتال منتقل شده است و شما بعد از خرید آنلاین می توانید با خیالی راحت اطلاعات حساب بانکی تان را وارد کنید تا مبلغی از اعتبار شما به اعتبار حساب فروشنده منتقل گردد. هنگامی که اطلاعات امنیتی همچون کلمۀ عبور را وارد می کنید، به کمک الگوریتم هایی که مبتنی بر نظریۀ اعداد هستند، داده های ارسالی رمزگذاری می گردند.

اگر در ارتباط با الگوریتم ها و طراحی الگوریتم ها شور یادگیری بیشتری دارید، آموزش طراحی الگوریتم که در فرادرس انتشار یافته است را به شما توصیه می کنیم.

آموزش طراحی الگوریتم در فرادرس -- کلیک کنید

الگوریتم مرتب سازی انتخابی (selection sort)

همانطور که پیشتر در همین آموزش طراحی الگوریتم از پایه مطرح ساختیم، یکی از مسائلی که در مبحث الگوریتم ها به وفور به آن پرداخته شده است مسئله مرتب سازی می باشد. الگوریتم های مختلف و زیادی برای انجام عملیات مرتب سازی داده ها ایجاد شده اند که در اینجا می خواهیم به یکی از آنها نگاه دقیق تری بیندازیم. کامپیوترها همیشه مشغول مرتب سازی هستند. وقتی وارد ایمیل تان می شوید، ایمیل های شما در صندوق پیام هایتان بر اساس تاریخ دریافتشان به صورت نزولی مرتب شده اند تا در نتیجۀ آن ایمیل های جدیدتر را در بالای لیست ببینید. هنگامی که وارد یک سایت فروشگاه اینترنتی می شوید، امکان این را دارید که کالاها را بر اساس قیمتشان یا بر اساس سایر پارامترها مرتب سازی کنید. مثال های بسیار دیگری نیز می توان از مرتب سازی زد که در اینجا به همین چند مثال اکتفا می کنیم. شاید با خودتان فکر کنید که مرتب سازی کار سختی نیست و نیازی به این همه الگوریتم ندارد. بد نیست بدانید که دانشمندان علوم کامپیوتر دهه هاست بر روی الگوریتم های مرتب سازی کار کرده و می کنند و برای هر کدام از این الگوریتم ها اسامی بامزه ای همچون مرتب سازی حبابی یا مرتب سازی اسپاگتی، هم برگزیده اند. برای این که بیشتر با این مبحث آشنا شوید فرض کنید مجموعۀ نامرتبی از قیمت بلیط های هواپیما به شکل زیر دارید.

این مجموعۀ اعداد را در کنار یکدیگر جمع می کنیم تا راحتتر بتوانیم با آنها کار کنیم. در دنیای کامپیوتر به این مجموعه ها آرایه گفته می شود.

بیایید ببینیم چگونه می توانیم این اعداد را مرتب کنیم. برای شروع با یک الگوریتم ساده کار را آغاز می کنیم. ابتدا کل این آرایه را از بالا تا پایین بررسی می کنیم تا کوچکترین عدد را بیابیم. برای این منظور از همان عدد بالایی یعنی \(307\) کار را شروع می کنیم، فعلاً فرض می گیریم که همین عدد، کوچکترین عدد موجود در این آرایه می باشد، مگر اینکه خلافش به ما ثابت شود. اگر این آرایه تنها همین یک عضو را می داشت، طبیعتاً کار تمام بود و قطعاً کوچکترین عدد همین \(307\) می بود. اما از آنجا که واقعیت چیز دیگریست سراغ عدد بعدی یعنی \(239\) می رویم. با مقایسۀ این دو عدد متوجه می شویم که \(239\) کوچکتر است. پس کوچکترین عدد ما در حال حاضر \(239\) است. سراغ عضو بعدی یعنی \(214\) می رویم. کوچکترین عدد تغییر کرد. این کار را تا آخرین عضو آرایه ادامه می دهیم تا مشخص شود که آیا عددی کوچکتر از \(214\) هم داریم یا نه.

حالا که کوچکترین عدد در این آرایه را یافتیم، می توانیم آن را در ابتدای لیست قرار دهیم و به سراغ یافتن کوچکترین عدد در سایر اعضای باقی ماندۀ این آرایه بگردیم.

در اینجا بد نیست اشاره کنم که یکی از مسائل مهم در دنیای الگوریتم ها موضوع ساختمان داده می باشد. اگر در این ارتباط مشتاق یادگیری بیشتری هستید، آموزش ساختمان داده ها را از دست ندهید.

آموزش ساختمان داده ها در فرادرس -- کلیک کنید

عملیاتی را که در مرحلۀ اول انجام داده بودیم تا به \(214\) به عنوان کوچکترین عدد برسیم، دوباره تکرار می کنیم. با این تفاوت که این عملیات را از دومین عضو آغاز می کنیم. بعد از یافتن عدد کوچک بعدی، به سراغ اعداد بعدی می رویم. این بار از عضو سوم آرایه آغاز می کنیم. این کار را تا جایی ادامه می دهیم که کل اعضای آرایۀ ما از کوچک به بزرگ مرتب شوند. در نهایت ما با لیست مرتب شدۀ زیر مواجه خواهیم شد.

این الگوریتم تنها یکی از الگوریتم های موجود برای مرتب سازی می باشد که البته ساده ترین آنها نیز هست. به این الگوریتم، الگوریتم مرتب سازی انتخابی (selection sort) گفته می شود.

نگاهی به شبه کد (pseudo code) الگوریتم مرتب سازی انتخابی

در بخش قبلی آموزش طراحی الگوریتم از پایه، یک الگوریتم مرتب سازی ساده با نام مرتب سازی انتخابی را مورد بررسی قرار دادیم. در اینجا شبه کد (pseudo code) این الگوریتم را می بینید. اگر با مفهوم شبه کد بیگانه هستید، باید بگویم چیز سختی نیست و به راحتی می توانید با آن ارتباط برقرار کنید. شبه کد همان کد است، با این تفاوت که به هیچ زبان برنامه نویسی خاصی نوشته نشده است. در واقع برای نوشتن شبه کد از زبان انگلیسی ساده استفاده می شود. البته طبیعتاً برای نوشتن شبه کد باید با اصول کلی برنامه نویسی همچون حلقه ها، شرط ها، ساختارهای توالی در کد و ... آشنایی داشت. اما نیاز نیست که بر گرامر زبان خاصی مسلط باشید. مزیت شبه کد هم در همینست که متعلق به هیچ زبان برنامه نویسی خاصی نیست و هر برنامه نویسی با استفاده از تخصص خودش و تسلطش بر زبان برنامه نویسی محبوبش، می تواند آن را به کدهای آن زبان برنامه نویسی خاص ترجمه کند. در واقع شبه کدها را با کدهای یک زبان برنامه نویسی خاص، بازنویسی کند.

اگر به این شبه کد نگاه کنید با کلمۀ FUNCTION (تابع) آغاز شده است. اساساً تفاوتی نمی کند از کدام زبان برنامه نویسی استفاده کنید، در همۀ آنها مفهوم تابع وجود دارد که مقداری را دریافت کرده و مقداری را باز می گرداند. هر چند الگوریتم دقیقاً به معنای تابع نیست، اما در بسیاری از موارد می توان این دو را معادل یکدیگر دانست، چرا که برنامه نویس ها معمولاً همۀ کارها را به صورت ماژولار انجام می دهند و برای هر الگوریتمی تابع خاصی می نویسند تا در آینده بتوانند از آن کدها، استفادۀ مجدد داشته باشند. در بدنۀ این تابع، دو حلقۀ تو در تو می بنید. حلقۀ اول از اولین عضو آرایه که عضو \(0\) می باشد، کار را آغاز می کند و حلقۀ دوم از ایندکس جاری در حلقۀ اول کارش را آغاز می کند. وظیفۀ حلقۀ داخلی مقایسۀ عدد جاری با سایر اعداد باقی مانده در آرایه است تا تعیین شود که آیا عدد کوچکتری هم وجود دارد یا نه. و وظیفۀ حلقۀ اصلی، اینست که هم کار تابع را آغاز کند و هم اینکه اعضایی را که به عنوان کوچکترین در هر مرحله شناسایی شده اند از لیست آرایۀ ورودی خارج کرده و به ابتدای لیست ببرد. در نهایت بعد از کلمۀ RETURN نام array را می بنید. این بخش از شبه کد به مقدار بازگشتی تابع، یا در واقع به مقدار بازگشتی الگوریتم مرتب سازی اشاره دارد. اگر دقت کنید در ابتدای این تابع نیز در داخل یک جفت پرانتز کلمۀ array را مشاهده خواهید کرد، آن آرایۀ بالایی به منزلۀ ورودی تابع و این آرایۀ پایینی به منزلۀ خروجی تابع می باشد. یک نکتۀ دیگر در این شبه کدها این بود که حلقه ها با عدد صفر آغاز شده اند. برای کسانی که تازه وارد دنیای الگوریتم و برنامه نویسی شده باشند، ممکن است این موضوع کمی نامأنوس به نظر آید، اما سعی کنید به آن خو بگیرید. در آینده ای نه چندان دور، از اینکه می بینید حلقه ها به جای یک با صفر آغاز شده اند، بسیار خوشحال خواهید شد، این یک مورد را قول می دهم.

در پایان این مقاله مایلم منابع آموزشی زیر را با شما به اشتراک بگذاریم: