الگوریتم مرتبسازی:
در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از دادهها را به ترتیبی مشخص میچیند.
پر استفادهترین ترتیبها، ترتیبهای عددی و لغتنامهای هستند. مرتبسازی کارا در بهینه سازی الگوریتمهایی که به لیستهای مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.
از ابتدای علم کامپیوتر مسائل مرتبسازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیدهاست. برای مثال مرتبسازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده میپندارند، الگوریتم کارآمد جدیدی همچنان ابداع میشوند (مثلاً مرتبسازی کتاب خانهای در سال ۲۰۰۴ مطرح شد).
مبحث مرتبسازی در کلاسهای معرفی علم کامپیوتر بسیار پر کاربرد است، مبحثی که در آن وجود الگوریتمهای فراوان به آشنایی با ایدههای کلی و مراحل طراحی الگوریتمهای مختلف کمک میکند؛ مانند تحلیل الگوریتم، دادهساختارها، الگوریتمهای تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.
طبقه بندي:
در علم کامپیوتر معمولاً الگوریتمهای مرتبسازی بر اساس این معیارها طبقهبندی میشوند:
-
پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتبسازیهای معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n۲ است. بهترین عملکرد برای مرتبسازی (O(n است. الگوریتمهایی که فقط از مقایسهٔ کلیدها استفاده میکنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
-
حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتمهای مرتبسازی «در جا» هستند. یعنی به جز دادههایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتمها به ایجاد مکانهای کمکی در حافظه برای نگهداری اطلاعات موقت نیاز دارند.
-
پایداری: الگوریتمهای مرتبسازی پایدار ترتیب را بین دادههای دارای کلیدهای برابر حفظ میکنند. فرض کنید میخواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نامهای الف و ب همسن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
-
مقایسهای بودن یا نبودن. در یک مرتبسازی مقایسهای دادهها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب میشوند.
-
روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتبسازی حبابی و مرتبسازی سریع و گزینشی مانند مرتبسازی پشتهای.
الگوریتم مرتب سازی حبابی:
اين الگوريتم ساده ترين و معروف ترين الگوريتم براي مرتب سازي داده است.
فرض کنید میخواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض میکنیم. همین کار را با عناصر دوم و سوم انجام میدهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگترین عنصر بین دادهها به آخر لیست میرسد . حالا یک بار دیگر از اول این کار را انجام میدهیم اما این بار تا عنصر (n -۱)ام ادامه میدهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار میکنیم ، و بازهم .... تا اینکه بالاخره دادهها مرتب میشوند.
مثلا:
۰ - ۰) ۵ ۶ ۴ ۲
۱ - ۱) ۵ ۶ ۴ ۲
۱ - ۲) ۵ ۴ ۶ ۲
۱ - ۳) ۵ ۴ ۲ ۶
۲ - ۱) ۴ ۵ ۲ ۶
۲ - ۲) ۴ ۲ ۵ ۶
۳ - ۱) ۲ ۴ ۵ ۶
مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم میشوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:
۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴
۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴
۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴
۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۱) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۲) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۳) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۴) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۳) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۵ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
همونطور که میبینید انتهای مرحله ۲ دادهها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحلهای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه میشه که دادهها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن میشیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست.