وقت مرتب کردنه !

مروری بر الگوریتم های مرتب سازی در دنیای کامپیوتر.

نگارنده : سنا سرقلی دانشجوی علوم کامپیوتر دانشگاه چمران.

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

مرتب‌سازی حبابی

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

با این حال، این الگوریتم با پیچیدگی زمانی n^2، به عنوان یکی از بدترین الگوریتم‌های مرتب‌سازی در نظر گرفته می‌شود. برای اینکه بهتر متوجه موضوع بشویم بیاید نگاهی به موضوع پیچیدگی زمان بیاندازیم.

پیچیدگی زمانی
قطعاً به عنوان یک دانشجوی کامپیوتر می‌دانید که یکی از عوامل اساسی که بر عملکرد و کارایی برنامه شما تأثیر می‌گذارد، سخت‌افزار، سیستم‌عامل و CPU ای است که از آن استفاده می‌کنید.
اما وقتی عملکرد یک الگوریتم را تجزیه و تحلیل می‌کنید، این موارد را در نظر نمی‌گیرید. در عوض، پیچیدگی زمانی و حافظه‌ای الگوریتم شما مهم است.
پیچیدگی زمانی یک الگوریتم مشخص می‌کند که چقدر طول می‌کشد تا یک الگوریتم به عنوان تابعی از اندازه ورودی آن اجرا شود. در واقع پیچیدگی زمانی نشان می‌دهد که بزرگ‌تر شدن ورودی یک الگوریتم، روی زمان اجرای آن چگونه تأثیر می‌گذارد.
برای مثال در الگوریتم مرتب‌سازی حبابی، پیچیدگی زمانی n^2 است که n در اینجا نشان دهنده تعداد اعداد لیست است. احتمالا حدس می‌زنید که هر چه n بیشتر باشد، یعنی لیستی که آن را مرتب می‌کنیم اعداد بیشتری داشته باشد، اجرای الگوریتم زمان بیشتری نیاز دارد. اما ما می‌توانیم از روی پیچیدگی زمانی n^2 دقیقا بفهمیم که اگر n برابر 10 باشد، اجرای الگوریتم 100 واحد زمانی زمان نیاز دارد و اگر n برابر 1000 باشد، اجرای الگوریتم یک میلیون واحد زمانی طول می‌کشد.

مرتب‌سازی ادغام
"تفرقه بینداز و حکومت کن! ". مرتب‌سازی ادغام یکی از کارآمدترین الگوریتم‌‌های مرتب‌سازی است که تقریباً بر همین اساس کار می‌کند. این برنامه یک لیست از اعداد را به چندین لیست کوچک‌تر می‌شکند و هرکدام را جداگانه مرتب می‌کند و در نهایت لیست‌های مرتب شده را با هم ادغام می‌کند. در علم کامپیوتر به این شکستن یک مسئله به چندین زیر‌مسئله کوچک‌تر، اصل Divide and Conquer می‌گویند.
مفهوم Divide and Conquer شامل سه مرحله است:
1. مسئله را به چندین زیرمسئله تقسیم کنید. ایده این است که مشکل را آنقدر به مسائل کوچک‌تر تقسیم کنید که زیرمسائل به وجود آمده، دیگر قابل تقسیم کردن نباشند.
2. مسائل شکسته‌شده را جدا جدا حل کنید.
3. پاسخ زیرمسئله ها را با هم ترکیب کنید تا راه حل مسئله واقعی را بیابید.
مرتب‌سازی ادغام یک الگوریتم بازگشتی است که به طور مداوم لیست اعداد را به دو نیمه تقسیم می‌کند و هر نیمه را مجدداً به دو نیمه دیگر تقسیم می‌کند تا زمانی که نتوان آن را بیشتر تقسیم کرد، یعنی در هر قسمت فقط یک عنصر باقی مانده است. واضح است که لیستی با یک عنصر نیازی به مرتب‌سازی ندارد و همیشه مرتب شده است، پس ما پاسخ زیرمسئله‌ها را پیدا کردیم! حالا کافیست که این لیست‌های کوچک مرتب را به همان شکل شکسته شدن با هم ادغام کنیم تا لیست اصلی مرتب شده ساخته شود.
به زبان ساده می‌توان گفت که فرایند ادغام مرتب‌سازی به این صورت است که آرایه را به دو نیمه تقسیم می‌کنیم، هر نیمه را مرتب می‌کنیم و سپس نیمه‌‌های مرتب شده را دوباره با هم ادغام می‌کنیم. این روند تا زمانی که کل آرایه مرتب شود تکرار می‌شود.

پیچیدگی زمانی الگوریتم مرتب‌سازی ادغام
با پیچیدگی زمان قبل‌تر آشنا شدیم، پیچیدگی زمانی در الگوریتم مرتب‌سازی ادغامی، n*log⁡(n) است. این به این معناست که اگر تعداد اعداد لیست n باشد، به n*log⁡(n) واحد زمانی برای اجرای الگوریتم نیاز‌ داریم. مثلا اگر n برابر 10 باشد حدودا به 30 واحد زمانی نیاز داریم. از مقایسه این عدد با الگوریتم مرتب‌سازی حبابی می‌بینیم که این الگوریتم خیلی سریع‌تر اجرا می‌شود. همچنین اگر n بزرگ‌تر شود این تفاوت خیلی مشهودتر است. مثلا اگر n برابر 1000 باشد، به ده‌هزار واحد زمانی برای اجرای الگوریتم نیاز داریم که خیلی کمتر از یک میلیون واحد در مرتب‌سازی حبابی است.

مرتب‌سازی رادیکس
مرتب‌سازی رادیکس یک الگوریتم مرتب‌سازی اعداد صحیح است که اعداد را با گروه‌بندی بر اساس ارقام و جایگاه آنها مرتب می‌کند. مثلاً اگر لیست ما شامل اعداد سه‌رقمی است، ابتدا اعداد را بر اساس رقم یکان، سپس بر اساس رقم دهگان و در نهایت بر اساس صدگان مرتب می‌کند و به این صورت در نهایت همه اعداد مرتب شده‌اند.

از این روش مرتب‌سازی برای مرتب کردن کلمات و حروف هم می‌توان استفاده کرد، چیزی شبیه به یک دیکشنری.

پیچیدگی زمانی الگوریتم مرتب‌سازی رادیکس
پیچیدگی زمانی این الگوریتم کمی با دو الگوریتم قبلی متفاوت است، چون زمان اجرای الگوریتم رادیکس، علاوه بر تعداد اعداد موجود در لیست، به تعداد ارقام اعداد هم بستگی دارد. اگر تعداد اعداد لیست را n و تعداد ارقام اعداد را d در نظر بگیریم، اجرای الگوریتم رادیکس به n* d واحد زمانی نیاز دارد یعنی پیچیدگی زمانی این الگوریتم nd است.

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